数据结构树和二叉树--课件

数据结构 第6章 树和二叉树第第6 6章章 树和二叉树树和二叉树学习目的与要求：学习目的与要求：1.熟练掌握二叉树的结构特性，掌握相应的证明方法；熟练掌握二叉树的结构特性，掌握相应的证明方法；2.熟悉二叉树的各种存储结构的特点及适用范围；熟悉二叉树的各种存储结构的特点及适用范围；3.熟练掌握二叉树各种遍历策略的递归和非递归算法，而且能灵活熟练掌握二叉树各种遍历策略的递归和非递归算法，而且能灵活运用遍历算法实现二叉树的其它操作；运用遍历算法实现二叉树的其它操作；4.熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。点的前驱和后继的方法。5.熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。换方法。6.了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。1ppt课件数据结构 第6章 树和二叉树基本内容基本内容树的定义和基本术语树的定义和基本术语二叉树的定义及性质二叉树的定义及性质二叉树的存储结构二叉树的存储结构 遍历二叉树遍历二叉树线索二叉树线索二叉树哈夫曼树及其应用哈夫曼树及其应用树和森林树和森林本章小结本章小结2ppt课件数据结构 第6章 树和二叉树树的定义和基本术语树的定义和基本术语1、树的定义、树的定义 树是一种常用的非线性数据结构。它是树是一种常用的非线性数据结构。它是n(n=0)个结点的有个结点的有限集。限集。n=0时，称为时，称为空树空树。在任意一棵非空树中：。在任意一棵非空树中：1）有且仅有）有且仅有一个特定的称为一个特定的称为根根（Root)的结点；的结点；2）当）当n1时，其余结点分时，其余结点分为为m(m0)个个互不相交互不相交的有限集的有限集T1,T2,Tm，其中每一个集合，其中每一个集合本身又是一棵树，并且称为本身又是一棵树，并且称为根的子树根的子树。2、树的特点、树的特点u有且只有一个称作根的结点；有且只有一个称作根的结点；u除根结点以外，其余结点有且只有一个双亲结点。除根结点以外，其余结点有且只有一个双亲结点。3ppt课件数据结构 第6章 树和二叉树3、树的示例、树的示例ABCDEFGHIJKLM有子树的树有子树的树A只有根结点的树只有根结点的树子树子树4ppt课件数据结构 第6章 树和二叉树4、树的基本术语、树的基本术语ABCDEF G HIJKLM结点结点(node)表示树中的元素，包括数据项及若干指向其子树的分支。表示树中的元素，包括数据项及若干指向其子树的分支。结点的度结点的度(degree)结点拥有的子树数。结点拥有的子树数。叶子叶子(leaf)度为度为0的结点，又称终端结点。的结点，又称终端结点。孩子孩子(child)结点子树的根称为该结点的孩子，该结点称为其孩子结点子树的根称为该结点的孩子，该结点称为其孩子结点的双亲结点的双亲(parents)兄弟兄弟(sibling)同一双亲的孩子。同一双亲的孩子。树的度树的度 一棵树中各结点的度的最大值。一棵树中各结点的度的最大值。结点的层次结点的层次(level)从根结点算起，根为第一层，它的孩子为第二从根结点算起，根为第一层，它的孩子为第二层层深度深度(depth)树中结点的最大层次数。树中结点的最大层次数。森林森林(forest)m(m0)棵互不相交的树的集合。棵互不相交的树的集合。另：另：祖先、子孙、堂兄弟、非终端结点、内部结点、祖先、子孙、堂兄弟、非终端结点、内部结点、无序树、有序树等无序树、有序树等5ppt课件数据结构 第6章 树和二叉树5、树的基本运算、树的基本运算(1)InitTree(&T):构造一棵空树构造一棵空树(2)TreeDepth(T):求树的深度求树的深度(3)Root(T):求树根求树根(4)Parent(T,cur_e):求树求树T中结点中结点cur_e的双亲的双亲(5)LeftChild(T,cur_e):若若cur_e是是T的非叶子结点，则返回它的最左的非叶子结点，则返回它的最左孩子，否则返回孩子，否则返回“空空”。(6)RightSibling(T,cur_e):若若cur_e有右兄弟，则返回它的右兄弟，有右兄弟，则返回它的右兄弟，否则函数值为否则函数值为“空空”。(7)InsertChild(&T,&p,i,c):插入插入c为为T中中p指结点的第指结点的第i棵子树。棵子树。(8)DeleteChild(&T,&p,i):删除删除T中中p所指结点的第所指结点的第i棵子树。棵子树。(9)TraverseTree(T,visit():按某种次序对按某种次序对T的每个结点调用函数的每个结点调用函数visit()一次且至多一次。一旦一次且至多一次。一旦visit()失败，则操作失败。失败，则操作失败。6ppt课件数据结构 第6章 树和二叉树6、树的表示法、树的表示法广义表表示法广义表表示法(a(b(d,e(i,j),f),c(g,h)7ppt课件数据结构 第6章 树和二叉树基本内容基本内容树的定义和基本术语树的定义和基本术语二叉树的定义及性质二叉树的定义及性质二叉树的存储结构二叉树的存储结构 遍历二叉树遍历二叉树线索二叉树线索二叉树哈夫曼树及其应用哈夫曼树及其应用树和森林树和森林本章小结本章小结8ppt课件数据结构 第6章 树和二叉树二叉树的定义和性质二叉树的定义和性质二叉树二叉树(binary tree):度不超过度不超过2的的有序有序树，是另一种树型结构。树，是另一种树型结构。二叉树的五种基本形态：二叉树的五种基本形态：(a)空二叉树空二叉树A(b)仅有根结点仅有根结点的二叉树的二叉树(c)右子树为右子树为空的二叉树空的二叉树A(d)左、右子树均左、右子树均非空的二叉树非空的二叉树A(e)左子树为左子树为空的二叉树空的二叉树A1、二叉树的定义、二叉树的定义特点：特点：每个结点至多只有两棵子树；每个结点至多只有两棵子树；二叉树的子树有左右之分，其次序不能任意颠倒。二叉树的子树有左右之分，其次序不能任意颠倒。9ppt课件数据结构 第6章 树和二叉树2、二叉树的基本运算、二叉树的基本运算(1)InitBiTree(&T):构造一棵空二叉树；构造一棵空二叉树；(2)BiTreeDepth(T):求二叉树的深度；求二叉树的深度；(3)BiTreeEmpty(T):若若T为空二叉树，则返回为空二叉树，则返回TRUE，否则，否则FALSE；(4)Parent(T,e):若若e是是T的非根结点，则返回它的的双亲，否则返回的非根结点，则返回它的的双亲，否则返回“空空”；(5)LeftChild(T,e):返回返回e的左孩子，若的左孩子，若e无左孩子，则返回无左孩子，则返回“空空”；(6)RightChild(T,cur_e):返回返回e的右孩子，若的右孩子，若e无右孩子，则返回无右孩子，则返回“空空”；(7)InsertChild(&T,&p,LR,c):插入插入c为为T中中p指结点的由指结点的由LR的值确定的左（右）子树；的值确定的左（右）子树；(8)DeleteChild(&T,&p,LR):删除删除T中中p所指结点的由所指结点的由LR的值确定的左（右）子树；的值确定的左（右）子树；(9)PreOrderTraverse(T):先序遍历二叉树先序遍历二叉树T；(10)InOrderTraverse(T):中序遍历二叉树中序遍历二叉树T；(11)PostOrderTraverse(T):后序遍历二叉树后序遍历二叉树T；(12)LevelOrderTraverse(T):层次遍历二叉树层次遍历二叉树T。10ppt课件数据结构 第6章 树和二叉树3、二叉树的性质、二叉树的性质:性质性质1：在二叉树的第在二叉树的第i层上至多有层上至多有2i-1个结点个结点(i1)。证明证明性质性质2：深度为深度为k的二叉树至多有的二叉树至多有2k-1个结点个结点(k1)。证明证明性质性质3：对任何一棵二叉树对任何一棵二叉树T，如果其终端结点数为，如果其终端结点数为n0，度为，度为2的结点数为的结点数为n2，则，则n0=n2+1。证明证明性质性质4：具有具有n个结点的个结点的完全二叉树完全二叉树的深度为的深度为 。证明证明性质性质5：如果对一棵有如果对一棵有n个结点的完全二叉树的结点按层序编号，个结点的完全二叉树的结点按层序编号，则对任一结点则对任一结点i(1i n)，有：，有：(1)如果如果i=1，则结点则结点i是二叉树的根，无双亲；如果是二叉树的根，无双亲；如果i1，则其双亲是则其双亲是 i/2。(2)如果如果2in，则结点则结点i无左孩子；否则其左孩子是无左孩子；否则其左孩子是2i。(3)如果如果2i+1n，则结点则结点i无右孩子；否则其右孩子是无右孩子；否则其右孩子是2i+1。证明证明11ppt课件数据结构 第6章 树和二叉树性质性质1证明证明：用归纳法证明之：用归纳法证明之 i=1时，只有一个根结点，显然，时，只有一个根结点，显然，2i-1=20=1 是对的。是对的。假设对所有假设对所有j(1ji)命题成立，即第命题成立，即第j层上至多有层上至多有2j-1个结点，个结点，那么，第那么，第i-1层至多有层至多有2i-2个结点；又二叉树每个结点的度至多为个结点；又二叉树每个结点的度至多为2，第第i层上最大结点数是第层上最大结点数是第i-1层的层的2倍，即倍，即22i-2=2i-1。故命题得证。故命题得证。性质性质2证明证明：由性质由性质1，可得深度为，可得深度为k 的二叉树最大结点数是：的二叉树最大结点数是：12ppt课件数据结构 第6章 树和二叉树性质性质3证明证明：设设n1为二叉树为二叉树T中度为中度为1的结点数，因为二叉树中所有结点的度的结点数，因为二叉树中所有结点的度均小于或等于均小于或等于2，所以其结点总数所以其结点总数为为 n=n0+n1+n2 又因为在二叉树中，除根结点外，其余结点都只有一又因为在二叉树中，除根结点外，其余结点都只有一个个分支进入分支进入。设设B为为分支总数分支总数，则，则n=B+1。而分而分支是由度为支是由度为1和度为和度为2的结点射出，的结点射出，所以所以B=n1+2n2，于是，于是，n=B+1=n1+2n2+1 由由 和和 得：得：n0=n2+112356713ppt课件数据结构 第6章 树和二叉树两种特殊形态的二叉树两种特殊形态的二叉树满二叉树：满二叉树：一棵深度为一棵深度为k且有且有2k-1个结点的二叉树个结点的二叉树完全二叉树：完全二叉树：深度为深度为k有有n个结点且个结点且每个结点都与深度为每个结点都与深度为k的满二叉树中编号的满二叉树中编号从从1至至n的结点一一对应的二叉树的结点一一对应的二叉树特点：特点：1)叶子结点只可能在最下面两层上叶子结点只可能在最下面两层上;2)任意结点的左右分支下的子孙最大任意结点的左右分支下的子孙最大层次层次0l左左-l右右1;3)深度为深度为k的完全二叉树，第的完全二叉树，第i(1 i k-1)层上结点数等于层上结点数等于2i-114ppt课件数据结构 第6章 树和二叉树123114589121367101415123114589126710123456712345615ppt课件数据结构 第6章 树和二叉树性质性质4证明：证明：假设完全二叉树的深度为假设完全二叉树的深度为k，根据性质，根据性质2和完全二叉树的定义有和完全二叉树的定义有 2k-1-1n2k-1 或或 2k-1n2k 于是于是 k-1 log2nn，此时，此时结点结点i无左孩子；结点无左孩子；结点i的右孩子也只能是结点的右孩子也只能是结点3，若，若3n，此时结点，此时结点i无无右孩子。右孩子。对于对于i1可以分成两种情况：可以分成两种情况：设第设第j层的第一个结点的编号为层的第一个结点的编号为i（由性质（由性质2可知可知i=2j-1），则其左孩子），则其左孩子必为必为j+1的第一个结点，其编号为的第一个结点，其编号为2j=2(2j-1)=2i，若，若2in，则无左孩子；，则无左孩子；其右孩子必为第其右孩子必为第j+1层的第二个结点，其编号为层的第二个结点，其编号为2i+1，若，若2i+1n，则无，则无右孩子。右孩子。17ppt课件数据结构 第6章 树和二叉树假设第假设第j层上某个结点的编号为层上某个结点的编号为i（2j-1i2j-1），且），且2i+1data);/访问根结点访问根结点 PreOrderTraverse(bt-lchild);PreOrderTraverse(bt-rchild);/PreOrderTraverse27ppt课件数据结构 第6章 树和二叉树先序遍历的调用过程：先序遍历的调用过程：ADBCD L RAD L RBD L RDD L RC先序遍历序列：先序遍历序列：A B D C28ppt课件数据结构 第6章 树和二叉树先序遍历二叉树的非递归算法（方法一）先序遍历二叉树的非递归算法（方法一）:void PreOrderTraverse(BiTree bt)/二叉树二叉树bt采用二叉链表存储，对采用二叉链表存储，对bt进行先序遍历进行先序遍历 if(bt)InitStack(S);Push(S,bt);/根指针进栈根指针进栈 while(!StackEmpty(S)while(GetTop(S,p)&p)printf(p-data);Push(S,p-lchild);/向左一直走到尽头向左一直走到尽头 Pop(S,p);/空指针退栈空指针退栈 if(!StackEmpty(S)Pop(S,p);Push(S,p-rchild);/while /if/PreOrderTraverse29ppt课件数据结构 第6章 树和二叉树先序遍历二叉树的非递归算法（方法二）先序遍历二叉树的非递归算法（方法二）:void PreOrderTraverse(BiTree bt)/二叉树二叉树bt采用二叉链表存储，对采用二叉链表存储，对bt进行先序遍历进行先序遍历 if(bt)InitStack(S);p=bt;Push(S,NULL);while(p)printf(p-data);if(p-rchild)Push(S,p-rchild);if(p-lchild)p=p-lchild;else Pop(S,p);/while /if/PreOrderTraverse30ppt课件数据结构 第6章 树和二叉树先序遍历二叉树的非递归算法（方法三）先序遍历二叉树的非递归算法（方法三）:void PreOrderTraverse(BiTree bt)/二叉树二叉树bt采用二叉链表存储，对采用二叉链表存储，对bt进行先序遍历进行先序遍历 if(bt)InitStack(S);p=bt;while(p|!StackEmpty(S)while(p)printf(p-data);if(p-rchild)Push(S,p-rchild);p=p-lchild;if(!StackEmpty(S)Pop(S,p);/while /if/PreOrderTraverse31ppt课件数据结构 第6章 树和二叉树2、中序遍历二叉树、中序遍历二叉树中序遍历二叉树的操作定义中序遍历二叉树的操作定义:若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则1)中序遍历左子树中序遍历左子树(L)；2)访问根结点访问根结点(D)；3)中序遍历右子树中序遍历右子树(R)中序遍历二叉树的递归算法中序遍历二叉树的递归算法:void InOrderTraverse(BiTree bt)/二叉树二叉树bt采用二叉链表存储，对采用二叉链表存储，对bt进行中序遍历进行中序遍历 if(bt)InOrderTraverse(bt-lchild);visit(bt-data);/访问根结点访问根结点 InOrderTraverse(bt-rchild);/InOrderTraverse32ppt课件数据结构 第6章 树和二叉树中序遍历的调用过程：中序遍历的调用过程：L D RL D RBL D RDAL D RC中序遍历序列：中序遍历序列：B D A CADBC33ppt课件数据结构 第6章 树和二叉树中序遍历二叉树的非递归算法（方法一）中序遍历二叉树的非递归算法（方法一）:void InOrderTraverse(BiTree bt)/二叉树二叉树bt采用二叉链表存储，对采用二叉链表存储，对bt进行中序遍历进行中序遍历 if(bt)InitStack(S);Push(S,bt);/根指针进栈根指针进栈 while(!StackEmpty(S)while(GetTop(S,p)&p)Push(S,p-lchild);/向左一直走到尽头向左一直走到尽头 Pop(S,p);/空指针退栈空指针退栈 if(!StackEmpty(S)Pop(S,p);printf(p-data);Push(S,p-rchild);/while /if/InOrderTraverse34ppt课件数据结构 第6章 树和二叉树中序遍历二叉树的非递归算法（方法二）中序遍历二叉树的非递归算法（方法二）:void InOrderTraverse(BiTree bt)/二叉树二叉树bt采用二叉链表存储，对采用二叉链表存储，对bt进行先序遍历进行先序遍历 if(bt)InitStack(S);p=bt;while(p|!StackEmpty(S)if(p)Push(S,p);p=p-lchild;else Pop(S,p);printf(p-data);p=p-rchild;/if/InOrderTraverse此处还可写成：此处还可写成：while(p)Push(S,p);p=p-lchild;if(!StackEmpty(S)Pop(S,p);printf(p-data);p=p-rchild;35ppt课件数据结构 第6章 树和二叉树3、后序遍历二叉树、后序遍历二叉树后序遍历二叉树的操作定义后序遍历二叉树的操作定义:若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则1)后序遍历左子树后序遍历左子树(L)；2)后序遍历右子树后序遍历右子树(R)；3)访问根结点访问根结点(D)后序遍历二叉树的递归算法后序遍历二叉树的递归算法:void PostOrderTraverse(BiTree bt)/二叉树二叉树bt采用二叉链表存储，对采用二叉链表存储，对bt进行后序遍历进行后序遍历 if(bt)PostOrderTraverse(bt-lchild);PostOrderTraverse(bt-rchild);visit(bt-data);/访问根结点访问根结点 /PostOrderTraverse36ppt课件数据结构 第6章 树和二叉树后序遍历的调用过程：后序遍历的调用过程：ADBC L R DL R DL R DDBL R DCA后序遍历序列：后序遍历序列：D B C A37ppt课件数据结构 第6章 树和二叉树后序遍历二叉树的非递归算法（方法一）后序遍历二叉树的非递归算法（方法一）:void PostOrderTraverse(BiTree bt)/二叉树二叉树bt采用二叉链表存储，对采用二叉链表存储，对bt进行后序遍历进行后序遍历 InitStack(S);Push(S,bt);/根指针进栈根指针进栈 while(!StackEmpty(S)while(GetTop(S,p)&p)Push(S,p-lchild);/向左一直走到尽头向左一直走到尽头 Pop(S,p);/空指针退栈空指针退栈 if(!StackEmpty(S)GetTop(S,p);if(p-rchild)Push(S,p-rchild);else Pop(S,p);printf(p-data);while(!StackEmpty(S)&GetTop(S,q)&q-rchild=p)Pop(S,p);printf(p-data);if(!StackEmpty(S)GetTop(S,p);Push(S,p-rchild);/PostOrderTraverse38ppt课件数据结构 第6章 树和二叉树后序遍历二叉树的非递归算法（方法二）后序遍历二叉树的非递归算法（方法二）:void PostOrderTraverse(BiTree bt)/二叉树二叉树bt采用二叉链表存储，对采用二叉链表存储，对bt进行后序遍历进行后序遍历 InitStack(S);Push(S,NULL);p=bt;q=NULL;while(p|!StackEmpty(S)if(p&p!=q)Push(S,p);p=p-lchild;else Pop(S,p);if(!StackEmpty(S)if(p-rchild&p-rchild!=q)Push(S,p);p=p-rchild;else printf(p-data);q=p;/PostOrderTraverse39ppt课件数据结构 第6章 树和二叉树后序遍历二叉树的非递归算法（方法三）后序遍历二叉树的非递归算法（方法三）:void PostOrderTraverse(BiTree bt)/二叉树二叉树bt采用二叉链表存储，对采用二叉链表存储，对bt进行后序遍历进行后序遍历 InitStack(S);p=bt;flag=1;do while(p)Push(S,p);p=p-lchild;q=NULL;flag=1;while(!StackEmpty(S)&flag)GetTop(S,p);if(p-rchild=q)printf(p-data);Pop(S,p);q=p;else p=p-rchild;flag=0;while(!StackEmpty(S);/PostOrderTraverse40ppt课件数据结构 第6章 树和二叉树 通过上述介绍可以看到：三种遍历算法递归执行的通过上述介绍可以看到：三种遍历算法递归执行的(指针指针)路线相同，只是路线相同，只是访问访问根结点的时机不同。如下图所示：根结点的时机不同。如下图所示：-*abc-*cab-*abcabc*-abc-*41ppt课件数据结构 第6章 树和二叉树4、层次遍历二叉树、层次遍历二叉树void LevelOrderTraverse(BiTree bt)/二叉树二叉树bt采用二叉链表存储，对采用二叉链表存储，对bt进行层次遍历进行层次遍历 if(bt)InitQueue(Q);EnQueue(Q,bt);while(!QueueEmpty(Q)DeQueue(Q,p);printf(p-data);if(p-lchild)EnQueue(Q,p-lchild);if(p-rchild)EnQueue(Q,p-rchild);/LevelOrderTraverse42ppt课件数据结构 第6章 树和二叉树5、按某种遍历序列建立二叉树的二叉链表、按某种遍历序列建立二叉树的二叉链表 例如按先序遍历序列建立二叉树的二叉链表，假设输入的字符顺例如按先序遍历序列建立二叉树的二叉链表，假设输入的字符顺序为：序为：ABC DE G F （表示空格），建立的二叉树如表示空格），建立的二叉树如下图所示：下图所示：void CreateBiTree(BiTree&bt)/根据输入的字符建立二叉树根据输入的字符建立二叉树bt的二叉链表的二叉链表 scanf(&ch);if(ch=)bt=NULL;else if(!(bt=(BiTNode*)malloc(sizeof(BiTNode)exit(0);bt-data=ch;CreateBiTree(bt-lchild);CreateBiTree(bt-rchild);/CreateBiTree43ppt课件数据结构 第6章 树和二叉树遍历二叉树的有关说明：遍历二叉树的有关说明：遍历二叉树的基本操作是遍历二叉树的基本操作是访问结点访问结点，不论哪种次序进行遍历，不论哪种次序进行遍历，对于含有对于含有n个结点的二叉树，其时间复杂度均为个结点的二叉树，其时间复杂度均为O(n)。对于非递归遍历算法所需辅助空间为遍历过程中栈的最大容量，对于非递归遍历算法所需辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为即树的深度，最坏情况下为n，所以其空间复杂度也为，所以其空间复杂度也为O(n)。已知二叉树的已知二叉树的先序遍历序列和中序遍历序列先序遍历序列和中序遍历序列、中序遍历序列中序遍历序列和和后序遍历序列后序遍历序列以及以及层次遍历序列和中序遍历序列层次遍历序列和中序遍历序列，均可唯一地，均可唯一地确定一棵二叉树，确定一棵二叉树，如图如图；已知二叉树的；已知二叉树的先序遍历序列先序遍历序列和和后序遍历后序遍历序列序列不能唯一地确定一棵二叉树，不能唯一地确定一棵二叉树，如图如图。44ppt课件数据结构 第6章 树和二叉树已知二叉树的：已知二叉树的：先序序列：先序序列：ABCDEFGHI中序序列：中序序列：BCAEDGHFI构造的二叉树如右图所示：构造的二叉树如右图所示：已知二叉树的：已知二叉树的：先序序列：先序序列：AB后序序列：后序序列：BA构造的二叉树如右图所示：构造的二叉树如右图所示：45ppt课件数据结构 第6章 树和二叉树基本内容基本内容树的定义和基本术语树的定义和基本术语二叉树的定义及性质二叉树的定义及性质二叉树的存储结构二叉树的存储结构 遍历二叉树遍历二叉树线索二叉树线索二叉树哈夫曼树及其应用哈夫曼树及其应用树和森林树和森林本章小结本章小结46ppt课件数据结构 第6章 树和二叉树线索二叉树线索二叉树线索二叉树的必要性：线索二叉树的必要性：无论以何种次序进行遍历，遍历二叉树的过程是以一定无论以何种次序进行遍历，遍历二叉树的过程是以一定规则规则将二叉树中结点排列成一个将二叉树中结点排列成一个线性序列线性序列，其，其实质实质是对一个非线性结是对一个非线性结构进行线性化操作，使每个结点构进行线性化操作，使每个结点(除第一个和最后一个外）在这除第一个和最后一个外）在这些线性序列中有且仅有一个些线性序列中有且仅有一个直接前驱直接前驱和和直接后继直接后继。但是以二叉链。但是以二叉链表作为存储结构时，只能找到结点的左右孩子信息，不能直接得表作为存储结构时，只能找到结点的左右孩子信息，不能直接得到结点在任一序列中的前驱和后继信息。到结点在任一序列中的前驱和后继信息。47ppt课件数据结构 第6章 树和二叉树如何存储遍历过程中得到的关于结点的前驱和后继信息？如何存储遍历过程中得到的关于结点的前驱和后继信息？简单办法简单办法：在每个结点上增加两个指针域，分别指向结点在遍历：在每个结点上增加两个指针域，分别指向结点在遍历过程中得到的前驱和后继结点。过程中得到的前驱和后继结点。缺点缺点：浪费存储空间。：浪费存储空间。最终思路最终思路：因为在有：因为在有n个结点的二叉链表中必定存在个结点的二叉链表中必定存在n+1个空链域，个空链域，因此应充分利用这些空链域来存放结点的前驱和后继信息。该方案因此应充分利用这些空链域来存放结点的前驱和后继信息。该方案最终导致线索二叉树的提出。最终导致线索二叉树的提出。48ppt课件数据结构 第6章 树和二叉树线索二叉树的定义：线索二叉树的定义：lchildltagdatartagrchild其中：其中：线索二叉树的存储结构：线索二叉树的存储结构：typedef enum PointerTagLink,Thread;typedef struct BiThrNode TElemType data;struct BiThrNode *lchild,*rchild;PointerTag Ltag,Rtag;BiThrNode,*BiThrTree 以这种结点结构构成的二叉链表，叫做以这种结点结构构成的二叉链表，叫做线索链表线索链表，其中指向结点前驱，其中指向结点前驱和后继的指针，叫做和后继的指针，叫做线索线索。加上线索的二叉树称之为。加上线索的二叉树称之为线索二叉树线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化线索化。49ppt课件数据结构 第6章 树和二叉树带头结点的线索二叉树示例带头结点的线索二叉树示例(中序中序)50ppt课件数据结构 第6章 树和二叉树遍历线索二叉树遍历线索二叉树 在线索树上进行遍历，只要先找到序列中的第一个结点，在线索树上进行遍历，只要先找到序列中的第一个结点，然后依次找结点后继直至其后继为空时止。然后依次找结点后继直至其后继为空时止。遍历的第一个结点：遍历的第一个结点：先序序列先序序列中第一个结点必为根结点；中第一个结点必为根结点；中序序列中序序列中第一个结点必为二叉树的最左下角的结点；中第一个结点必为二叉树的最左下角的结点；后序序列后序序列中第一个结点必为二叉树的左子树的最右下角的结点。中第一个结点必为二叉树的左子树的最右下角的结点。如何在线索二叉树的找结点的后继呢？根据不同的遍历如何在线索二叉树的找结点的后继呢？根据不同的遍历方法，其后继结点的查找方法也不同。方法，其后继结点的查找方法也不同。51ppt课件数据结构 第6章 树和二叉树寻找当前结点寻找当前结点p在在中序遍历中序遍历下的后继与前驱下的后继与前驱if(p-RTag=Thread)后继为后继为 p-rchildelse /p-RTag=Link 后继为当前结点右子树最左下的结点后继为当前结点右子树最左下的结点if(p-LTag=Thread)前驱为前驱为 p-lchild else/p-LTag=Link 前驱为当前结点左子树的最右下的结点前驱为当前结点左子树的最右下的结点中序遍历序列：中序遍历序列：a+b*c-d-e/f52ppt课件数据结构 第6章 树和二叉树中序遍历线索二叉树中序遍历线索二叉树void InOrderTraverse_Thr(BiThrTree T)/对带头结点的线索二叉树对带头结点的线索二叉树T进行中序遍历进行中序遍历 p=T-lchild /T为头指针为头指针,p指向根结点指向根结点 Link=0;Thread=1 while(p!=T)/空树或遍历结束时空树或遍历结束时p=T while(p-LTag=Link)p=p-lchild;/先找到第一个结点先找到第一个结点 printf(“%c”,p-data);while(p-Rtag=Thread&p-rchild!=T)p=p-rchild;printf(“%c”,p-data);/访问后继结点访问后继结点 p=p-rchild;/InOrderTraverse_Thr53ppt课件数据结构 第6章 树和二叉树二叉树的线索化二叉树的线索化 线索化的实质是将二叉链表中的空指针改为指向前驱或后继线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此，线索化的线索，而前驱或后继的信息只有在遍历时才能得到，因此，线索化的过程即为在遍历的过程中修改空指针的过程，算法描述如下：的过程即为在遍历的过程中修改空指针的过程，算法描述如下：void InOrderThreading(BiThrTree&Thrt,BiThrTree T)/中序遍历二叉树中序遍历二叉树T，并将其中序线索化，并将其中序线索化，Thrt指向头结点指向头结点 if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)exit(0);Thrt-LTag=Link;Thrt-RTag=Thread;/建立头结点建立头结点 Thrt-rchild=Thrt;/右指针回指右指针回指 if(!T)Thrt-lchild=Thrt;/若二叉树空，则左指针回指若二叉树空，则左指针回指 else Thrt-lchild=T;pre=Thrt;InThreading(T);/中序遍历进行中序线索化中序遍历进行中序线索化 pre-rchild=Thrt;pre-RTag=Thread;/最后一个结点线索化最后一个结点线索化 Thrt-rchild=pre;/InOrderThreading54ppt课件数据结构 第6章 树和二叉树寻找当前结点寻找当前结点p在在先序先序遍历遍历下的后继与前驱下的后继与前驱55ppt课件数据结构 第6章 树和二叉树先序遍历线索二叉树先序遍历线索二叉树void PreOrder_Thr(BiThrTree T)/T指向头结点，头结点的左链指向头结点，头结点的左链lchild指向根结点，先序遍历线索二叉树指向根结点，先序遍历线索二叉树 p=T-lchild;/p指向根结点指向根结点 if(p)printf(p-data);while(p-rchild!=T)if(p-LTag=Link)p=p-lchild;else p=p-rchild;printf(p-data);/PreOrder_Thr56ppt课件数据结构 第6章 树和二叉树先序线索化二叉树先序线索化二叉树void PreThreading(BiThrTree p)if(p)if(!p-lchild)p-LTag=Thread;p-lchild=pre;if(!p-rchild)p-RTag=Thread;if(pre&pre-RTag=Thread)pre-rchild=p;pre=p;if(p-LTag=Link)PreThreading(p-lchild);if(p-RTag=Link)PreThreading(p-rchild);/PreThreading57ppt课件数据结构 第6章 树和二叉树寻找当前结点寻找当前结点p在在后序后序遍历遍历下的后继与前驱下的后继与前驱58ppt课件数据结构 第6章 树和二叉树后序遍历线索二叉树后序遍历线索二叉树void PostOrder_Thr(TriThrTree T)/T指向头结点，头结点的左链指向头结点，头结点的左链lchild指向根结点，后序遍历线索二叉树指向根结点，后序遍历线索二叉树 p=T-lchild;do while(p-LTag=Link)p=p-lchild;if(p-RTag=Link)p=p-rchild;while(p-LTag!=Thread|p-RTag!=Thread);printf(%c,p-data);while(p!=T)if(p-RTag=Link)f=p-parent;if(f-RTag=Thread|p=f-rchild)p=f;else p=f-rchild;do while(p-LTag=Link)p=p-lchild;if(p-RTag=Link)p=p-rchild;while(p-LTag!=Thread|p-RTag!=Thread);else p=p-rchild;printf(%c,p-data);/PostOrder_Thr59ppt课件数据结构 第6章 树和二叉树后序线索二叉树后序线索二叉树void PostThreading(TriThrTree p)if(p)PostThreading(p-lchild);PostThreading(p-rchild);if(!p-lchild)p-LTag=Thread;p-lchild=pre;if(!p-rchild)p-RTag=Thread;if(pre&pre-RTag=Thread)pre-rchild=p;pre=p;/PostThreading优点：优点：对于遍历操作，线索树优于非线索树，遍历对于遍历操作，线索树优于非线索树，遍历线索树不用设栈线索树不用设栈60ppt课件数据结构 第6章 树和二叉树void InThreading(BiThrTree p)/中序线索化中序线索化 if(p)InThreading(p-lchild);/左子树线索化左子树线索化 if(!p-lchild)p-LTag=Thread;p-lchild=pre;/前驱线索前驱线索 if(!pre-rchild)pre-RTag=Thread;pre-rchild=p;/后继线索后继线索 pre=p;/保持保持pre指向指向p的前驱的前驱 InThreading(p-rchild);/右子树线索右子树线索 /InThreading61ppt课件数据结构 第6章 树和二叉树基本内容基本内容树的定义和基本术语树的定义和基本术语二叉树的定义及性质二叉树的定义及性质二叉树的存储结构二叉树的存储结构 遍历二叉树遍历二叉树线索二叉树线索二叉树哈夫曼树及其应用哈夫曼树及其应用树和森林树和森林本章小结本章小结62ppt课件数据结构 第6章 树和二叉树1、树的存储结构、树的存储结构（1）双亲表示法）双亲表示法 以一组连续空间存储树的结点，同时在每个结点中附设一个指以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置，其形式说明如下：示器指示其双亲结点在链表中的位置，其形式说明如下：#define MAX_TREE_SIZE 100typedef struct PTNode /结点结构结点结构 TElemTypedata;int parent;/双亲位置域双亲位置域PTNode;typedef struct /树结构树结构 PTNode nodesMAX_TREE_SIZE;int r,n;/根的位置和结点数根的位置和结点数PTree树和森林树和森林63ppt课件数据结构 第6章 树和二叉树树的双亲表示法示例树的双亲表示法示例RABCDEFGHK-10123456789000113666数组下标数组下标优点优点：PARENT(T,x)操作可以在常量时间内实现操作可以在常量时间内实现缺点缺点：求结点的孩子时需要遍历整个结构求结点的孩子时需要遍历整个结构64ppt课件数据结构 第6章 树和二叉树（2）孩子表示法：）孩子表示法：由于树中每个结点有多棵子树，可使用多重链表表示树，其由于树中每个结点有多棵子树，可使用多重链表表示树，其每个结点有多个指针域，其中每个指针指向一棵子树的根结点。每个结点有多个指针域，其中每个指针指向一棵子树的根结点。其结点有如下两种格式。如下图：其结点有如下两种格式。如下图：child1datachild2childddegreedatachild1child2childd第一种格式：第一种格式：结点同构结点同构，链表中会产生许多空链域，浪费空间；，链表中会产生许多空链域，浪费空间；容易证明：容易证明：在一棵有点在一棵有点n个结点度为个结点度为k的树中必有的树中必有n(k-1)+1个空链域。个空链域。第二种格式：第二种格式：结点不同构结点不同构，空间比较节约，但操作不方便。，空间比较节约，但操作不方便。65ppt课件数据结构 第6章 树和二叉树 另外一种办法：每个结点的孩子排列起来，看成一个线性表，另外一种办法：每个结点的孩子排列起来，看成一个线性表，以单链表作为存储结构。则以单链表作为存储结构。则n个结点有个结点有n个孩子链表（叶子的孩子个孩子链表（叶子的孩子链表为空表）。链表为空表）。n个头指针又组成一个线性表，为便于查找，可采个头指针又组成一个线性表，为便于查找，可采用顺序存储结构。用顺序存储结构。typedef struct CTNode /孩子结点孩子结点 int child;struct CTNode *next;*ChildPtr;typedef struct TElemType data;ChildPtr firstchild;/孩子链表头指针孩子链表头指针CTBox;typedef struct CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根的位置结点数和根的位置;CTree;66ppt课件数据结构 第6章 树和二叉树树的孩子链表表示法示例树的孩子链表表示法示例优点优点：CHILD(T,i,&x)操作可以在常量时间内实现操作可以在常量时间内实现缺点缺点：PARENT(T,x)需要遍历整个结构需要遍历整个结构解决方法解决方法：将双亲表示法和孩子表示法结合起来进行操作将双亲表示法和孩子表示法结合起来进行操作67ppt课件数据结构 第6章 树和二叉树（3）孩子兄弟表示法：）孩子兄弟表示法：又称又称二叉树表示法二叉树表示法，或，或二叉链表表示法二叉链表表示法。即以二叉链表做树。即以二叉链表做树的存储结构，链表中的两个链域分别指向该结点的的存储结构，链表中的两个链域分别指向该结点的第一个孩子结第一个孩子结点点和和下一个兄弟结点下一个兄弟结点。其形式说明如下：。其形式说明如下：typedef struct CSNode ElemType data;struct CSNode *firstchild,*nextsibling;CSNode,*CSTree;68ppt课件数据结构 第6章 树和二叉树树的孩子兄弟表示法示例树的孩子兄弟表示法示例优点优点：便于实现各种树的操作：便于实现各种树的操作69ppt课件数据结构 第6章 树和二叉树2、森林与二叉树的转换、森林与二叉树的转换 由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个作为媒介可导出树与二叉树之间的一个对应关系对应关系。给定一棵树，可以找到给定一棵树，可以找到唯一唯一的一棵二叉树的一棵二叉树与之对应与之对应。从物理结构。从物理结构来看，他们的二叉链表表示相同，只是解释不同。来看，他们的二叉链表表示相同，只是解释不同。如图所示如图所示树的根结点无兄弟结点，其对应的二叉树的树的根结点无兄弟结点，其对应的二叉树的右子树必为空右子树必为空。若把。若把森林中的第二棵树的根结点看成是第一棵树的根结点的兄弟，则同森林中的第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可以导出森林与二叉树之间的对应关系。样可以导出森林与二叉树之间的对应关系。70ppt课件数据结构 第6章 树和二叉树树转换成二叉树的方法树转换成二叉树的方法(1)在同胞兄弟之间加连线；在同胞兄弟之间加连线；ABCEDABCED(2)保留结点与第一个孩子之间的连线，去掉其余连线；保留结点与第一个孩子之间的连线，去掉其余连线；ABCED(3)将结点与孩子之间的连线调整为垂直线，将同胞兄弟之间的将结点与孩子之间的连线调整为垂直线，将同胞兄弟之间的连线调整为水平线；连线调整为水平线；ABCED(4)以根结点为轴，以根结点为轴，顺时针顺时针旋转旋转45度。度。71ppt课件数据结构 第6章 树和二叉树二叉树转换成树的方法二叉树转换成树的方法(1)将每个结点的左孩子沿及其右链访问到的所有结点与左孩子将每个结点的左孩子沿及其右链访问到的所有结点与左孩子的双亲之间加连线；的双亲之间加连线；(2)将结点与右链之间的连线去掉；将结点与右链之间的连线去掉；(3)将所有的兄弟结点调整在同一水平线上，并作适当的角度调整。将所有的兄弟结点调整在同一水平线上，并作适当的角度调整。72ppt课件数据结构 第6章 树和二叉树森林转换成二叉树的方法森林转换成二叉树的方法(1)将每棵树转化成二叉树；将每棵树转化成二叉树；(2)将第一棵树的树根作为整棵二叉树的树根；将第一棵树的树根作为整棵二叉树的树根；(3)将剩余的每棵树依次连接到二叉树的右子树上。将剩余的每棵树依次连接到二叉树的右子树上。73ppt课件数据结构 第6章 树和二叉树3、树与森林的遍历、树与森林的遍历树的遍历有两种：树的遍历有两种：先根遍历先根遍历：先访问树的根结点，然后依次先根遍历根的每棵子树；：先访问树的根结点，然后依次先根遍历根的每棵子树；（等价于二叉树的先序遍历）（等价于二叉树的先序遍历）后根遍历后根遍历：先依次后根遍历每棵子树，然后访问根结点。：先依次后根遍历每棵子树，然后访问根结点。（等价于（等价于树的中序遍历）树的中序遍历）先根序列先根序列：ABCDE后根序列后根序列：BDCEA74ppt课件数据结构 第6章 树和二叉树先序遍历森林先序遍历森林：若森林非空，则按下述规则遍历之：若森林非空，则按下述规则遍历之(1)访问森林中第一棵树的根结点；访问森林中第一棵树的根结点；(2)先序遍历第一棵树中根结点的子树森林；先序遍历第一棵树中根结点的子树森林；(3)先序遍历除去第一棵树之后剩余的树构成的森林。先序遍历除去第一棵树之后剩余的树构成的森林。（等价于二叉树的先序遍历）（等价于二叉树的先序遍历）森林的遍历有两种：森林的遍历有两种：中序遍历森林中序遍历森林：若森林非空，则按下述规则遍历之：若森林非空，则按下述规则遍历之(1)中序遍历第一棵树的根结点的子树森林；中序遍历第一棵树的根结点的子树森林；(2)访问第一棵树的根结点；访问第一棵树的根结点；(3)中序遍历除去第一棵树之后剩余的树构成的森林。中序遍历除去第一棵树之后剩余的树构成的森林。（等价于二叉树的中序遍历）（等价于二叉树的中序遍历）先序序列先序序列：ABCDEFGHIJ中序序列中序序列：BCDAFEHJIG75ppt课件数据结构 第6章 树和二叉树76ppt课件数据结构 第6章 树和二叉树基本内容基本内容树的定义和基本术语树的定义和基本术语二叉树的定义及性质二叉树的定义及性质二叉树的存储结构二叉树的存储结构 遍历二叉树遍历二叉树线索二叉树线索二叉树哈夫曼树及其应用哈夫曼树及其应用树和森林树和森林本章小结本章小结77ppt课件数据结构 第6章 树和二叉树哈夫曼（哈夫曼（Huffman）树及其应用）树及其应用1、相关概念、相关概念路径和路径长度路径和路径长度：从树中一个结点到另一个结点之间的分支构从树中一个结点到另一个结点之间的分支构成这两个结点之间的成这两个结点之间的路径路径，路径上的分支数目称作，路径上的分支数目称作路径长度路径长度。树的路径长度树的路径长度：从树根到每一个结点的路径长度之和。从树根到每一个结点的路径长度之和。树的带权路径长度树的带权路径长度：树中所有叶子结点的带权路径长度之和，树中所有叶子结点的带权路径长度之和，通常记作：通常记作：哈夫曼树哈夫曼树：带权路径长度带权路径长度WPL最小的二叉树称作赫夫曼树或最优最小的二叉树称作赫夫曼树或最优二叉树。二叉树。78ppt课件数据结构 第6章 树和二叉树(1)WPL=7*2+5*2+2*2+4*2=36(2)WPL=7*3+5*3+2*1+4*2=46(3)WPL=7*1+5*2+2*3+4*3=35（哈夫曼树）（哈夫曼树）79ppt课件数据结构 第6章 树和二叉树2、构造哈夫曼树（哈夫曼算法）、构造哈夫曼树（哈夫曼算法）（1）根据给定的）根据给定的n个权值个权值w1,w2,.,wn 构成构成n棵二叉树的集合棵二叉树的集合F=T1,T2,.,Tn,其中每棵二叉树其中每棵二叉树Ti只有一个带权为只有一个带权为wi的根结点的根结点,其其左右子树为空左右子树为空;（2）在）在F中中选取两棵根结点的权值最小的树作为左右子树构造选取两棵根结点的权值最小的树作为左右子树构造一棵新二叉树，一棵新二叉树，且置新的二叉树的根结点的权值为其左右子树上且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和；根结点的权值之和；（3）在）在F中删除这两棵树，同时将新得到的二叉树加入中删除这两棵树，同时将新得到的二叉树加入F中；中；（4）重复（）重复（2）和（）和（3），直到），直到F中只含一棵二叉树为止。这棵中只含一棵二叉树为止。这棵树便是哈夫曼树。树便是哈夫曼树。80ppt课件数据结构 第6章 树和二叉树赫夫曼树构造过程示例赫夫曼树构造过程示例181ppt课件数据结构 第6章 树和二叉树赫夫曼树构造过程示例赫夫曼树构造过程示例2(非唯一性非唯一性)WPL1=(2+4+5+6)*2=34WPL2=6*1+5*2+2*3+4*3=3482ppt课件数据结构 第6章 树和二叉树3、哈夫曼树应用实例、哈夫曼树应用实例判定问题判定问题 在很多问题的处理过程中，需要进行大量的条件判断，这些在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计