数据结构与算法-第五章Trees

1、信息工程学院信息工程学院School of Information Engineering2第第5 5章章 树形结构树形结构(Trees)(Trees)5.1 5.1 树的基本概念树的基本概念(Basic concept of tree)(Basic concept of tree) 5.2 5.2 二叉树概念和性质二叉树概念和性质(Property and concept of binary tree)(Property and concept of binary tree)5.3 5.3 二叉树存储结构二叉树存储结构(Physical storage structure of binary

2、 tree)(Physical storage structure of binary tree)5.4 5.4 二叉树的遍历二叉树的遍历(Binary tree traversals)(Binary tree traversals)35.5 5.5 二叉树的基本运算及其实现二叉树的基本运算及其实现(Algorithm implementation and basic operations of binary tree)5.6 5.6 二叉树的构造二叉树的构造(Construction of binary tree)(Construction of binary tree)5.8 5.8 哈夫

3、曼树哈夫曼树(Huffman tree)(Huffman tree) SummarySummary5.7 5.7 线索二叉树线索二叉树(Threaded binary tree)(Threaded binary tree)45.1.1 5.1.1 树的定义树的定义(Definition)(Definition) 5.1.3 5.1.3 树的基本术语树的基本术语(Basic terminology) (Basic terminology) 5.1.2 5.1.2 树的表示树的表示(Representation)(Representation)5.1.4 5.1.4 树的性质树的性质(Proper

4、ty)(Property)5.1.5 5.1.5 树的基本运算树的基本运算(Basic operation)(Basic operation)5.1.6 5.1.6 树的存储结构树的存储结构(Physical structure)(Physical structure)5.1 5.1 树的基本概念树的基本概念(Basic concept of tree)(Basic concept of tree) 55.1.1 5.1.1 树的定义树的定义(Definition)(Definition) 形式化定义：形式化定义： 树：树：TK,R。K是包含是包含n个结点的有穷集合个结点的有穷集合(n0),关

5、系关系R满足以下条件满足以下条件: (1) 有且仅有一个结点有且仅有一个结点k0K,它对于关系它对于关系R来说来说没有前驱结点没有前驱结点,结点结点k0称作树的根。称作树的根。 (2) 除结点除结点k0外外,K中的每个结点对于关系中的每个结点对于关系R来说来说都有且仅有一个前驱结点。都有且仅有一个前驱结点。 (3) K中每个结点对于关系中每个结点对于关系R来说可以有多个后来说可以有多个后继结点。继结点。6递归定义：递归定义： 树是由树是由n(n0)个结点组成的有限集合个结点组成的有限集合(记为记为T)。其。其中中, 如果如果n=0,它是一棵空树它是一棵空树,这是树的特例；这是树的特例； 如果如

6、果n0,这这n个结点中存在个结点中存在(有仅存在有仅存在)一个结点作一个结点作为树的根结点为树的根结点,简称为根简称为根(root),其余结点可分为其余结点可分为m (m0)个互不相交的有限集个互不相交的有限集T1,T2,Tm,其中每一棵其中每一棵子集本身又是一棵符合本定义的树子集本身又是一棵符合本定义的树,称为根称为根root的子的子树。树。7A只有根结点的树ABCDEFGHIJKLM有子树的树根子树85.1.2 5.1.2 树的表示树的表示(Representation)(Representation) ( (1) 树形表示法。树形表示法。这是树的最基本的表示这是树的最基本的表示,使用一使

7、用一棵倒置的树表示树结构棵倒置的树表示树结构,非常直观和形象。下图就是非常直观和形象。下图就是采用这种表示法。采用这种表示法。 A C G J B E D F I H M K L 树形表示法树形表示法 9 (2) 文氏图表示法。文氏图表示法。使用集合以及集合使用集合以及集合的包含关系描述树结构。下图就是树的文氏的包含关系描述树结构。下图就是树的文氏图表示法。图表示法。 H L D K I M C G J E B F 文氏图表示法文氏图表示法 A 10 (3) 凹入表示法。凹入表示法。使用线段的伸缩描述树结使用线段的伸缩描述树结构。下图是树的凹入表示法。构。下图是树的凹入表示法。11 (4) 括

8、号表示法。括号表示法。 将树的根结点写在括号的左边将树的根结点写在括号的左边,除根结点之外除根结点之外的其余结点写在括号中并用逗号间隔来描述树结的其余结点写在括号中并用逗号间隔来描述树结构。下图是树的括号表示法。构。下图是树的括号表示法。 括括号号表表示示法法 A(B(E,F),C(G(J),D(H,I(K,L,M) 125.1.3 5.1.3 树的基本术语树的基本术语( (Basic terminology)结点(node)度不为零的结点称为度不为零的结点称为非终端结点，非终端结点，又叫又叫分支分支结点结点。度为零的结点称为。度为零的结点称为终端结点终端结点或或叶结点叶结点。结点的度(deg

9、ree)结点拥有的子树数叶子(leaf)度为0的结点孩子(child)在一棵树中，每个结点的后继双亲(parents)孩子结点的上层结点叫该结点的兄弟(sibling)同一双亲的孩子树的度(degree)一棵树中最大的结点度数13结点的层次(level)从根结点算起，根为第一层，它的孩子为第二层深度(depth)树中结点的最大层次数祖先(ancestor)-从根到该结点所经分支上的所有结点堂兄弟(cousin)双亲在同一层次的结点有序树(ordered tree)将树中结点的各个子树看成从左至右是有次序的第一孩子(first child)-有序树中最左边的子树的根森林(forest)m(m0)

10、棵互不相交的树的集合 对树中各个结点而言，其子树的集合即为森林14ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先155.1.4 5.1.4 树的性质树的性质(Property)(Property) Property 1 树中的结点数等于所有结点的度数加树中的结点数等于所有结点的度数加1。 Prove：根据树的定义根据树的定义,在一棵树中

11、在一棵树中,除树根结点外除树根结点外,每个结点有且仅有一个前驱结点。每个结点有且仅有一个前驱结点。也就是说也就是说,每个结每个结点与指向它的一个分支一一对应点与指向它的一个分支一一对应,所以除树根之外的所以除树根之外的结点数等于所有结点的分支数结点数等于所有结点的分支数(度数度数),从而可得树中从而可得树中的结点数等于所有结点的度数加的结点数等于所有结点的度数加1。16 Property 2 度为度为m的树中第的树中第i层上至多有层上至多有mi-1个结点个结点,这里应有这里应有i1。 Prove(采用数学归纳法采用数学归纳法) 对于第一层对于第一层,因为树中的第一层上只有一个结点因为树中的第一

12、层上只有一个结点,即即整个树的根结点整个树的根结点,而由而由i=1代入代入mi-1,得得mi-1=m1-1=1,也同样也同样得到只有一个结点得到只有一个结点,显然结论成立。显然结论成立。 假设对于第假设对于第(i-1)层层(i1)命题成立命题成立,即度为即度为m的树中第的树中第(i-1)层上至多有层上至多有mi-2个结点个结点,则根据树的度的定义则根据树的度的定义,度为度为m的树中每个结点至多有的树中每个结点至多有m个孩子结点个孩子结点,所以所以第第i层上的结层上的结点数至多为第点数至多为第(i-1)层上结点数的层上结点数的m倍倍,即至多为即至多为mi-2m=mi-1个个,这与命题相同这与命题

13、相同,故命题成立。故命题成立。17 Property 3 高度为高度为h的的m次树至多有次树至多有 个结点。个结点。 Prove：由树的性质由树的性质2可知可知,第第i层上最多结点数为层上最多结点数为mi-1(i=1,2,h),显然当高度为显然当高度为h的的m次树次树(即度为即度为m的树的树)上每一层都达到最多结点数时上每一层都达到最多结点数时,整个整个m次树具有最多结次树具有最多结点数点数,因此有：因此有：整个树的最多结点数整个树的最多结点数=每一层最多结点数之和每一层最多结点数之和=m0+m1+m2+mh-1 = 。11 mmh11 mmh18 Property 4 具有具有n个结点的个结

14、点的m次树的最小高度为次树的最小高度为 logm(n(m-1)+1) 。 Prove：设具有设具有n个结点的个结点的m次树的高度为次树的高度为h,若在该若在该树中前树中前h-1层都是满的层都是满的,即每一层的结点数都等于即每一层的结点数都等于mi-1个个(1ih-1),第第h层层(即最后一层即最后一层)的结点数可能满的结点数可能满,也可也可能不满能不满,则该树具有最小的高度。其高度则该树具有最小的高度。其高度h可计算如下：可计算如下：19根据树的性质根据树的性质3可得：可得： n乘乘(m-1)后得：后得： mh-1n(m-1)+1mh以以m为底取对数后得：为底取对数后得：h-1logm(n(m

15、-1)+1)h即即logm(n(m-1)+1)hlogm(n(m-1)+1)+1因因h只能取整数只能取整数,所以所以 h= logm(n(m-1)+1) 结论得证。结论得证。111 mmh11 mmh205.1.5 5.1.5 树的基本运算树的基本运算(Basic operation)(Basic operation) Tree operation can be classfied into Tree operation can be classfied into three types:three types: First,First,寻找满足某种特定关系的结点寻找满足某种特定关系的结点,

16、,如寻找如寻找当前结点的双亲结点等；当前结点的双亲结点等； Second,Second,插入或删除某个结点插入或删除某个结点, ,如在树的当前如在树的当前结点上插入一个新结点或删除当前结点的第结点上插入一个新结点或删除当前结点的第i i个个孩子结点等；孩子结点等； Third,Third,遍历树中每个结点遍历树中每个结点, ,这里着重介绍。这里着重介绍。21 树的遍历树的遍历(traversal)运算运算是指按某种方式访问是指按某种方式访问树中的每一个结点且每一个结点只被访问一次。树中的每一个结点且每一个结点只被访问一次。树的遍历运算的算法主要有先根遍历和后根遍历树的遍历运算的算法主要有先根遍

17、历和后根遍历两种。两种。 注意注意,下面的先根遍历和后根遍历算法都是递归下面的先根遍历和后根遍历算法都是递归的的。 1. 先根遍历先根遍历(Preorder Traversal) 先根遍历过程为：先根遍历过程为： (1) 访问根结点；访问根结点； (2) 按照从左到右的次序先根遍历根结点的每按照从左到右的次序先根遍历根结点的每一棵子树。一棵子树。 22 2. 后根遍历后根遍历(Postorder Traversal) 后根遍历过程为：后根遍历过程为： (1) 按照从左到右的次序后根遍历根结点的每一按照从左到右的次序后根遍历根结点的每一棵子树；棵子树； (2) 访问根结点。访问根结点。23ABC

18、DEFGHIJKLMNO先根遍历：后根遍历：层次遍历：ABE F I GCDHJ KL NOME I F G B C J K N O L M H D AAB C DE F GH I J KL MNO245.1.6 5.1.6 树的存储结构树的存储结构(Physical structure)(Physical structure)1. 1. 双亲存储结构双亲存储结构 这种存储结构是一种顺序存储结构这种存储结构是一种顺序存储结构, ,用用一组连一组连续空间存储树的所有结点续空间存储树的所有结点, ,同时在每个结点中附同时在每个结点中附设一个伪设一个伪指针指示其双亲结点的位置指针指示其双亲结点的位置

19、。 A D B C G E F A -1 B 0 C 0 D 0 E 2 F 2 G 2 0 1 2 3 4 5 6 (a) (b) 树的双亲存储结构示意图树的双亲存储结构示意图252. 孩子链存储结构孩子链存储结构 孩子链存储结构可按树的度孩子链存储结构可按树的度(即树中所有结点度的即树中所有结点度的最大值最大值)设计结点的孩子结点指针域个数。下图设计结点的孩子结点指针域个数。下图(a)的树的树对应的孩子链存储结构如图对应的孩子链存储结构如图(b)所示。所示。 A B C F D E (a) G A B C D E F G (b) 树的树的孩子链孩子链存储结构示意图存储结构示意图263. 孩

20、子兄弟链存储结构孩子兄弟链存储结构 孩子兄弟链存储结构是为每个结点设计三个域：孩子兄弟链存储结构是为每个结点设计三个域：一个一个数据元素域数据元素域,一个该结点的一个该结点的第一个孩子结点指第一个孩子结点指针域针域,一个该结点的一个该结点的下一个兄弟结点指针域下一个兄弟结点指针域。 下图下图(a)的树对应的孩子兄弟链存储结构如图的树对应的孩子兄弟链存储结构如图(b)所示。所示。 A B C F D E (a) G A B D C E G F (b) 树的树的孩子兄弟链孩子兄弟链存储结构示意图存储结构示意图275.2.1 5.2.1 二叉树概念二叉树概念(Concept)(Concept)5.2

21、.2 5.2.2 二叉树性质二叉树性质(Property)(Property)5.2.3 5.2.3 二叉树与树、森林之间的转换二叉树与树、森林之间的转换(Transformation between binary tree and (Transformation between binary tree and tree, binary tree and forest)tree, binary tree and forest)5.2 5.2 二叉树概念和性质二叉树概念和性质(Property and concept of binary tree)(Property and concept of

22、 binary tree)285.2.1 二叉树的概念(Binary tree)另一种树型结构。 Characteristic 每个结点至多只有二棵子树(即不存在度大于2的结点) 二叉树的子树有左、右之分，且其次序不能任意颠倒 Basic formsA只有根结点的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树均非空29 在一棵二叉树中在一棵二叉树中, ,如果所有分支结点都有左孩子如果所有分支结点都有左孩子结点和右孩子结点结点和右孩子结点, ,并且叶结点都集中在二叉树的最并且叶结点都集中在二叉树的最下一层下一层, ,称为称为满二叉树满二叉树(Full Binary Tree)(Ful

23、l Binary Tree)。 可以对满二叉树的结点进行连续编号可以对满二叉树的结点进行连续编号, ,约定编号约定编号从树根为从树根为1 1开始开始, ,按照层数从小到大、同一层从左到右按照层数从小到大、同一层从左到右的次序进行。的次序进行。 A B C D E H I J K F G L M N O 1 2 3 4 5 6 7 8 9 10 15 11 12 13 14 满二叉树满二叉树 12个结点的二叉树称为且有一棵深度为kk30 若二叉树中最多只有最下面两层的结点的度数可若二叉树中最多只有最下面两层的结点的度数可以小于以小于2,2,并且最下面一层的叶结点都依次排列在该层并且最下面一层的叶

24、结点都依次排列在该层最左边的位置上最左边的位置上, ,称为称为完全二叉树完全二叉树(Complete Binary (Complete Binary Tree)Tree)。 深度为深度为k，有，有n个结点的二叉树当且仅当其每一个结点都与个结点的二叉树当且仅当其每一个结点都与深度为深度为k的满二叉树中编号从的满二叉树中编号从1至至n的结点一一对应时，称为的结点一一对应时，称为 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完全二叉树完全二叉树 311231145891213671014151231145891267101234567123456325

25、.2.2 5.2.2 二叉树性质二叉树性质(Property)(Property) Property 1 非空二叉树上叶结点数等于双分支结点非空二叉树上叶结点数等于双分支结点数加数加1。 证明：证明：设二叉树上叶结点数为设二叉树上叶结点数为n0,单分支结点数为单分支结点数为n1,双分支双分支结点数为结点数为n2,则则总结点数总结点数=n0+n1+n2。 在一棵二叉树中在一棵二叉树中,所有结点的分支数所有结点的分支数(即度数即度数)应等于单分支结应等于单分支结点数加上双分支结点数的点数加上双分支结点数的2倍倍,即即总的分支数总的分支数=n1+2n2。 由于二叉树中除根结点以外由于二叉树中除根结点

26、以外,每个结点都有惟一的一个分支指每个结点都有惟一的一个分支指向它向它,因此二叉树中有：因此二叉树中有： 总的分支数总的分支数=总结点数总结点数-1。 由上述三个等式可得：由上述三个等式可得：n1+2n2=n0+n1+n2-1即：即：n0=n2+133 Property 2 非空二叉树上第非空二叉树上第i层上至多有层上至多有2i-1个结点个结点,这里应有这里应有i1。 证明：用归纳法证明之 i=1时，只有一个根结点， 是对的 假设对所有j(1jdata); /*访问根结点访问根结点*/ PreOrder(b-lchild); PreOrder(b-rchild); A B C E F D G

27、A B C D E F G (a) (b) 先序遍历序列： ABDGCEF5.4.2 5.4.2 二叉树遍历递归算法二叉树遍历递归算法(Recursive algorithm of binary tree traversal) 51 void InOrder(BTNode *b) /*中序遍历的递归算法中序遍历的递归算法*/ if (b!=NULL) InOrder(b-lchild); printf(%c ,b-data); /*访问根结点访问根结点*/ InOrder(b-rchild); A B C E F D G A B C D E F G (a) (b) 中序遍历序列： DGBAEC

28、F52 void PostOrder(BTNode *b) /*后序遍历递归算法后序遍历递归算法*/ if (b!=NULL) PostOrder(b-lchild); PostOrder(b-rchild); printf(%c ,b-data); /*访问根结点访问根结点*/ A B C E F D G A B C D E F G (a) (b) 后序遍历序列： GDBEFCA53Level Order Traversal其过程是：其过程是：若二叉树非空（假设其高度为若二叉树非空（假设其高度为h），则：），则：（1）访问根结点（第）访问根结点（第1层）；层）；（2）从左到右访问第）从左到右

29、访问第2层的所有结点；层的所有结点；（3）从左到右访问第）从左到右访问第3层的所有结点、层的所有结点、第、第h层的所有结点。层的所有结点。 A B C E F D G A B C D E F G (a) (b) 层次遍历序列： ABCDEFG54void LevelOrder(BTNode *b) BTNode *p; BTNode *quMaxSize;/*定义环形队列定义环形队列,存放结点指针存放结点指针*/ int front,rear;/*定义队头和队尾指针定义队头和队尾指针*/ front=rear=-1;/*置队列为空队列置队列为空队列*/ rear+; qurear=b;/*根结

30、点指针进入队列根结点指针进入队列*/ while (front!=rear)/*队列不为空队列不为空*/ front=(front+1)%MaxSize; p=qufront;/*队头出队列队头出队列*/ printf(%c ,p-data);/*访问结点访问结点*/55if (p-lchild!=NULL)/*有左孩子时将其进队有左孩子时将其进队*/ rear=(rear+1)%MaxSize; qurear=p-lchild; if (p-rchild!=NULL)/*有右孩子时将其进队有右孩子时将其进队*/ rear=(rear+1)%MaxSize; qurear=p-rchild;

31、56 Example 5.2 假设二叉树采用二叉链存储结构存储假设二叉树采用二叉链存储结构存储,试设计一个算法试设计一个算法,输出一棵给定二叉树的所有叶子结输出一棵给定二叉树的所有叶子结点。点。 Solution：输出一棵二叉树的所有叶子结点的递归输出一棵二叉树的所有叶子结点的递归模型模型f()如下：如下： f(b)：不做任何事件：不做任何事件 若若b=NULL f(b)：输出：输出*b结点的结点的data域域 若若*b为叶子结点为叶子结点 f(b)：f(b-lchild);f(b-rchild) 其他情况其他情况57 void DispLeaf(BTNode *b) if (b!=NULL)

32、 if (b-lchild=NULL & b-rchild=NULL) printf(%c ,b-data); else DispLeaf(b-lchild); DispLeaf(b-rchild); 58先序遍历非递归算法先序遍历非递归算法 先将根结点进栈，在栈不空时循环：先将根结点进栈，在栈不空时循环： 出栈出栈p p，访问，访问* *p p结点，若右孩子不空将该右结点，若右孩子不空将该右孩子结点进栈，若左孩子不空再将该左孩子结孩子结点进栈，若左孩子不空再将该左孩子结点进栈。点进栈。5.4.3 5.4.3 二叉树遍历非递归算法二叉树遍历非递归算法 (Non-recursive al

33、gorithm of binary tree traversal) 59void PreOrder2(BTNode *b) BTNode *StMaxSize,*p; int top=-1;top+; Sttop=b; /根结点入栈根结点入栈while (top-1) /栈不为空时循环栈不为空时循环 p=Sttop; top-; /退栈并访问该结点退栈并访问该结点 printf(%c ,p-data); if (p-rchild!=NULL) /右孩子结点入栈右孩子结点入栈 top+; Sttop=p-rchild; if (p-lchild!=NULL) /左孩子结点入栈左孩子结点入栈 to

34、p+; Sttop=p-lchild; 602. 中序遍历非递归算法中序遍历非递归算法 由中序遍历过程可知，采用一个栈保存需要返回的结由中序遍历过程可知，采用一个栈保存需要返回的结点指针，点指针，先扫描（并非访问）根结点的所有左结点并将它先扫描（并非访问）根结点的所有左结点并将它们一一进栈。们一一进栈。 然后出栈一个结点然后出栈一个结点，显然该结点没有左孩子结点或者，显然该结点没有左孩子结点或者左孩子结点已访问过（进一步说明该结点的左子树均已访左孩子结点已访问过（进一步说明该结点的左子树均已访问），则访问它。问），则访问它。然后扫描该结点的右孩子结点，将其进然后扫描该结点的右孩子结点，将其进栈

35、，再扫描该右孩子结点的所有左结点并一一进栈，栈，再扫描该右孩子结点的所有左结点并一一进栈，如此如此这样，直到栈空为止。这样，直到栈空为止。61 void InOrder2(BTNode *b) BTNode *StMaxSize,*p; int top=-1;p=b;while (top-1 | p!=NULL) while (p!=NULL) /扫描扫描*p的所有左结点并进栈的所有左结点并进栈 top+; Sttop=p; p=p-lchild; if (top-1) p=Sttop;top-; /出栈出栈*p结点结点 printf(%c ,p-data); /访问之访问之 p=p-rchi

36、ld; /扫描扫描*p的右孩子结点的右孩子结点 /end of while(top-1 | p!=NULL) 找找*b的最左下的最左下结点结点623. 后序遍历非递归算法后序遍历非递归算法 由后序遍历过程可知，采用一个栈保存需要返回的结点指由后序遍历过程可知，采用一个栈保存需要返回的结点指针，先扫描根结点的所有左结点并一一进栈，出栈一个结点针，先扫描根结点的所有左结点并一一进栈，出栈一个结点*b即当前结点，然后扫描该结点的右孩子结点并入栈，再扫描该即当前结点，然后扫描该结点的右孩子结点并入栈，再扫描该右孩子结点的所有左结点并入栈。当一个结点的左右孩子结点右孩子结点的所有左结点并入栈。当一个结点

37、的左右孩子结点均访问后再访问该结点，如此这样，直到栈空为止。均访问后再访问该结点，如此这样，直到栈空为止。 难点：难点：如何判断一个结点如何判断一个结点*b的右孩子结点已访问过的右孩子结点已访问过，为此，为此用用p保存刚刚访问过的结点（初值为保存刚刚访问过的结点（初值为NULL），若），若b-rchild=p成立（成立（在后序遍历中，在后序遍历中，*b的右孩子结点一定刚好在的右孩子结点一定刚好在*b之前访之前访问问），说明），说明*b的左右子树均已访问，现在应访问的左右子树均已访问，现在应访问*b。 63void PostOrder2(BTNode *b)BTNode *StMaxSize;

38、BTNode *p;int flag, top=-1;/栈指针置初值栈指针置初值do while (b!=NULL) /将将*b的所有左结点进栈的所有左结点进栈 top+; Sttop=b; b=b-lchild; p=NULL; /p指向栈顶结点的前一个已访问的结点指向栈顶结点的前一个已访问的结点 flag=1; /设置设置b的访问标记为已访问过的访问标记为已访问过找最左下结点找最左下结点64 while (top!=-1 & flag=1) b=Sttop; /取出当前的栈顶元素取出当前的栈顶元素 if (b-rchild=p) printf(%c ,b-data);/访问访问*b

39、结点结点top-;p=b;/p指向则被访问的结点指向则被访问的结点 else b=b-rchild; /b指向右孩子结点指向右孩子结点 flag=0;/设置未被访问的标记设置未被访问的标记 /end of while (top!=-1 & flag=1) while (top!=-1); b b的右孩子不存在或已访问过的右孩子不存在或已访问过65 从上述过程可知，栈中保存的是当前从上述过程可知，栈中保存的是当前结点结点*b的所有祖先结点（均未访问过）。的所有祖先结点（均未访问过）。 例如，书中例子求一个结点的所有祖例如，书中例子求一个结点的所有祖先结点。先结点。665.5.1 5.5.

40、1 二叉树的基本运算概述二叉树的基本运算概述（Basic operations of binary tree)5.5.2 5.5.2 二叉树的基本运算算法实现二叉树的基本运算算法实现(Algorithm implementation of basic operations)5.5 5.5 二叉树的基本运算及其实现二叉树的基本运算及其实现(Algorithm implementation and basic operations (Algorithm implementation and basic operations of binary tree)of binary tree)67归纳起来归

41、纳起来,二叉树有以下基本运算：二叉树有以下基本运算： (1)创建二叉树创建二叉树CreateBTNode(*b,*str)：根据二叉根据二叉树括号表示法的字符串树括号表示法的字符串*str生成对应的链式存储结构生成对应的链式存储结构。 (2)查找结点查找结点FindNode(*b,x)：在二叉树在二叉树b中寻找中寻找data域值为域值为x的结点的结点,并返回指向该结点的指针。并返回指向该结点的指针。 (3)找孩子结点找孩子结点LchildNode(p)和和RchildNode(p)：分分别求二叉树中结点别求二叉树中结点*p的左孩子结点和右孩子结点的左孩子结点和右孩子结点。5.5.1 5.5.1

42、 二叉树的基本运算概述二叉树的基本运算概述（Basic operations of binary tree)68 (4)求高度求高度BTNodeDepth(*b)：求二叉树求二叉树b的高度。的高度。若二叉树为空若二叉树为空,则其高度为则其高度为0；否则；否则,其高度等于左子其高度等于左子树与右子树中的最大高度加树与右子树中的最大高度加l。 (5)输出二叉树输出二叉树DispBTNode(*b)：以括号表示法以括号表示法输出一棵二叉树。输出一棵二叉树。69 (1) 创建二叉树创建二叉树CreateBTNode(*b,*str) 用用ch扫描采用括号表示法表示二叉树的字符串。分扫描采用括号表示法表

43、示二叉树的字符串。分以下几种情况：以下几种情况： 若若ch=(：则将前面刚创建的结点作为双亲结点则将前面刚创建的结点作为双亲结点进栈进栈,并置并置k=1,表示其后创建的结点将作为这个结点的表示其后创建的结点将作为这个结点的左孩子结点；左孩子结点； 若若ch=)：表示栈中结点的左右孩子结点处理完表示栈中结点的左右孩子结点处理完毕毕,退栈；退栈； 若若ch=,：表示其后创建的结点为右孩子结点；表示其后创建的结点为右孩子结点；5.5.2 5.5.2 二叉树的基本运算算法实现二叉树的基本运算算法实现(Algorithm implementation of basic operations)70 其他情

44、况其他情况,表示要创建一个结点表示要创建一个结点,并根据并根据k值建立它与栈中结点之间的联系值建立它与栈中结点之间的联系, 当当k=1时时,表示这个结点作为栈中结点的左孩表示这个结点作为栈中结点的左孩子结点子结点,当当k=2时时,表示这个结点作为栈中结点的表示这个结点作为栈中结点的右孩子结点。如此循环直到右孩子结点。如此循环直到str处理完毕。处理完毕。 算法中算法中使用一个栈使用一个栈St保存双亲结点保存双亲结点,top为其栈为其栈指针指针,k指定其后处理的结点是双亲结点指定其后处理的结点是双亲结点(保存在保存在栈中栈中)的左孩子结点的左孩子结点(k=1)还是右孩子结点还是右孩子结点(k=2

45、)。71 void CreateBTNode(BTNode * &b,char *str) BTNode *StMaxSize,*p=NULL; int top=-1,k,j=0; char ch; b=NULL;/*建立的二叉树初始时为空建立的二叉树初始时为空*/ ch=strj; while (ch!=0) /*str未扫描完时循环未扫描完时循环*/ switch(ch) case (:top+;Sttop=p;k=1; break; /*为左孩子结点为左孩子结点*/ case ):top-;break; case ,:k=2; break; /*为孩子结点右结点为孩子结点右结点*

46、/72 default:p=(BTNode *)malloc(sizeof(BTNode); p-data=ch;p-lchild=p-rchild=NULL; if (b=NULL) /*p为二叉树的根结点为二叉树的根结点*/ b=p; else /*已建立二叉树根结点已建立二叉树根结点*/ switch(k) case 1:Sttop-lchild=p;break; case 2:Sttop-rchild=p;break; j+;ch=strj; 73 例如例如,对于括号表示串对于括号表示串A(B(D(,G),C(E,F),建立建立二叉树链式存储结构的过程如下表所示。二叉树链式存储结构的过

47、程如下表所示。ch算法执行的操作算法执行的操作St中元素中元素A建立建立A结点结点,b指向该结点指向该结点(A为树的根）为树的根） 空空(A结点进栈结点进栈,k=1AB建立建立B结点结点,因因k=1,将其作为将其作为A结点的左结点的左孩子结点孩子结点A(B结点进栈结点进栈,k=1ABD建立建立D结点结点,因因k=1,将其作为将其作为B结点的左结点的左孩子结点孩子结点AB74ch算法执行的操作算法执行的操作St中元素中元素(D结点进栈结点进栈,k=1ABD,k=2ABDG建立建立G结点结点,因因k=2,将其作为将其作为D结结点的右孩子结点点的右孩子结点ABD)退栈一次退栈一次AB)退栈一次退栈一

48、次A,k=2AC建立建立C结点结点,因因k=2,将其作为将其作为A结结点的右孩子结点点的右孩子结点A(C结点进栈结点进栈,k=1ACE建立建立E结点结点,因因k=1,将其作为将其作为C结结点的左孩子结点点的左孩子结点AC,k=2AC75ch算法执行的操作算法执行的操作St中元素中元素F建立建立F结点结点,因因k=2,将其作为将其作为C结点结点的右孩子结点的右孩子结点AC)退栈一次退栈一次A)退栈一次退栈一次空空ch扫描完毕扫描完毕算法结束算法结束 A B C D E F G 生成的二叉树生成的二叉树76 (2) 查找结点查找结点FindNode(*b,x) 采用采用先序遍历先序遍历递归算法查找

49、值为递归算法查找值为x的结点。找到后返的结点。找到后返回其指针回其指针,否则返回否则返回NULL。算法如下：。算法如下： BTNode *FindNode(BTNode *b, ElemType x) BTNode *p; if (b=NULL) return NULL; else if (b-data=x) return b; else p=FindNode(b-lchild,x); if (p!=NULL) return p; else return FindNode(b-rchild,x); 77 (3) 找孩子结点找孩子结点LchildNode(p)和和RchildNode(p) 直接

50、返回直接返回*p结点的左孩子结点或右孩子结点的指结点的左孩子结点或右孩子结点的指针。算法如下：针。算法如下： BTNode *LchildNode(BTNode *p) return p-lchild; BTNode *RchildNode(BTNode *p) return p-rchild; 78(4) 求高度求高度BTNodeDepth(*b)求二叉树的高度的递归模型求二叉树的高度的递归模型f()如下：如下： f(NULL)=0 f(b)=MAXf(b-lchild),f(b-rchild)+1 其他情况其他情况对应的算法如下：对应的算法如下：79int BTNodeDepth(BTNo

51、de *b) int lchilddep, rchilddep; if (b=NULL) return(0); /*空树的高度为空树的高度为0*/ else lchilddep=BTNodeDepth(b-lchild);/*求左子树的高度为求左子树的高度为lchilddep*/ rchilddep=BTNodeDepth(b-rchild);/*求右子树的高度为求右子树的高度为rchilddep*/ return(lchilddeprchilddep)? (lchilddep+1):(rchilddep+1); 80 (5) 输出二叉树输出二叉树DispBTNode(*b) 其过程是：其过程

52、是：对于非空二叉树对于非空二叉树b,先输出其元素值先输出其元素值,当当存在左孩子结点或右孩子结点时存在左孩子结点或右孩子结点时,输出一个输出一个“(”符号符号,然后递归处理左子树然后递归处理左子树,输出一个输出一个“,”符号符号,递归处理右递归处理右子树子树,最后输出一个最后输出一个“)”符号。符号。 对应的递归算法如下：对应的递归算法如下：81 void DispBTNode(BTNode *b) if (b!=NULL) printf(%c,b-data); if (b-lchild!=NULL | b-rchild!=NULL) printf(); DispBTNode(b-lchild

53、);/*递归处理左子树递归处理左子树*/ if (b-rchild!=NULL) printf(,); DispBTNode(b-rchild);/*递归处理右子树递归处理右子树*/ printf(); 82 Example 5.5 假设二叉树采用二叉链存储结构假设二叉树采用二叉链存储结构,设计设计一个算法输出从每个叶子结点到根结点的路径。一个算法输出从每个叶子结点到根结点的路径。 解：解：这里用层次遍历方法这里用层次遍历方法,设计的队列为非循环顺设计的队列为非循环顺序队列序队列(类似于第类似于第3章章3.2.4小节中求解迷宫问题时使用小节中求解迷宫问题时使用的队列的队列), 将所有已扫描过的

54、结点指针进队将所有已扫描过的结点指针进队,并在队列中并在队列中保存双亲结点的位置。保存双亲结点的位置。 当找到一个叶子结点时当找到一个叶子结点时,在队列中通过双亲结点的在队列中通过双亲结点的位置输出该叶子结点到根结点的路径。对应的算法如位置输出该叶子结点到根结点的路径。对应的算法如下：下： 83void AllPath(BTNode *b) struct snode BTNode *node;/*存放当前结点指针存放当前结点指针*/ int parent;/*存放双亲结点在队列中的位置存放双亲结点在队列中的位置*/ qMaxSize;/*定义顺序队列定义顺序队列*/ int front,rea

55、r,p;/*定义队头和队尾指针定义队头和队尾指针*/ front=rear=-1; /*置队列为空队列置队列为空队列*/ rear+;qrear.node=b; /*根结点指针进入队列根结点指针进入队列*/ qrear.parent=-1; /*根结点没有双亲结点根结点没有双亲结点*/84 while (frontlchild=NULL & b-rchild=NULL) printf(%c到根结点路径到根结点路径:,b-data); p=front; while (qp.parent!=-1) printf(%c-,qp.node-data); p=qp.parent; printf(

56、%cn,qp.node-data); if (b-lchild!=NULL) /*左孩子结点入队列左孩子结点入队列*/ rear+;qrear.node=b-lchild; qrear.parent=front; if (b-rchild!=NULL)/*右孩子结点入队列右孩子结点入队列*/ rear+; qrear.node=b-rchild; qrear.parent=front; /*end of while*/ 85 同一棵二叉树具有惟一先序序列、中序序列和同一棵二叉树具有惟一先序序列、中序序列和后序序列后序序列,但不同的二叉树可能具有相同的先序序列、但不同的二叉树可能具有相同的先序序

57、列、中序序列和后序序列。中序序列和后序序列。 例如例如, 教材中教材中P176 如图如图7.11所示的所示的5棵二叉树棵二叉树,先序序列都为先序序列都为ABC。 如图如图7.12所示的所示的5棵二叉树棵二叉树,中序序列都为中序序列都为ACB。 如图如图7.13所示的所示的5棵二叉树棵二叉树,后序序列都为后序序列都为CBA。 5.6 5.6 二叉树的构造二叉树的构造(Construction of binary tree)(Construction of binary tree)86 显然显然,仅由一个先序序列仅由一个先序序列(或中序序列、后序序列或中序序列、后序序列),无法确定这棵二叉树的树形

58、。无法确定这棵二叉树的树形。 如果同时知道一棵二叉树的先序序列和中序序列如果同时知道一棵二叉树的先序序列和中序序列,或者同时知道中序序列和后序序列或者同时知道中序序列和后序序列,就能确定这棵二叉就能确定这棵二叉树。树。 但是，同时知道先序序列和后序序列仍不能确定二但是，同时知道先序序列和后序序列仍不能确定二叉树的树形。如图叉树的树形。如图7.11和和7.13中除第一棵外的中除第一棵外的4棵二叉棵二叉树先序序列都是树先序序列都是ABC，后序序列都是，后序序列都是CBA。 87Theorem 5.1Theorem 5.1：任何：任何n(n0)n(n0)个不同结点的二又树个不同结点的二又树, ,都可

59、由它的中都可由它的中序序列和先序序列惟一地确定。序序列和先序序列惟一地确定。 采用数学归纳法证明。采用数学归纳法证明。 当当n=0时时,二叉树为空二叉树为空,结论正确。结论正确。 假设结点数小于假设结点数小于n的任何二叉树的任何二叉树,都可以由其先序序列和中序都可以由其先序序列和中序序列惟一地确定。序列惟一地确定。 已知某棵二叉树具有已知某棵二叉树具有n(n0)个不同结点个不同结点,其先序序列是其先序序列是a0a1an-1；中序序列是；中序序列是b0b1bk-1bkbk+1bn-1。 因为在先序遍历过程中因为在先序遍历过程中,访问根结点后访问根结点后,紧跟着遍历左子树紧跟着遍历左子树,最最后再

60、遍历右子树。所以后再遍历右子树。所以,a0必定是二叉树的根结点必定是二叉树的根结点,而且而且a0必然在必然在中序序列中出现。中序序列中出现。也就是说也就是说,在中序序列中必有某个在中序序列中必有某个bk(0kn-1)就是根结点就是根结点a0。88 由于由于bk是根结点是根结点,而在中序遍历过程中而在中序遍历过程中,先遍历左子先遍历左子树树,再访问根结点再访问根结点,最后再遍历右子树。最后再遍历右子树。所以在中序序列所以在中序序列中中,b0b1bk-1必是根结点必是根结点bk(也就是也就是a0)左子树的中序序左子树的中序序列列,即即bk的左子树有的左子树有k个结点个结点(注意注意,k=0表示结点表示结点bk没有没有左子树。左子树。