第一章算法概要课件

第一章算法概要第一章算法概要2020/11/262020/11/261 1第二章第二章基本数据结构及其运算（五）基本数据结构及其运算（五）n n树的基本概念树的基本概念树的基本概念树的基本概念n n二叉树二叉树二叉树二叉树2020/11/262 2n n1 1 树的基本概念树的基本概念树的基本概念树的基本概念n n非线性结构非线性结构非线性结构非线性结构uu对于结构中的一个结点，可能有多个前趋和多个后继对于结构中的一个结点，可能有多个前趋和多个后继对于结构中的一个结点，可能有多个前趋和多个后继对于结构中的一个结点，可能有多个前趋和多个后继uu线性表中是有且仅有一个前趋和一个后继线性表中是有且仅有一个前趋和一个后继线性表中是有且仅有一个前趋和一个后继线性表中是有且仅有一个前趋和一个后继n n1.11.1树的定义树的定义树的定义树的定义 uu树是以分支关系定义的层次结构。树是以分支关系定义的层次结构。树是以分支关系定义的层次结构。树是以分支关系定义的层次结构。uu倒生树：树根在上，根上分茎，茎上分叶倒生树：树根在上，根上分茎，茎上分叶倒生树：树根在上，根上分茎，茎上分叶倒生树：树根在上，根上分茎，茎上分叶uu是族谱、社会组织机构一类实体的逻辑抽象是族谱、社会组织机构一类实体的逻辑抽象是族谱、社会组织机构一类实体的逻辑抽象是族谱、社会组织机构一类实体的逻辑抽象树的基本概念树的基本概念2020/11/263 3n n对定义的理解对定义的理解对定义的理解对定义的理解uu（1 1）有限集）有限集）有限集）有限集uu（2 2）递归定义：树，根，子树）递归定义：树，根，子树）递归定义：树，根，子树）递归定义：树，根，子树uu（3 3）有且仅有一个根结点）有且仅有一个根结点）有且仅有一个根结点）有且仅有一个根结点uu（4 4）子树是互不相交的有限集）子树是互不相交的有限集）子树是互不相交的有限集）子树是互不相交的有限集uu（5 5）树的层次性）树的层次性）树的层次性）树的层次性有且仅有一个根结点有且仅有一个根结点有且仅有一个根结点有且仅有一个根结点除根结点以外的结点有且仅除根结点以外的结点有且仅除根结点以外的结点有且仅除根结点以外的结点有且仅有一个父结点有一个父结点有一个父结点有一个父结点树的定义树的定义2020/11/264 4n n树是一种数据结构树是一种数据结构树是一种数据结构树是一种数据结构uuTree=(D,R)Tree=(D,R)D D：元素的集合：元素的集合：元素的集合：元素的集合R R：元素关系的集合：元素关系的集合：元素关系的集合：元素关系的集合vv（父、子关系（父、子关系（父、子关系（父、子关系 前件、后件关系）前件、后件关系）前件、后件关系）前件、后件关系）vv各结点没有或仅有一个父结点各结点没有或仅有一个父结点各结点没有或仅有一个父结点各结点没有或仅有一个父结点vv有且仅有一个根结点有且仅有一个根结点有且仅有一个根结点有且仅有一个根结点vv各结点可以有任意个子树各结点可以有任意个子树各结点可以有任意个子树各结点可以有任意个子树树的定义树的定义2020/11/265 5n n1.2 1.2 树的术语树的术语树的术语树的术语n n1 1）结点）结点）结点）结点n n2 2）度与深度）度与深度）度与深度）度与深度根结点根结点根结点根结点没有前驱，仅有后继没有前驱，仅有后继没有前驱，仅有后继没有前驱，仅有后继结点的度：该结点拥有的子树数目。结点的度：该结点拥有的子树数目。结点的度：该结点拥有的子树数目。结点的度：该结点拥有的子树数目。树的度：最大的结点度树的度：最大的结点度树的度：最大的结点度树的度：最大的结点度深度：最大的层次数深度：最大的层次数深度：最大的层次数深度：最大的层次数叶结点叶结点叶结点叶结点(茎茎茎茎)分支结点分支结点分支结点分支结点没有后继，仅有前驱没有后继，仅有前驱没有后继，仅有前驱没有后继，仅有前驱有且仅有一个前驱，可以有多个后继有且仅有一个前驱，可以有多个后继有且仅有一个前驱，可以有多个后继有且仅有一个前驱，可以有多个后继树的术语树的术语2020/11/266 6树的术语树的术语孩子孩子孩子孩子兄弟兄弟兄弟兄弟祖先祖先祖先祖先子孙子孙子孙子孙双亲双亲双亲双亲孩子孩子孩子孩子A A3 3）A A节点的节点的节点的节点的2020/11/267 7树的术语树的术语n n4 4）路径（树枝，分支）路径（树枝，分支）路径（树枝，分支）路径（树枝，分支）uu从从从从K1K1出发自上而下到出发自上而下到出发自上而下到出发自上而下到K2K2所经历的所有结点序列所经历的所有结点序列所经历的所有结点序列所经历的所有结点序列K1K1K2K2K3K3K4K4K5K5K6K6K7K7K1 K4 K7 K2K1 K4 K7 K2树上两节点之间的路径有？条树上两节点之间的路径有？条树上两节点之间的路径有？条树上两节点之间的路径有？条2020/11/268 8树的术语树的术语n n5 5）有序树与无序树）有序树与无序树）有序树与无序树）有序树与无序树uu有序树：兄弟有长幼之分，从左至右。交换兄弟位置，变成不同的树。有序树：兄弟有长幼之分，从左至右。交换兄弟位置，变成不同的树。有序树：兄弟有长幼之分，从左至右。交换兄弟位置，变成不同的树。有序树：兄弟有长幼之分，从左至右。交换兄弟位置，变成不同的树。2020/11/269 9树的术语树的术语n n6 6）森林）森林）森林）森林uu不相交的树的集合不相交的树的集合不相交的树的集合不相交的树的集合2020/11/261010二叉树二叉树n n2 2 二叉树二叉树二叉树二叉树n n2.12.1、定义、定义、定义、定义uu二叉树是结点的有限集，或为空，或由根的左、右子树组成，左右子树又分别是符合定义的二叉树。二叉树是结点的有限集，或为空，或由根的左、右子树组成，左右子树又分别是符合定义的二叉树。二叉树是结点的有限集，或为空，或由根的左、右子树组成，左右子树又分别是符合定义的二叉树。二叉树是结点的有限集，或为空，或由根的左、右子树组成，左右子树又分别是符合定义的二叉树。uu对比树的定义：对比树的定义：对比树的定义：对比树的定义：空二叉树空二叉树空二叉树空二叉树 树的定义中没有空树的概念树的定义中没有空树的概念树的定义中没有空树的概念树的定义中没有空树的概念不多于不多于不多于不多于2 2个孩子个孩子个孩子个孩子 树的节点可以有任意个子树树的节点可以有任意个子树树的节点可以有任意个子树树的节点可以有任意个子树子树有左右之分子树有左右之分子树有左右之分子树有左右之分 无序树可不区分左右无序树可不区分左右无序树可不区分左右无序树可不区分左右uu树的其它定义适用于二叉树：根茎叶、度、路径树的其它定义适用于二叉树：根茎叶、度、路径树的其它定义适用于二叉树：根茎叶、度、路径树的其它定义适用于二叉树：根茎叶、度、路径仍然是递归定义。仍然是递归定义。仍然是递归定义。仍然是递归定义。二叉树是树吗？二叉树是树吗？二叉树是树吗？二叉树是树吗？2020/11/261111二叉树二叉树n n（4 4）二叉树的形态）二叉树的形态）二叉树的形态）二叉树的形态空树空树空树空树无子树无子树无子树无子树仅有左子树仅有左子树仅有左子树仅有左子树有左右子树有左右子树有左右子树有左右子树仅有右子树仅有右子树仅有右子树仅有右子树2020/11/261212二叉树的性质二叉树的性质n n2.22.2、二叉树的性质、二叉树的性质、二叉树的性质、二叉树的性质uu（1 1）在二叉树的第）在二叉树的第）在二叉树的第）在二叉树的第i i层上最多有层上最多有层上最多有层上最多有2 2i-1i-1个结点个结点个结点个结点第第第第i i层的结点数最多是第层的结点数最多是第层的结点数最多是第层的结点数最多是第i-1i-1层的两倍层的两倍层的两倍层的两倍uu（2 2）深度为）深度为）深度为）深度为k k的二叉树最多有的二叉树最多有的二叉树最多有的二叉树最多有2 2k k-1-1个结点个结点个结点个结点uu（3 3）叶结点数比具有两个孩子的结点数多）叶结点数比具有两个孩子的结点数多）叶结点数比具有两个孩子的结点数多）叶结点数比具有两个孩子的结点数多 个个个个1二叉树的数学特性二叉树的数学特性二叉树的数学特性二叉树的数学特性二叉树与二进制之间存在必然联系，二叉树与二进制之间存在必然联系，进而可以与整个数学发生关联了进而可以与整个数学发生关联了2020/11/261313二叉树的性质二叉树的性质n n（3 3）叶结点数比具有两个孩子的结点数多）叶结点数比具有两个孩子的结点数多）叶结点数比具有两个孩子的结点数多）叶结点数比具有两个孩子的结点数多1 1个个个个设设设设n n0 0为叶结点个数，为叶结点个数，为叶结点个数，为叶结点个数，n n1 1为具有一个孩子的分支结点个数，为具有一个孩子的分支结点个数，为具有一个孩子的分支结点个数，为具有一个孩子的分支结点个数，n n2 2为具有两个孩子的分支结点个数，为具有两个孩子的分支结点个数，为具有两个孩子的分支结点个数，为具有两个孩子的分支结点个数，n n为结点总个数为结点总个数为结点总个数为结点总个数结论：结论：结论：结论：n n0 0=n n2 2+1;+1;条件条件条件条件1 1、n=n=n n0 0+n n1 1+n+n2 2条件条件条件条件2 2、n=n=分支的个数分支的个数分支的个数分支的个数 +1+1设为分支的个数为设为分支的个数为设为分支的个数为设为分支的个数为B B条件条件条件条件3 3、B=2 nB=2 n2 2+n+n1 1所以：所以：所以：所以：2n2n2 2+n+n1 1+1=n+1=n0 0+n+n1 1+n+n2 22020/11/261414二叉树的性质二叉树的性质n n（4 4）深度为）深度为）深度为）深度为K K的满二叉树，结点个数为的满二叉树，结点个数为的满二叉树，结点个数为的满二叉树，结点个数为2 2k k-1-1uu满二叉树：所有的结点要么有两个孩子，要么一个也没有。所有的叶结点都位于同一层。满二叉树：所有的结点要么有两个孩子，要么一个也没有。所有的叶结点都位于同一层。满二叉树：所有的结点要么有两个孩子，要么一个也没有。所有的叶结点都位于同一层。满二叉树：所有的结点要么有两个孩子，要么一个也没有。所有的叶结点都位于同一层。uu满二叉树：满二叉树：满二叉树：满二叉树：“装满装满装满装满”节点的二叉树节点的二叉树节点的二叉树节点的二叉树uu半满二叉树：深度为半满二叉树：深度为半满二叉树：深度为半满二叉树：深度为K K的二叉树，的二叉树，的二叉树，的二叉树，K K1 1层是满二叉树，层是满二叉树，层是满二叉树，层是满二叉树，K K层节点个数不足层节点个数不足层节点个数不足层节点个数不足2 2K K1 1个个个个2020/11/261515二叉树的性质二叉树的性质n n（5 5）具有）具有）具有）具有n n个节点的完全二叉树，深度为个节点的完全二叉树，深度为个节点的完全二叉树，深度为个节点的完全二叉树，深度为loglog2 2n+1n+1uu完全二叉树：特殊的半满二叉树，最后一层节点从左至右依次排列，没有间断。完全二叉树：特殊的半满二叉树，最后一层节点从左至右依次排列，没有间断。完全二叉树：特殊的半满二叉树，最后一层节点从左至右依次排列，没有间断。完全二叉树：特殊的半满二叉树，最后一层节点从左至右依次排列，没有间断。uu如果对节点数为如果对节点数为如果对节点数为如果对节点数为n n的完全二叉树自上而下，从左至右依次编号，则节点的完全二叉树自上而下，从左至右依次编号，则节点的完全二叉树自上而下，从左至右依次编号，则节点的完全二叉树自上而下，从左至右依次编号，则节点i i的父结点为的父结点为的父结点为的父结点为 i/2 i/2 1 12 23 34 45 56 6uu若若若若2i2inn，则，则，则，则i i的的的的左左左左后继是后继是后继是后继是2i2i；若；若；若；若2in,2in,则则则则i i无无无无左左左左后继后继后继后继uu若若若若2i2i1n1n，则，则，则，则i i的的的的右右右右后继是后继是后继是后继是2i2i1 1；若；若；若；若2in,2in,则则则则i i无无无无右右右右后继后继后继后继2020/11/261616完全二叉树完全二叉树n n关于完全二叉树的其他描述形式关于完全二叉树的其他描述形式关于完全二叉树的其他描述形式关于完全二叉树的其他描述形式uu如果对满二叉树的节点从上至下，从左至右连续编号，具有如果对满二叉树的节点从上至下，从左至右连续编号，具有如果对满二叉树的节点从上至下，从左至右连续编号，具有如果对满二叉树的节点从上至下，从左至右连续编号，具有n n个节点的完全二叉树各节点与同样深个节点的完全二叉树各节点与同样深个节点的完全二叉树各节点与同样深个节点的完全二叉树各节点与同样深度的满二叉树的前度的满二叉树的前度的满二叉树的前度的满二叉树的前n n个节点一一对应个节点一一对应个节点一一对应个节点一一对应uu叶节点仅位于下两层，对任一节点，若其右子树的深度为叶节点仅位于下两层，对任一节点，若其右子树的深度为叶节点仅位于下两层，对任一节点，若其右子树的深度为叶节点仅位于下两层，对任一节点，若其右子树的深度为1 1，则其左子树的深度不小于，则其左子树的深度不小于，则其左子树的深度不小于，则其左子树的深度不小于1 12020/11/261717二叉树二叉树满二叉树满二叉树满二叉树满二叉树半满二叉树半满二叉树半满二叉树半满二叉树完全二叉树完全二叉树完全二叉树完全二叉树非完全二叉树非完全二叉树非完全二叉树非完全二叉树半满二叉树半满二叉树半满二叉树半满二叉树半满二叉树半满二叉树半满二叉树半满二叉树非完全二叉树非完全二叉树非完全二叉树非完全二叉树2020/11/261818二叉树的遍历二叉树的遍历n n2.32.3、二叉树的操作、二叉树的操作、二叉树的操作、二叉树的操作n n2.3.12.3.1遍历操作遍历操作遍历操作遍历操作uu分支及根的遍历顺序分支及根的遍历顺序分支及根的遍历顺序分支及根的遍历顺序A AB BC C中根遍历中根遍历中根遍历中根遍历中序遍历中序遍历中序遍历中序遍历A AC C先根遍历先根遍历先根遍历先根遍历先序遍历先序遍历先序遍历先序遍历B B后根遍历后根遍历后根遍历后根遍历后序遍历后序遍历后序遍历后序遍历A A A AB B B BC C C Cuu以根被访问顺序来划分不同的遍历方法以根被访问顺序来划分不同的遍历方法以根被访问顺序来划分不同的遍历方法以根被访问顺序来划分不同的遍历方法uu在子树的访问顺序中始终以左子树优先在子树的访问顺序中始终以左子树优先在子树的访问顺序中始终以左子树优先在子树的访问顺序中始终以左子树优先特点：特点：特点：特点：左左左左 根根根根 右右右右根根根根 左左左左 右右右右左左左左 右右右右 根根根根2020/11/261919二叉树的遍历二叉树的遍历n n1 1）中根遍历（中序遍历）中根遍历（中序遍历）中根遍历（中序遍历）中根遍历（中序遍历）ABCDEFGHIJKLMNOPQF G C E H B D J I A L N P O Q M K左左 根根 右右2020/11/262020二叉树的遍历二叉树的遍历n n2 2）先根遍历（先序遍历）先根遍历（先序遍历）先根遍历（先序遍历）先根遍历（先序遍历）ABCDEFGHIJKLMNOPQA B C F G E H D I J K L M N O P Q根根 左左 右右2020/11/262121二叉树的遍历二叉树的遍历n n3 3）后根遍历（后序遍历）后根遍历（后序遍历）后根遍历（后序遍历）后根遍历（后序遍历）ABCDEFGHIJKLMNOPQG F H E C J I D B P Q O N M L K A左左 右右 根根2020/11/262222思考：思考：思考：思考：uu第一个被遍历的节点，第一个被遍历的节点，第一个被遍历的节点，第一个被遍历的节点，uu最后一个被遍历的节点，最后一个被遍历的节点，最后一个被遍历的节点，最后一个被遍历的节点，课堂练习课堂练习n n写出这颗二叉树的三种遍历顺序写出这颗二叉树的三种遍历顺序写出这颗二叉树的三种遍历顺序写出这颗二叉树的三种遍历顺序ABCDEFGHIJKLMNOPQ3 3、后根遍历（左右根）、后根遍历（左右根）、后根遍历（左右根）、后根遍历（左右根）A B C F G E H D I J K L M N O P QG F H E C J I D B P Q O N M L K A1 1、中根遍历（左根右）中根遍历（左根右）中根遍历（左根右）中根遍历（左根右）2 2、先根遍历（根左右）、先根遍历（根左右）、先根遍历（根左右）、先根遍历（根左右）F G C E H B D J I A L N P O Q M K2020/11/262323树的存储树的存储n n2.42.4树的存储树的存储树的存储树的存储n n2.4.12.4.1连续顺序存储连续顺序存储连续顺序存储连续顺序存储K1K1K2K2K5K5K4K4K6K6a 0 a 0 a 1 a 1 a 2 a 2 a 3 a 3 a 4 a 4 连续线性的下标不能很好的反映树的分支关系（非线性）连续线性的下标不能很好的反映树的分支关系（非线性）连续线性的下标不能很好的反映树的分支关系（非线性）连续线性的下标不能很好的反映树的分支关系（非线性）2020/11/262424DATADATA子树子树子树子树1 12 23 3树的存储树的存储n n2.4.22.4.2、链接存储多重链表、链接存储多重链表、链接存储多重链表、链接存储多重链表uu树的节点树的节点树的节点树的节点 对应于对应于对应于对应于 链表的结点链表的结点链表的结点链表的结点uu树节点间的分支关系用结点间的指针描述树节点间的分支关系用结点间的指针描述树节点间的分支关系用结点间的指针描述树节点间的分支关系用结点间的指针描述uu结点可能有多个指针多重链表，每个指针描述对应节点的一个分支关系结点可能有多个指针多重链表，每个指针描述对应节点的一个分支关系结点可能有多个指针多重链表，每个指针描述对应节点的一个分支关系结点可能有多个指针多重链表，每个指针描述对应节点的一个分支关系有且仅有一个根结点有且仅有一个根结点有且仅有一个根结点有且仅有一个根结点不同的指针指向不同的子树根结点不同的指针指向不同的子树根结点不同的指针指向不同的子树根结点不同的指针指向不同的子树根结点一个子树有仅有一个根结点一个子树有仅有一个根结点一个子树有仅有一个根结点一个子树有仅有一个根结点问题，一个结点里究竟该有多少个指针呢？问题，一个结点里究竟该有多少个指针呢？问题，一个结点里究竟该有多少个指针呢？问题，一个结点里究竟该有多少个指针呢？2020/11/262525顺序存储二叉树顺序存储二叉树n n2.5.1 2.5.1 顺序存储二叉树顺序存储二叉树顺序存储二叉树顺序存储二叉树uu将完全二叉树从上到下，从左到右编号后，结点号码可作为数组的下标，从而将完全二叉树顺序存将完全二叉树从上到下，从左到右编号后，结点号码可作为数组的下标，从而将完全二叉树顺序存将完全二叉树从上到下，从左到右编号后，结点号码可作为数组的下标，从而将完全二叉树顺序存将完全二叉树从上到下，从左到右编号后，结点号码可作为数组的下标，从而将完全二叉树顺序存储下来。当给出任意结点储下来。当给出任意结点储下来。当给出任意结点储下来。当给出任意结点i i，我们可以知道它的父结点为，我们可以知道它的父结点为，我们可以知道它的父结点为，我们可以知道它的父结点为 i/2 i/2，两个孩子分别为，两个孩子分别为，两个孩子分别为，两个孩子分别为2i2i和和和和2i2i1 1。uu一般的二叉树相对于同样深度的完全二叉树，缺失了部分结点，在顺序存储时，这些位置要空出来。一般的二叉树相对于同样深度的完全二叉树，缺失了部分结点，在顺序存储时，这些位置要空出来。一般的二叉树相对于同样深度的完全二叉树，缺失了部分结点，在顺序存储时，这些位置要空出来。一般的二叉树相对于同样深度的完全二叉树，缺失了部分结点，在顺序存储时，这些位置要空出来。以维持结点编号之间的父子换算关系以维持结点编号之间的父子换算关系以维持结点编号之间的父子换算关系以维持结点编号之间的父子换算关系uu如此存放，将浪费较多空间如此存放，将浪费较多空间如此存放，将浪费较多空间如此存放，将浪费较多空间2020/11/262626顺序存储二叉树顺序存储二叉树n n例例例例H HA AC CB BD DE EGGF FI IK KJ JMMOOU UP P1 12 23 34 45 56 67 78 89 9101011111212131314141515A AH HB BC CE ED DF FGGK KI IMMJ JOOP PU Ua1a1a15a15H HA AC CB BE EGGF FI IU UP PMM1 12 23 34 45 56 67 78 89 9101011111212131314141515A AH HB BC CE EF FGGI IMMP PU Ua1a1a15a15数组的下标可以体现逻辑关系数组的下标可以体现逻辑关系数组的下标可以体现逻辑关系数组的下标可以体现逻辑关系2020/11/262727用链表实现二叉树用链表实现二叉树n n2.5.2 2.5.2 用链表实现二叉树用链表实现二叉树用链表实现二叉树用链表实现二叉树n n二叉树链表结点的定义二叉树链表结点的定义二叉树链表结点的定义二叉树链表结点的定义struct struct B Btnodetnode T data;T data;B Btnodetnode *Lchild;*Lchild;B Btnodetnode *Rchild;*Rchild;dataLchileRchild左孩子，左子树左孩子，左子树左孩子，左子树左孩子，左子树右孩子，右子树右孩子，右子树右孩子，右子树右孩子，右子树2020/11/262828用链表实现二叉树用链表实现二叉树n n二叉树的链表结构二叉树的链表结构二叉树的链表结构二叉树的链表结构dLRdLRdLRdLRdLRdLRdLRdLR2020/11/262929二叉树的建立二叉树的建立n n2.5.3 2.5.3 建立二叉树建立二叉树建立二叉树建立二叉树uu设输入次序：（以先根为序）设输入次序：（以先根为序）设输入次序：（以先根为序）设输入次序：（以先根为序）ABC_ _ DEF _ _ G _ _ _ H _ I _ JK _ _ L _ _ABC_ _ DEF _ _ G _ _ _ H _ I _ JK _ _ L _ _ABC_DEF_G_H_I_JK_L_每一个空格每一个空格每一个空格每一个空格“_”_”表示一个空指针表示一个空指针表示一个空指针表示一个空指针利用先根遍历算利用先根遍历算利用先根遍历算利用先根遍历算法框架，建立二法框架，建立二法框架，建立二法框架，建立二叉树叉树叉树叉树根据输入的情况，根据输入的情况，根据输入的情况，根据输入的情况，将新节点放在指定将新节点放在指定将新节点放在指定将新节点放在指定的位置，然后从新的位置，然后从新的位置，然后从新的位置，然后从新节点开始下一个过节点开始下一个过节点开始下一个过节点开始下一个过程程程程2020/11/263030二叉树的建立二叉树的建立template template void Binary_Tree:creat_Binary_Tree(T end)void Binary_Tree:creat_Binary_Tree(T end)Btnode*p;Btnode*p;T x;T x;cinx;cinx;if(x=end)return;if(x=end)return;create a new node p;create a new node p;p-d=x;p-d=x;p-lchild=NULL;p-lchild=NULL;p-rchild=NULL;p-rchild=NULL;p=new Btnode;p=new Btnode;根据输入，生成新链点，主要包括申请链点空间根据输入，生成新链点，主要包括申请链点空间根据输入，生成新链点，主要包括申请链点空间根据输入，生成新链点，主要包括申请链点空间输入新元素输入新元素输入新元素输入新元素生成整个树的根生成整个树的根生成整个树的根生成整个树的根 BT=p;creat(p,1,end);creat(p,1,end);creat(p,2,end);creat(p,2,end);return;return;以先根遍历算法为基础递归生成二叉树以先根遍历算法为基础递归生成二叉树以先根遍历算法为基础递归生成二叉树以先根遍历算法为基础递归生成二叉树2020/11/263131二叉树的建立二叉树的建立template static creat(Btnode*p,int k,T end)Btnode*q;T x;cinx;if(x!=end)q=new Btnode;q-d=x;q-lchild=NULL;q-rchild=NULL;if(k=1)p-lchild=q;if(k=2)p-rchild=q;creat(q,1,end);creat(q,2,end);return;2020/11/263232二叉树的遍历二叉树的遍历n n中根遍历算法中根遍历算法中根遍历算法中根遍历算法uu算法实现分析算法实现分析算法实现分析算法实现分析uu遍历过程：遍历过程：遍历过程：遍历过程：从根开始从根开始从根开始从根开始ABC1 1、找到、找到、找到、找到B B，但不访问，但不访问，但不访问，但不访问B B2 2、根据、根据、根据、根据B B找到找到找到找到A A，访问，访问，访问，访问A A3 3、再回到、再回到、再回到、再回到B B、访问、访问、访问、访问B B4 4、根据根据根据根据B B找到找到找到找到C C，访问，访问，访问，访问C C方法一、利用栈来实现回朔方法一、利用栈来实现回朔回到回到回溯回溯X2020/11/263333ABCDEFGHIJKLMNOPQ1 1、树（子树）根入栈，不访问、树（子树）根入栈，不访问、树（子树）根入栈，不访问、树（子树）根入栈，不访问2 2、左子树入栈，左子树的各子树根依次入栈即反复进行步骤、左子树入栈，左子树的各子树根依次入栈即反复进行步骤、左子树入栈，左子树的各子树根依次入栈即反复进行步骤、左子树入栈，左子树的各子树根依次入栈即反复进行步骤1 13 3、当左子树为空时，出栈，访问根结点、当左子树为空时，出栈，访问根结点、当左子树为空时，出栈，访问根结点、当左子树为空时，出栈，访问根结点4 4、根节点右子树入栈根节点右子树入栈根节点右子树入栈根节点右子树入栈（新树入栈，到步骤（新树入栈，到步骤（新树入栈，到步骤（新树入栈，到步骤1 1去遍历右子树）去遍历右子树）去遍历右子树）去遍历右子树）5 5、当右子树为空时，、当右子树为空时，、当右子树为空时，、当右子树为空时，出栈，访问（祖先）爷结点，出栈，访问（祖先）爷结点，出栈，访问（祖先）爷结点，出栈，访问（祖先）爷结点，将爷结点的右子树入栈将爷结点的右子树入栈将爷结点的右子树入栈将爷结点的右子树入栈（新树入栈，回到步骤（新树入栈，回到步骤（新树入栈，回到步骤（新树入栈，回到步骤1)1)总结：树入栈后一直朝左走（一路进栈），走不动时出栈并访问节点。同时将该节点右子树入栈。如果其右子树为空，总结：树入栈后一直朝左走（一路进栈），走不动时出栈并访问节点。同时将该节点右子树入栈。如果其右子树为空，总结：树入栈后一直朝左走（一路进栈），走不动时出栈并访问节点。同时将该节点右子树入栈。如果其右子树为空，总结：树入栈后一直朝左走（一路进栈），走不动时出栈并访问节点。同时将该节点右子树入栈。如果其右子树为空，就再出栈一个节点，访问，出栈节点右子树入栈就再出栈一个节点，访问，出栈节点右子树入栈就再出栈一个节点，访问，出栈节点右子树入栈就再出栈一个节点，访问，出栈节点右子树入栈ABCFGEHD2020/11/263434利用递归的遍历算法利用递归的遍历算法n n方法二：利用递归调用来实现回溯方法二：利用递归调用来实现回溯方法二：利用递归调用来实现回溯方法二：利用递归调用来实现回溯n n中根遍历递归算法中根遍历递归算法中根遍历递归算法中根遍历递归算法template template static intrav(Btnode*p)static intrav(Btnode*p)if(p!=NULL)if(p!=NULL)intrav(p-lchild);intrav(p-lchild);coutd ;coutdrchild);intrav(p-rchild);return 0;return 0;左左 根根 右右2020/11/263535n n后根遍历递归算法后根遍历递归算法后根遍历递归算法后根遍历递归算法template template static postrav(Btnode*p)static postrav(Btnode*p)if(p!=NULL)if(p!=NULL)postrav(p-lchild);postrav(p-lchild);postrav(p-rchild);postrav(p-rchild);coutd ;coutd ;return;return;左左 右右 根根利用递归的遍历算法利用递归的遍历算法2020/11/263636利用递归的遍历算法利用递归的遍历算法n n先根遍历递归算法先根遍历递归算法先根遍历递归算法先根遍历递归算法template template static pretrav(Btnode*p)static pretrav(Btnode*p)if(p!=NULL)if(p!=NULL)coutd ;coutdlchild);pretrav(p-lchild);pretrav(p-rchild);pretrav(p-rchild);return;return;根根 左左 右右2020/11/263737树与二叉树的转换树与二叉树的转换n n2.6 2.6 树的二叉表示树的二叉表示树的二叉表示树的二叉表示uu将树转化为二叉树将树转化为二叉树将树转化为二叉树将树转化为二叉树uu规则：规则：规则：规则：把各自的第一子树挂在左链，兄弟挂在右链把各自的第一子树挂在左链，兄弟挂在右链把各自的第一子树挂在左链，兄弟挂在右链把各自的第一子树挂在左链，兄弟挂在右链uu特点：转换后的二叉树，特点：转换后的二叉树，特点：转换后的二叉树，特点：转换后的二叉树，根结点没有右子树根结点没有右子树根结点没有右子树根结点没有右子树12435671234567882020/11/263838template static void LEAF(Btnode*p)if(p!=NULL)if(p-lchild=NULL)&(p-rchild=NULL)coutdlchild);LEAF(p-rchild);return;2020/11/263939template static void CHANG(Btnode*p)if(p!=NULL)if(p-lchild!=NULL)|(p-rchild!=NULL)k=p-lchild;p-lchild=p-rchild;p-rchild=k;CHANG(p-lchild);CHANG(p-rchild);return;2020/11/264040谢谢！谢谢！谢谢！谢谢！2020/11/2641