树结构的定义和基本操作.ppt

第6章 树,6.1 树结构的定义和基本操作 6.2 二叉树 6.3 遍历二叉树 6.4 树和森林 6.5 树的应用 习题,前面谈的基本上是线性表结构，线性表,栈、队列、串、一维数组，即使二维数组(矩阵结构、十字类别)也不过只是线性表的组合，即：除首元素和尾元素以外，每一个元素有唯一的前驱和后续元素。 树形结构是一种重要的非线性结构，讨论的是层次和分支关系，即：除了有一个根元素没有前驱以外，每一个元素都有唯一的前驱元素；另外，每一个元素有零个或多个后继元素。例如，人类社会的族谱和各种社会组织机构都可以用树来形象表示。树在计算机领域中也得到广泛应用。,6.1 树结构的定义和基本操作,6.1.1 树的定义 递归定义： 树(tree)是n(n0)个结点的有限集。在任意一棵树中： (1)有且只有一个特定的称为根(root)的结点。 (2)当n1时，其余结点可分为m(m0)个互不相交的有限集T1，T2，Tm，其中每一个集合本身又是一棵树，称为子树(subtree)。 图6.1所示，在图中的树有13个结点，A是树根，其余结点构成三个互不相交的子集：T1=B，E，F，K，L，T2=C，G，T3=D，H，I，J，M；T1，T2和T3都是根A的子树，且它们本身也是一棵树。如在T1中，B是该子树根，其余结点又构成两个互不相交子集，T11=E，K，L和T12=F，T11和T12都是根B的子树，且它们本身也是一棵树。,图6.1 树的示例,上面是树的一个递归定义，树除了该递归定义外，还有其它定义。如图6.2所示为图6.1中树的各种表示.,从图6.1的示例可以看出，树有两个特点： (1) 树的根结点没有前驱结点，其余结点有且只有一个前驱结点。 (2) 树结点可以有零个或多个后继结点。 树结构描述的是层次和分支关系。,图6.2 树的其它三种表示方法,图6.2(a)是以嵌套集合的形式表示(任何两个集合，或不相交，或一个包含另一个)；图6.2(b)是以广义表的形式表示，根作为子树森林组成的表的名字写在表的左边；图6.2(c)用的是凹入表示法。,6.1.2 树的常用术语 结点：是包含一个数据元素和若干指向其子树的分支 (即关系). 结点的度：结点拥有的子树数。 叶子：度为0的结点。 分支结点：度不为0的结点。 树的度：树内各结点的度的最大值，图6.1所示树是 一 个3叉树. 孩子结点(child)：结点的后继，结点子树的根结点。 双亲结点(parent)：孩子结点的前驱。s是f的孩子,则f是s的双亲. 兄弟结点(sibling)：同一个双亲的孩子之间互称为兄弟。 祖先结点：从根到该结点的所经过分支上的所有结点, 图6.1树中L结点的祖先结点是A，B，F。,子孙结点：以某结点为根的子树中任一结点都称为该结点 的子孙. 图6.1树中D的子孙结点为H，I，J，M. 结点的层次：根是第1层，依次为第2层。 树的深度：树中结点的最大层次，图6.1所示的树深度为4. 有序树：树中结点的各子树看成从左至右是有次序的,例 如, 人类社会的族谱就是一个有序树。 无序树：树中结点的各子树没有次序的，孩子结点的顺 序可以调整。 森林：m(m0)棵互不相交的树的集合。森林和树之 间的联系是：一棵树取掉根，其子树构成一个 森林；同样，一个森林增加一个根结点成为树.,6.1.3 树的基本操作 (1)initiate(T)：T树的初始化，包括建树。 (2)root(T)：求T树的根。 (3)parent(T,x)：求T树中x结点的双亲结点。 (4)child(T,x,i)：求T树中x结点的第i个孩子结点。 (5)right_sibling(T,x)：求T树中x结点的右兄弟。 (6)Insert_child(y,i,x)：将根为x的子树置为y结点的第i个孩子 (7)del_child(x,i)：删除x结点的第i个孩子(整个子树)。 (8)traverse(T)：遍历T树。按某个次序依次访问树中每一个结点，并使每个结点都被访问且只被访问一次。 (9)clear(T)置空T树。 以上操作的具体实现，依赖于采用的存储结构。,6.2 二叉树,6.2.1 定义及其操作 二叉树是另一种树形结构，它的特点是每一个结点至多只有两棵子树，并且，子树有左、右之分，其次序不能颠倒。 递归定义：二叉树是n(n0)个结点有限集，当n1时，有而且仅有一个结点为根结点，其余结点构成为2个互不相交的子集T1，T2，其中每一个子集又是一棵二叉树，分别称作为根结点的左子树和右子树。 注意：二叉树不是度为2的树，在度为2的树中，当一个结点的度为1时，其子树是不考虑序的；而在二叉树中，当一个结点的度为1时，其子树要考虑序，即：是作为双亲的左子树还是作为双亲右子树。另外，树不允许为空树，但二叉树允许为空。 由二叉树的递归定义可知，二叉树有五种基本形态，如图6.3所示。,(a)空树 (b)仅有根 (c)右子树空 (c)左、右子树均在 d)左子树空,图6.3 二叉树的五种形态,由二叉树的递归定义可知，二叉树有五种基本形态，如图6.3所示。与树的基本操作类似，二叉树有下面一些基本操作： (l)lch(T,x)：求T树中x结点的左孩子。 (2)rch(T,x)：求T树中x结点的右孩子。 (3)lsibling(T,x)：求T树中x结点的左兄弟。 (4)rsibling(T,x)：求T树中x结点的右兄弟。 其他操作与树相同。,6.2.2 二叉树的性质 二叉树具有下列重要性质。 性质1：在二叉树的第i层上至多有2i-1个结点(i1)。 当i=1时，只有一个根结点，2i-1=20=1，由于二叉树的每一个结点的度最多为2，因此，当i2时，第i层上的结点数，最多为上一层的2倍，所以，第2层最多有21=21个结点，第3层最多有221=22个，依次类推，第i层最多有22i-2=2i-1个。 性质2：深度为k的二叉树至多有2k -1个结点(k1)。 由性质1可见，深度为k的二叉树的最大结点数为： (第i层上的最大结点数)=2i-1=2k-1,性质3：对任何一棵二叉树T，如果其叶子结点数为n0，度 为2的结点数为n2，则n0=n2+1。 在二叉树中，度为1的结点为n1，这样树的结点数 n=n0+n1+n2 另外，除根结点外每个结点都有唯一的双亲结点指向该结点，所以度为1的结点指向一个后续，而度为2的结点指向两个后续，因此，二叉树结点数n=n1+2*n2+1。 因为 n=n0+n1+n2=n1+2*n2+1 可得 n0=n2+1,下面介绍两种特殊的二叉树。 满二叉树：一棵深度为k的二叉树，若其有2k-1个结点，则称为满二叉树。在满二叉树中只有度为0和度为2的结点，并且在每一层上的结点数都是该层所能取结点的最大值。如图6.4(a)所示为一个深度为4的满二叉树。,(a) 满二叉树,完全二叉树：一个深度为k的二叉树，其结点数n2k-1，并且这n个结点所构成的二叉树，与一个深度为k的满二叉树前n个结点位置相同，则该树是一个深度为k的完全二叉树。如图6.4(b)所示为一个深度为4，结点数为12的完全二叉树。深度为k的完全二叉树，其前k-1层是满二叉树，最后第k层的结点依次排在左边的位置上。,(b)完全二叉树,完全二叉树有如下两个重要性质。 性质4：具有n个结点的完全二叉树的深度为trunc(log2n)+1。(注：trunc(x)为取整函数，该函数无条件舍掉x的小数部分) 性质5：如果对一棵有n个结点的完全二叉树(其深度trunc(log2n)+1)的结点按顺序标号，标号的顺序从根开始，按层次自上而下，在每一层上从左至右，如图6.4(b)所示的完全二叉树，就是按此规则标号，对于树中任意标号为i的结点有以下特性： (1)i1时，i的双亲结点是trunc(i/2)。 (2)若2in，则i的左孩子是标号为2i的结点；若2in，则该结点不存在左孩子。 (3)若2i+1n，则i的右孩子是标号为2i+1的结点；若2i+1n，则该结点不存在右孩子。,6.2.3 二叉树的存储结构 (1)顺序存储结构 满二叉树或完全二叉树顺序存储方式: 即用一个数组按结点的标号顺序依次存放二叉树中的数据元素。图6.4(b)是一棵完全二叉树，可以用一维数组bt12作为它的存储结构，将二叉树中标号为i的结点的数据元素存放在分量bti-1中，如图6.5(a)所示。存储位置暗藏了树中的关系，树的关系是通过完全二叉树的性质实现，例如bt5的双亲结点标号是k=trunc(i+1)/2=3，双亲结点所对应的数组分量btk-1=bt2。,(a)完全二叉树,非完全二叉树，也必须按完全二叉树的形式存储，如图6.5(b)所示，图中“0”表示该结点不存在。对于畸形二叉树(树中大量存在度为1和度为0的结点)，采用顺序存储方式，空间浪费较大。,(b)非完全二叉树,(2)链式结构 由于二叉树是一种非线性结构，一般情况下采用链式存储结构。不同的结点结构，可以构成不同的链式结构，常用的有以下两种。 (a)标准存储(也称为“二叉链表”)。 每一个结点有三个域，即：数据域、左指针、右指针。用C语言描述如下： struct bitnode int data; struct node *lch,*rch; typedef struct bitnode BiTNode;,(b)带逆存储(也称为“三叉链表”)。 在二叉链表中，便于找到一个结点的左右孩子，但要找一个结点的双亲不方便，必须从树根开始遍历整个二叉树，所以，在结点中增加一个指向双亲结点的指针域。结点的结构如下： struct tritnode int data; struct node *lch,*rch,*parent; ; typedef struct tritnode TriTnode; 图6.6是一个二叉树的两种链式存储结构图示。从图中可知，二叉树的链式存储结构和逻辑结构是一致的。,(a)二叉树逻辑结构 (b)二叉链表 (c)二叉链表,图6.6 二叉树的链式存储结构,6.3 遍历二叉树,一个遍历二叉树的问题，即：按一定规律访问二叉树上的每个结点，且每个结点只能访问一次。这里“访问”的含义很广，可以是对结点作各种处理。 在线性结构中，因为除尾结点外，每一个结点都有唯一后续，所以只要从首结点开始，每次取后继结点就可以遍历线性结构中每一个结点。而二叉树是一种非线性结构，每一个结点可能有两个后续，因此需要寻找一种规律，将层次形的二叉树序列转化为一个线性序列。 由递归定义可知，二叉树是由三个基本单元组成，即：根结点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树。若以(，T，R分别表示遍历左子树、访问根和遍历右子树，则可有六种遍历方案：TLR，LTR，LRT，TRL，RTL，RLT。通常限定先遍历左子树，后遍历右子树。所以，二叉树的遍历主要指前三种。,6.3.1 二叉树遍历的递归算法 (1)前序遍历(TLR)递归算法 前序遍历(也可以称为前序遍历)二叉树的操作定义为： 若二叉树为空，则空操作(不作任何操作)；否则 (1)访问根结点。 (2)前序访问左子树。 (3)前序访问右子树。 算法6.1 前序遍历二叉树的递归算法。 void prev(BiTNode *root) if(root!=NULL) printf(“%d,“,root-data);/* 访问根结点 */ prev(root-lch); prev(root-rch); ,(2)中序遍历(LTR)递归算法 中序遍历二叉树的操作定义为： 若二叉树为空，则空操作(不作任何操作)；否则， (1)中序访问左子树。 (2)访问根结点。 (3)中序访问右子树。 由中序遍历的定义，可得到中序遍历二叉树的递归算法如下： 算法6.2 中序遍历二叉树的递归算法。 void mid(BiTNode *root) if(root!=NULL) mid(root-lch); printf(“%d,“,root-data);/* 访问根结点 */ mid(root-rch); ,(3)后序遍历(LRT)递归算法 后序遍历二叉树的操作定义为： 若二叉树为空，则空操作(不作任何操作)；否则， (1)后序访问左子树； (2)后序访问右子树； (3)访问根结点； 由后序遍历的定义，可得到后序遍历二叉树的递归算法如下。 算法6.3 后序遍历二叉树的递归算法。 void pos(BiTNode *root) if(root!=NULL) pos(root-lch); pos(root-rch); printf(“%d,“,root-data);/* 访问根结点 */ ,图6.7 表达式(a*(b-c)+d/e)的二叉树,前序遍历二叉树, 得到二叉树的前序序列为: +*a-bc/de 中序遍历二叉树，得到此树的中序序列为: a*b-c+d/e 后序遍历二叉树，得到此树的后序序列为: abc-*de/+,递归算法逻辑清晰、易懂，但在实现时，由于函数调用栈层层叠加，所以效率不高(每次函数调用，都要保存函数返回地址，实现参数传递，创建局部变量)，下面讨论二叉树遍历的非递归算法。,6.3.2 二叉树遍历的非递归算法 (1)前序非递归的算法 前序遍历的特点是：首先访问根，访问完根后访问左子树，所以对每一个结点，在访问完该结点后，沿其左链访问下来，直到左链为空，这时，所有已被访问过的结点进栈。然后结点出栈，对于每一个出栈结点，即表示该结点和其左子树已被访问结束，按照前序遍历的定义，应该访问该结点的右子树。 (1)当前指针指向根结点。 (2)打印当前结点，当前指针指向其左孩子并进栈，重复(2)，直至左孩子为NULL。 (3)依次退栈，将当前指针指向右孩子。 (4)若栈非空或当前指针非NULL，执行2；否则结束。,算法6.4 前序遍历二叉树的非递归算法。 void BiT_PreOrder(BiTNode *root) BiTNode *p,*nodeMAX; int top=0; p=root; do while(p!=NULL) printf(“%d,“,p-data); nodetop=p; top+; p=p-lch; if(top0) top-; p=nodetop; p=p-rch; /* 凡是退栈的指针，其所指的结点及其左子树，都已遍历 */ while(top0|p!=NULL); ,(2)中序非递归的算法 中序的特点是：首先访问左子树，所以对每一个结点，沿其左链走下来，直到左链为空，所有经过的结点进栈。然后结点出栈，对于每一个出栈结点，即表示该结点的左子树已访问结束，按照中序遍历的定义，应该访问该结点(根)，访问完该结点后，访问该结点的右子树。 (1)当前指针指向根结点。 (2)当前结点进栈，当前指针指向其左孩子，重复(2)，直至左孩子为NULL。 (3)依次退栈，退栈指针成为当前指针，打印当前结点。 (4)将当前指针指向右孩子。 (5)若栈非空或当前指针非NULL，执行2；否则结束。,算法6.5 中序遍历二叉树的非递归算法。 void BiT_MidOrder(BiTNode *root) BiTNode *p,*nodeMAX; int top=0; p=root; do while(p!=NULL) nodetop=p; top+; p=p-lch; if(top0) top-; p=nodetop; printf(“%d,“,p-data ); p=p-rch; /* 凡是退栈的指针，其所指的结点的左子树，都已遍历 */ while(top0|p!=NULL); ,(3)后序非递归的算法 后序的特点是：在左、右子树都被访问结束后，才能访问根，所以，每一个出栈的结点都要判断是访问完左子树返回根，还是访问完右子树返回根，一个结点只有在其右子树访问结束后，才能访问该结点。因此，需要对进栈的指针进行补充说明，在这里引入了一个标志栈int flagMAX。 （1)当前指针指向根结点。 （2)当前结点进栈，所对应的标志栈为0，当前指针指向其左孩子，重复(2)，直至左孩子为NULL。 （3)判断栈顶元素的标志，若为1，则依次退栈，并打印退栈指针所指结点，直到标志为0。 （4)将栈顶元素的标志变为1，将当前指针为指向栈顶元素的右孩子。 （5)若栈非空或当前指针非NULL，执行2；否则结束。,算法6.6 后序遍历二叉树的非递归算法(#define LEFT 0, #define RIGHT 1) void BiT_PostOrder(BiTNode *root) BiTNode *p, *nodeMAX; int top,flagMAX; p=root;top=0; /* top指向下一个进栈的位置 */ do while(p!=NULL) /* 结点非空，进栈，遍历左子树，直至最左下结点 */ nodetop=p; flagtop=LEFT; top+; p=p-lch; while(top0 ,6.3.3 二叉树的层次遍历算法 按照层次遍历二叉树，是通过队列实现的。首先，将根的结点入列；然后，每次判断队列是否为空；若队列不为空，则取出队首元素所对应的结点，并将该不为空(NULL)的孩子结点的指针入列；如若队列为空，则遍历结束。 算法6.7二叉树的层次遍历算法。 void TravelByLevel(BiTNode *root) BiTNode *p; Queue Q; /* Q为指针队列 */ Queue_Init( ,6.3.4 遍历算法的应用 (1) 一种建树算法 已知树的结构，可以写出唯一的前序序列。但反之，则不能建立唯一的树结构。这里推荐一种改进的前序遍历方法，其遍历序列可以和树结构一一对应。该遍历方法对空指针用字符*表示。于是6.8图的前序序列为“ABD*E*C*“。由于这样的序列和树结构一一对应，所以可以用此类序列作为建树的参数。,图6.8,图6.8,算法6.8 一种建立二叉树的算法。 /* s中为带空指针记号的前序序列， *pi为下标在，函数调用中被改变*/ BiTNode *BiT_Create(char s,int *pi) BiTNode *root; char ch; ch=s*pi; *(pi)+; if(ch=*) return(NULL); /* 创建根结点 */ root=(BiTNode *)malloc(sizeof(BiTNode); root-data=ch; /* 创建左子树，并将左子树的根指针赋给root-lchild */ root-lchild=BiT_Create(s, pi); /* *pi在调用中已被修改 */ /* 创建右子树，并将右子树的根指针赋给root-lchild */ root-rchild=BiT_Create(s, pi); return(root); main() char s20=“ABD*E*C*“; int i=0; BiTNode *root; root=BiT_Create(s, &i) ,(2)释放二叉树结构 树结构是一种动态数据结构，它由一个个结点逐渐创建链接而成。当树结构处理完成后，有必要释放其所有结点。 遍历算法的本质是访问每个结点且每个结点只访问一次。这和释放每个结点的要求非常相似，以下是利用后序遍历算法的结构，释放二叉树中所有结点的存储结构的算法。 算法6.9 释放二叉树中所有结点的存储结构的算法。 void BiT_Free(BiTNode *root) if(root!=NULL) BiT_Free(root-lchild); BiT_Free(root-rchild); free(root); /* 将访问语句改为释放语句 */ 需要注意的是，必须采用后序遍历算法的结构，而不能是前序或中序的遍历结构。因为只有在释放完左右子树之，才允许释放根结点，否则，程序的运行是不安全的。,(3)统计结点的个数 统计结点个数是树结构的一个简单应用算法，同样可以借鉴遍历算法的结构。只是将访问结点的语句改为加法运算而已。 算法6.10 统计二叉树结点个数算法。 int BiT_Count(BiTNode *root) int left,right; if(root=NULL) return(0); left= BiT_Count(root-lchild); /* 计算左子树的结点数 */ right=BiT_Count(root-rchild); /* 计算右子树的结点数 */ return(left+right+1); /* 计算结点总数 */ ,算法6.11 统计二叉树树叶结点的个数算法。 统计结点个数算法的一个变形是：统计树叶结点的个数。这只需要在做加法运算前，先判断结点的度是否为0。 int BiT_LeafCount(BiTNode *root) int left,right; if(root=NULL) return(0); if(root-lchild=NULL ,(4)求二叉树的深度 空二叉树的深度为0，否则它的深度等于其根的左右子树的深度的最大值加1。显然这是一个递归定义，最简捷的实现方式是采用递归算法。同样，在此借鉴后序遍历算法的结构，在遍历根的左右子树时，分别计算其深度，于是二叉树的深度自然就求出了。 算法6.12 计算二叉树的深度算法。 int BiT_Depth(BiTNODE *root) int left,right; if(root=NULL) return(0); left = BiT_Depth(root-lchild); /* 计算左子树深度 */ right= BiT_Depth(root-rchild); /* 计算右子树深度 */ return(max(left,right)+1); ,(5)交换树中每个结点的左右子树 若仅仅交换某个结点的左右子树，那就太简单了。要求对每个结点的左右子树都进行交换，这是加强对遍历算法理解、应用的一个常用练习。以下采用后序遍历的算法结，交换每个结点的左右子树。 算法6.13 交换二叉树每个结点的左右子树算法。 void BiT_Exchange(BiTNode *root) BiTNode *p; if(root=NULL) return; BiT_Exchange(root-lchild); /* 对左子树中的每个结点交换 */ BiT_Exchange(root-rchild); /* 对右子树中的每个结点交换 */ /* 交换结点的左右孩子 */ p=root-lchild; root-lchild=root-rchild; root-rchild=p; ,(6)根据前序序列和中序序列构造二叉树结构 我们已经知道二叉树结构和它的某个遍历序列不存在一一对应的关系，但若已知一个二叉树的前序序列和中序序列，却一定可以唯一确定一个二叉树的结构。 算法思路如下： (a)因为前序序列的首元素为根元素，所以可以立即确定根结点。 (b)在中序序列中定位根结点的位置，必然将中序序列分为根元素和左、右子树三个部分。 (c)由于已知左、右子树的元素个数，也自然可以将前序序列分为根元素和左、右子树三个部分。 (d)建树问题被细分为建左右子树的同类小问题。在问题逐步分解细化过程中，若中序序列和前序序列都为空序列，则表明待建子树为空。,示例：设pre0到pre6为前序序列abdecgh， mid0到mid6为中序序列dbeagch。其建树的步骤如下。,确定根结点的数据为pre0，即字符a。 (2)在中序序列中定位字符a的位置，即下标为3，可以确定mid0到mid2为左子树的中序序列；mid4到mid6为右子树的中序序列。 (3)根据中序序列与前序序列的对应关系，可知pre1到pre3为左子树的前序序列；pre4到pre6为右子树的前序序列。 (4)根据前序序列pre1到pre3，中序序列mid0到mid2，构造左子树；根据前序序列pre4到pre6，中序序列mid4到mid6，构造右子树。,在程序中值得注意的是，在这种递归算法策略中，大小问题的描述，即函数的参数形式，必须具有完全相同的形式。 算法6.14 由前序序列和中序序列构造二叉树结构算法。 /* pre中存储前序序列，mid中存储中序序列，n为序列中元素的个数 */ /* pre_i为前序序列在pre中的起始位置 */ /* mid_i为前序序列在mid中的起始位置 */ BiTNode *premid(char pre,char mid,int pre_i,int mid_i,int n) int i=0; BiTNode *root; if(n=0) return(NULL); /* 最终解决方案：空序列建空树 */ /* 在中序序列中定位根元素的位置 */,while(idata=prepre_i; /* 建左子树 */ root-lchild=premid(pre,mid, pre_i+1, mid_i, i); /* 建右子树 */ root-rchild=premid(pre,mid, pre_i+i+1,mid_i+i+1,n-i-1) ; return(root); main() char pre=abdecgh, mid=dbeagch; BiTNode *root; root=premid(pre, mid, 0,0,7); ,6.4 树和森林,6.4.1 树的存储结构 在大量的应用中，可以使用多种形式的存储结构来表示树。在这里介绍三种表示树的方法，在具体应用中可以采用这三种表示方法，也可以定义其它存储结构，以满足应用的需求。采用某种结构的理由来自实践的需要，即使数据完全一样，因具体应用不同，所以结构就可能不同。,(1)双亲表示法 采用一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在该连续空间中位置。若该连续空间用数组表示，则每一个结点的指示器值是其双亲结点在数组中下标。用C语言定义的树的双亲表示存储结构如下： struct node int data; int parent; /* 双亲结点的下标 */ treeMAX;,例如，图6.10所示为一棵树及其双亲表示的存储结构，其中，tree0.parent存放树中结点数。,图6.10 树的双亲表示法,在这种存储结构中，利用每一个结点的双亲指示域，很容易找到每一个结点的双亲，同样找结点的祖先结点也非常便利。但要找某个结点的孩子或子孙结点，需遍历整个数组.,(2)孩子表示法 将树中每个结点的孩子结点用一个单链表(孩链表)表示，那么，一棵树有n个结点就有n个孩链表(度为0的结点，所对应的孩链表为空表)。这n个孩链表的头指针又构成一个线性表，用一个指针数组存储该线性表，这就构成了树的孩子表示法的存储结构。 如图6.11(a)所示为图6.10中树的孩子表示法的存储结构，在这种存储结构中，找一个结点的孩子十分方便。例如，要找结点B的孩子，只要遍历结点B的孩链表，就可以找到该结点的所有孩子。但要找一个结点的双亲就不方便，需要遍历整个结构。例如，要找结点D的双亲结点，就要找到某个结点的孩链表中有结点D，该结点就是D的双亲，在这里结点B的孩链表中包含了D结点的位置，所以，B是D的双亲结点。,图6.11 图6.10中树的孩子表示法,为了便于查找结点的双亲，将树的双亲表示法和孩子表示法结合起来，就有了树的双亲孩子表示法，如图6.11(b)所示就是树的双亲孩子表示法存储结构示意图。 这种结构用C语言描述如下： struct node int pos; /* 结点在数组中下标 */ struct node *link; ； struct t_node char data; int parent; struct node *first_link; /* 孩子链表的头指针 */ treeMAX; 其中，tree0.parent用来存放树中结点数。,(3)孩子兄弟表示法 又称为二叉树表示法，也称为二叉链表表示法，即：以二叉链表作为树的存储结构。链表中结点的两个指针域分别指向该结点的第一个孩子结点和右边下一个兄弟结点，分别命名为son域和brother域。 struct node int data; struct node *son; /* 第1个孩子 */ struct node *brother; /* 下一个兄弟 */ ；,图6.12 图6.10中树的二叉链表表示法,图6.12所示为图6.10中树的孩子兄弟链表的存储结构。在这种存储结构中，找一个结点的孩子十分方便。,6.4.2 树与二叉树的转换 由于二叉树和树都可以用二叉链表存储，因此，可从树的孩子兄弟链表中，导出树与二叉树之间的一个对应关系。也就是说，可以找到唯一的二叉树与之对应。从物理(存储)结构来看，它们的二叉链表是相同的。只是解释不同而已。 例如，图6.12所示为图6.10中树的孩子兄弟链表的存储结构，表中结点的两个指针域son域和brother域解释为：指向该结点的第一个孩子结点和下一个兄弟结点。但也可以看成是将图6.10中树转换成的二叉树的存储结构。这时，表中结点的两个指针域son域和brother域就应解释为：指向该结点左孩子和右孩子。 所以，树与二叉树之间转换和树的二叉链表表示法所用的方法相同。,6.4.3 森林与二叉树的转换 (1)森林转换为二叉树 从树的二叉链表表示的定义可知，一棵与树对应的二叉树，其右子树必为空。所以，只要将森林中所有树的根结点视为兄弟，即将各个树转换为二叉树；再按森林中树的次序，依次将后一个树作为前一棵树的右子树，并将第一棵树的根作为目标二叉树树根，就可以将一个森林转换成二叉树。 转换规则定义： 若F=T1,T2,Tn是森林，可按以下规则转成一棵二叉树B(F)=root,LB,RB： (1)若F为空，即n=0，则B(F)为空树。 (2)若F非空，即n0，则B(F)的根是T1的根，其左子树为LB是从T1根结点的子树森林F1=T11,T12,T1m转换而成的二叉树；其右子树RB是从除T1外的森林F=(T2,Tn)转换而成的二叉树。,图6.13 森林与二叉树的对应关系示例,(2)二叉树还原为森林 转换规则定义： 若B=(root,LB,RB)是一棵二叉树，可按以下规则转换为森林F=T1,T2,Tn： (1)若B为空，则B(F)为空树。 (2)若B非空，则F中第一棵树T1的根是二叉树的根；T1中根结点的子森林F1是由B的左子树LB转换而成的森林；F中除T1之外其余树组成的森林F=T2,T3,Tm是由B(F)的右子树RB转换而成。 森林与目标二叉树之间有一一对应的关系。所以，对森林的操作也可以在二叉树的结构上进行。,回 顾,树和森林 一、树的存储结构,1. 双亲表示法 2. 孩子表示法 3. 孩子兄弟表示法,二、树和二叉树的转换 三、森林和二叉树的转换 四、二叉树转换为树或森林,6.5 树的应用,6.5.1 二叉排序树 6.5.2 哈夫曼树,6.5.1 二叉排序树 1、二叉排序树的定义 二叉排序树，是一种很有用的、特殊的二叉树，它的每一个结点数据中都有一个关键值，并有如下性质：对于每个结点，如果其左子树非空，则左子树的所有结点的关键值都小于该结点的关键值；如果其右子树非空，则右子树的所有结点的关键值都大于该结点的关键值。,如图6.14所示的二叉树，就是一棵二叉排序树。二叉排序树有查找效率高，增添、删除方便的特点，而且对二叉排序树进行中序遍历，将得到一个按结点关键值递增有序的中序线性序列。所以，它被广泛地用来作为动态查找的数据结构。,二叉排序树的存储结构也采用二叉链表，存储结构如下：,举例：用二叉排序树作为目录树，把一个记录的关键码和记录的地址作为二叉排序树的结点，按关键码值建成二叉排序树。这样，既能像有序表那样进行高效查找，又能像链表那样灵活删除，而不需要移动其他结点。如要得到按关键码值的排序结果，还可以对其进行中序遍历。,struct bstnode int data; struct bstnode *lch,*rch; ; typedef struct bstnode BSTNode;,2、二叉排序树的查找 在二叉排序树中进行查找，将要查找的值从树根开始比较，若与根的关键值相等，则成功；若比根的关键值小，则到左子树找；若比根的关键值大，则到右子树找；直到查找成功或查找子树为空(失败)。若成功，则返回查找到结点的地址；若失败，则返回空指针。,查找的递归算法如下： 算法6.15 二叉排序树的查找递归算法。 BSTNode *search(BSTNode *root, int x) if(root=NULL) return(NULL); while(root) if(x=root-elem.key) return(root); if(xelem.key) root=root-lch; else root=root-rch; return(NULL); ,3、二叉排序树的插入和生成 插入是一个动态的查找过程。首先在树中查找x，若不存在则插入。从空树开始，插入一系列结点，就是二叉排序树的生成过程。例如，给定一组关键值序列为45,24,53, 45,12,24,90，则生成二叉排序树的过程如图所示。,45,24,53, 45,12,24,90,图6.15 二叉排序树的生成过程,x,再插入50,将要插入的关键值存放在数组aMAX中，MAX为要插入的关键值个数。 (a) 二叉排序树的插入算法 算法6.16 二叉排序树中插入结点的递归算法 BSTNode *BSTNode_Insert(BSTNode *root, BSTNode *newp) /* 在根指针为root的二叉排序树中插入结点*newp */ if(root=NULL) return (newp); if(newp-datadata) root-lch=BSTNode_Insert(root-lch, newp); else root-rch=BSTNode_Insert(root-rch, newp); return (root); ,算法6.17 二叉排序树中插入结点的非递归算法。 BSTNode *BSTNode_Insert(BSTNode *root, BSTNode *newp) /*在根指针为root的二叉排序树中插入关键值为ai的结点*/ BSTNode *p=root; if(root=NULL) return(newp); while(1) if(newp-data data) if(p-lch) p=p-lch; else p-lch=newp; return(root); else if(p-rch) p=p-rch; else p-rch=newp; return(root); return(root); ,(b) 建立二叉排序树 算法6.18 利用插入算法，建立二叉排序树。 BSTNode * BSTNode_Create(BSTNode *root, int a,int n) /* 依据a中元素序列，建立二叉排序树 */ BSTNode *p,*head=NULL; int i; for(i=0; idata=ai; p-lch=p-rch=NULL; head=BSTNode_Insert(head,p); /* 调用插入函数 */ return(head); ,3、二叉排序树的删除 在二叉排序树中删除结点，首先要进行查找，若查找成功则删除该结点，但删除之后，不能破坏原二叉排序树中结点的关系，即删除后二叉树的中序序列仍然是按关键值递增有序。 删除算法可分下面三种情况讨论： （1）被删除结点是叶子结点 （2）被删除结点是单分支结点 （3）被删除结点是双分支结点 (假定，p指向要删除结点，f指向p的双亲结点，且不失一般性，设p是f的右孩子),(1) 被删除结点是叶子结点 若*p结点为叶子结点，只需直接删除。 即：将双亲结点指向它的指针，设置为空指针(f-rch=NULL)。,(2)被删除结点是单分支结点 若*p结点为单分支结点，只需用它唯一子树的根去继承它的位置。 即：将双亲结点原指向它的指针，设置为指向它的左孩子或右孩子(若只有左子树，则f-rch=p-lch；若只有右子树，则f-rch=p-rch),(3)被删除结点是双分支结点 若*p结点为双分支结点，为保证删除该结点后，该树的中序序列任然是按关键值递增有序。 所以有如下两种方法。,方法1：用左子树中序遍历的最后一个结点(左子树的最右结点)替换*p。 查找到*p的左子树的右链为空的结点*s；然后，用*s的数据替换*p的数据；最后，删除*s结点。*s是其双亲结点的右孩子，并且s-rch为NULL。若s-lch也为空，则置*s双亲的右指针为NULL，删除*s；若s-lch不为空，则置*s双亲的右指针为s-lch，删除*s。,左子树最右结点,*s双亲的右指针改为s-lch,s-lch,方法2：用右子树中序遍历的第一个结点(右子树的最左结点)替换*p。 首先，沿*p的右子树的左链，查找到左指针域为空的结点*s；然后，用*s的数据替换*p的数据；最后，删除*s结点。,算法6.19 二叉排序树中删除结点的算法(x删除结点的关键值) BSTNode * BSTNode_del(BSTNode *root,int x) BSTNode *p,*f,*s_f,*s; /* p要删除结点,f为p的双亲,s为p的左子树的最右边结点,s_f为s双亲 */ if(root=NULL) return; /* 二叉排序树为空树 */ f=NULL; p=root; while(p!=NULL /* 查找结束，进行节点删除，下一页*/,/* 查找失败，无找到要删除的结点 */ if(p=NULL) return(root); /* 删除*p的第一种情形：*p为叶子 */ if(p-lch=NULL ,/* 删除*p的第二种情形：*p为单分支结点 */ if(p-lch=NULL) /* 没有左子树 */ if(f=NULL) root=p-rch;free(p);return(root); if(f-lch=p) f-lch=p-rch; /* *p是双亲的左孩子 */ else f-rch=p-rch; /* *p是双亲的右孩子 */ free(p); return(root); if(p-rch=NULL) /* 没有右子树 */ if(f=NULL) root=p-lch;free(p);return(root); if(f-lch=p) f-lch=p-lch; else f-rch=p-lch; free(p); return(root); ,/* 删除*p的第三种情形：*p为双分支结点 */ s_f=p; s=p-lch; /* 找*p左子树的最右结点*s,*s_f是*s的父结点 */ while(s-rch!=NULL) /* 循环，直到s右指针为空 */ s_f=s; s=s-rch; /* s以替代p，然后删除s结点 */ p-data=s-data; if(s-lch=NULL) /* *s是叶子 */ s_f-rch=NULL; /*置*s双亲结点的右指针为空*/ else /* *s有左子树 */ s_f-rch=s-lch; /*置*s双亲的右指针为*s的左孩子*/ free(s); return(root); ,6.5.2 哈夫曼树以及应用 哈夫曼树，又称为最优树，是一类带权路径长度最短的树，有着广泛的应用。 (a)基本术语 路径：从一个结点到另一个结点之间的若干分支。 路径长度：路径的分支数。 结点的路径长度：从根到该结点的路径长度。 树的路径长度：树中所有结点的路径长度之和。一般记作PL。 图6.17所示为计算树的路径长度的示例。在结点数相同的条件下，路径最短的二叉树为完全二叉树。 若将上述概念推广到一般情况，考虑带有权值的结点。 结点的带权路径：从根到带权结点之间的路径长度与结点上的权值乘积。,树的带权路径：树中所有带权结点的带权路径长度之和(无权值结点的路径不考虑)。一般记作WPL，即,其中，wk是编号为k结点的权值；lk是根到编号为k结点的路径；n为树中带权结点数。,最优二叉树(哈夫曼树)：假设有n个权值w1,w2,wn，是构造一棵有n个叶子结点的严格二叉树(只有度为0和度为2的结点)，