数据结构树课件.ppt

《数据结构树课件.ppt》由会员分享，可在线阅读，更多相关《数据结构树课件.ppt（168页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、引言引言:在前面几章里讨论的数据结构都属于线性结构，线在前面几章里讨论的数据结构都属于线性结构，线性结构的特点是逻辑结构简单，易于进行查找、插性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作，主要用于对客观世界中具有单一入和删除等操作，主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述。而现实中的许的前驱和后继的数据关系进行描述。而现实中的许多事物的关系并非如此简单，如人类社会的族谱、多事物的关系并非如此简单，如人类社会的族谱、各种社会组织机构以及城市交通、通讯等，这些事各种社会组织机构以及城市交通、通讯等，这些事物中的联系都是非线性的，采用非线性结构进行描物中的联系都是非线

2、性的，采用非线性结构进行描绘会更明确和便利。绘会更明确和便利。:所谓非线性结构，是指在该结构中至少存在一个数所谓非线性结构，是指在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后据元素，有两个或两个以上的直接前驱（或直接后继）元素。树结构和图结构是非常重要的非线性结继）元素。树结构和图结构是非常重要的非线性结构。构。-第六章第六章 树和二叉树树和二叉树F本章内容本章内容6.1 树的定义和基本术语6.2 二叉树6.2.1 二叉树的定义及基本运算6.2.2 二叉树的性质6.2.3 二叉树的存储结构6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树6.3.2 线索二叉树6.4 树

3、和森林6.4.1 树的存储结构6.4.2 森林与二叉树的转换及遍历6.6 赫夫曼树及应用6.6.1 赫夫曼树（最优二叉树）6.6.2 赫夫曼编码-6.1 树树树树是n个结点的有限集合(可以是空集)，在任一棵非空树中：（1）有且仅有一个称为根根的结点。（2）其余结点可分为互不相交的子集，而且这些子集本身又是一棵树，称为根的子树子树。JIACBDHGFEKLM-从逻辑结构看：从逻辑结构看：1）树中只有）树中只有树根没有父结点树根没有父结点；2）除根外，其余结点都有且仅一个父结点；）除根外，其余结点都有且仅一个父结点；3）树中的结点，可以有零个或多个）树中的结点，可以有零个或多个孩子结点孩子结点；4

4、)没有孩子的结点称为没有孩子的结点称为叶子结点叶子结点，或终端结点；，或终端结点；5）除根外的其他结点，都存在唯一一条从根到该结点的路径；）除根外的其他结点，都存在唯一一条从根到该结点的路径；JIACBDHGFEKLM-树的基本术语树的基本术语树的结点：树的结点：包含一个数据元素及若干指向子树的分支；包含一个数据元素及若干指向子树的分支；孩子结点：孩子结点：结点的子树的根称为该结点的孩子；结点的子树的根称为该结点的孩子；父结点：父结点：B是是A的孩子，则的孩子，则A是是B的父亲；的父亲；兄弟结点：兄弟结点：同一双亲的孩子结点；同一双亲的孩子结点；堂兄弟结点：堂兄弟结点：其父结点在同一层上的结点

5、；其父结点在同一层上的结点；祖先结点祖先结点:从根到该结点所经分支上的所有结点；从根到该结点所经分支上的所有结点；子孙结点：子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙；以某结点为根的子树中任一结点都称为该结点的子孙；结点的度结点的度:结点的孩子数目结点的孩子数目JIACBDHGFEKLM-树的基本运算树的基本运算n找树的根结点找树的根结点n求树的高度求树的高度n找指定结点的父结点找指定结点的父结点n找指定结点的孩子结点找指定结点的孩子结点n在树中插入、删除一个结点在树中插入、删除一个结点n遍历树遍历树n.JIACBDHGFEKLM-树的表示树的表示JIACBDHGFEKLMGCK

6、LEFBMHJIDA(a)(A(B(E(k,L),F),C(G),D(H(M),I(),J()(b)-6.2 二叉树二叉树n二叉树的定义：二叉树要么为空，要么由根结二叉树的定义：二叉树要么为空，要么由根结点、左子树和右子树组成。左、右子树本身也点、左子树和右子树组成。左、右子树本身也是二叉树。是二叉树。n注意：二叉树的子树有严格的左右之分，而树没有。ACBFEDG-二叉树的子树要区分左子树和右子树，即使只有一棵子树也要进行区分。这是二叉树与树的最主要的差别。下面列出了二叉树的5种基本形态，(c)和（d）是不同的两棵二叉树。(a)空二叉树AABABACB(b)只有根的二叉树(c)根和左子树(d)

7、根和右子树(e)根和左右子树二叉树的5种基本形式-6.2.2二叉树的性质二叉树的性质性质性质1 在二叉树的第在二叉树的第i层上至多有层上至多有2i-1个结点个结点性质性质2 深度为深度为k的二叉树至多有的二叉树至多有2k-1个结点个结点性质性质3任何一个二叉树中度为任何一个二叉树中度为2的结点数目的结点数目(n2)比度为比度为0的结点的结点数目数目(n0)少少1，即，即n2 n0-1。GGKJCFABE EIHD-6.2.2二叉树的性质二叉树的性质性质性质3任何一个二叉树中度为任何一个二叉树中度为2的结点数目的结点数目(n2)比比度为度为0的结点数目的结点数目(n0)少少1，即，即n2n0-1

8、。证证明明：设设二二叉叉树树上上叶叶结结点点数数为为n0，单单分分支支结结点点数数为为n1，双分支结点数为，双分支结点数为n2，则总结点数，则总结点数=n0+n1+n2。在在一一棵棵二二叉叉树树中中，所所有有结结点点的的分分支支数数(即即度度数数)应应等等于于单单分分支支结结点点数数加加上上双双分分支支结结点点数数的的2倍倍，即即总总的的分分支数支数=n1+2n2。由由于于二二叉叉树树中中除除根根结结点点以以外外，每每个个结结点点都都有有惟惟一一的的一一个个分分支支指指向向它它，因因此此二二叉叉树树中中：总总的的分分支支数数=总总结点数结点数-1。由上述三个等式可得：由上述三个等式可得：n1+

9、2n2=n0+n1+n2-1即：即：n0=n2+1-满二叉树和完全二叉树满二叉树和完全二叉树高度为3的满二叉树高度为3的一个完全二叉树高度为3的一个完全二叉树-完全二叉树完全二叉树高度为3的完全二叉树(a)(b)(c)(d)-满二叉树和完全二叉树满二叉树和完全二叉树高度为3的满二叉树高度为3的一个完全二叉树123456712345-二叉树的性质二叉树的性质(续续)性质性质4一个有一个有n个结点的完全二叉树的高度个结点的完全二叉树的高度Hlog(n)+1。证明：证明：设具有设具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为h，则根据性质，则根据性质3：深度为深度为h的二叉树至多有的二叉

10、树至多有2h-1个结点，因此，个结点，因此，n=2h-1综上，综上，2h-1=n2h，或，或h-1=log2nh即即h=log2n+1或或 log2n+1 证毕。证毕。-二叉树的性质二叉树的性质(续续)性质性质5完全二叉树中的某结点编号为完全二叉树中的某结点编号为i，则，则1)1)若有左孩子，则左孩编号为若有左孩子，则左孩编号为2i2i2 2）若有右孩子，则右孩子结点编号为）若有右孩子，则右孩子结点编号为2i+12i+13 3）若有双亲，则双亲结点编号为）若有双亲，则双亲结点编号为i/2i/2-6.2.3 二叉树的顺序存储二叉树的顺序存储n二叉树的顺序存储指的是用元素在数组中的下标表二叉树的顺

11、序存储指的是用元素在数组中的下标表示一个结点与其孩子和父结点的关系示一个结点与其孩子和父结点的关系.n完全二叉树的顺序存储完全二叉树的顺序存储E EDCFABA B C D E F12345678910 11 12#define MAX_TREE_SIZE 100typedef TelemType SqBiTreeMAX_TREE_SIZE;SqBiTree bt;-二叉树的顺序存储二叉树的顺序存储n非完全二叉树的顺序存储非完全二叉树的顺序存储E EGFCDABA B CD EF G12345678910 11 12 13 14 15 16F非完全二叉树不适合进行顺序存储非完全二叉树不适合进行

12、顺序存储-二叉树的链式存储二叉树的链式存储n一般用二叉链表存储二叉树一般用二叉链表存储二叉树(每个结点有两个指针域每个结点有两个指针域)E EGFCDABABCEDFGrootLchilddataRchildtypedef struct BiTNode TElemType data;struct BiTNode*Lchild,*Rchild;BiTNode,*BiTree;-二叉树的链式存储二叉树的链式存储n三叉链表存储三叉链表存储(每个节点有三个指针域每个节点有三个指针域)E EGFCDABABCEDFGrootLchilddataRchildParent-6.3 遍历二叉树和线索二叉树遍历

13、二叉树和线索二叉树n任何一个非空的二叉树都由三部分构成任何一个非空的二叉树都由三部分构成DLR根结点根的左子树根的右子树F树的遍历是访问树中每个结点仅一次的过程。遍历可以被树的遍历是访问树中每个结点仅一次的过程。遍历可以被认为是把所有的结点放在一条线上，或者将一棵树进行线认为是把所有的结点放在一条线上，或者将一棵树进行线性化的处理。性化的处理。-6.3.1 二叉树的遍历二叉树的遍历先左后右：DLR，LDR，LRDDLR根结点根的左子树根的右子树v先右后左：DRL，RDL，RLD-先序遍历先序遍历nDLR：访问根结点、先序遍历左子树、先序遍历右子树DLR123-先序遍历先序遍历nDLR：访问根结

14、点、先序遍历左子树、先序遍历右子树若二叉树非空 （1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树；若二叉树为空，结束 基本项（也叫终止项）若二叉树非空 递归项 （1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树；DLR-voidpreorder(BiTNode*root)/先序遍历root指向根的二叉树 if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if /preorder先序遍历先序遍历LchilddataRchildE ECD

15、ABABCEDroot-voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if /preorderBACEDGFroot先序遍历序列：root:A-voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if /preor

16、derBACEDGFroot先序遍历序列：Aroot:A-voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if /preorderBACEDGFrootroot:Broot:A先序遍历序列：A B-voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rc

17、hild);/先序遍历根的右子树/if /preorderBACEDGFrootroot:Broot:A先序遍历序列：A Broot:DD -voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if /preorderBACEDGFrootroot:Broot:A先序遍历序列：A Broot:DD root:NULL-Dvoidpreorder(BiTNode*root)if(root!=NULL)cout

18、data；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if /preorderBACEDGFrootroot:Broot:A先序遍历序列：A Broot:DD -voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if /preorderBACEDGFrootroot:Broot:A先序遍历序列：A Broo

19、t:DD root:NULL-Dvoidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if /preorderBACEDGFrootroot:Broot:A先序遍历序列：A Broot:DD -E Evoidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchi

20、ld);/先序遍历根的右子树/if /preorderBACDGFrootroot:Broot:A先序遍历序列：A B Droot:EE-Gvoidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if /preorderBACEDGFrootroot:Broot:A先序遍历序列：A B Droot:EEGroot:G-Evoidpreorder(BiTNode*root)if(root!=NULL)coutda

21、ta；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if /preorderBACEDGFrootroot:Broot:A先序遍历序列：A B Droot:EEG-Bvoidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if /preorderBACEDGFrootroot:Broot:A先序遍历序列：A B D

22、EG-Avoidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if /preorderBACEDGFrootroot:A先序遍历序列：A B DEG-Cvoidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if /preor

23、derBACEDGFrootroot:A先序遍历序列：A B DEGroot:CC-voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if /preorderBACEDGFrootroot:A先序遍历序列：A B DEGroot:CC root:NULL-Cvoidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild

24、);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if /preorderBACEDGFrootroot:A先序遍历序列：A B DEGroot:CC-Fvoidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if /preorderBACEDGFrootroot:A先序遍历序列：A B DEGroot:CCroot:FF-Cvoidpreorder(BiTNode*r

25、oot)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if /preorderBACEDGFrootroot:A先序遍历序列：A B DEGroot:CCF-Avoidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if /preorderBACEDGFrootroot

26、:A先序遍历序列：A B DEGCF-voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if /preorderBACEDGFroot先序遍历序列：A B DEGCF-先序遍历过程先序遍历过程BACEDGF先序遍历序列：先序遍历序列：A B DEG C FABDEGCF递归调用递归调用返回返回voidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点pr

27、eorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if /preorder-root:Aroot:Broot:Eroot:G栈在先序遍历中的作用栈在先序遍历中的作用BACEDGFroot先序遍历序列：A B DEGn栈用于保存当前结点的祖先结点栈用于保存当前结点的祖先结点-中序遍历中序遍历nLDR：中序遍历左子树、访问根结点、中序遍历右子树DLR213-中序遍历中序遍历nLDR：中序遍历左子树、访问根结点、中序遍历右子树若二叉树非空 （1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树；若二叉树为空，结束 基

28、本项（也叫终止项）若二叉树非空 递归项 （1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树；DLR-voidinorder(BiTNode*root)/中序遍历root指向根的二叉树 if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树 coutdata；/访问根结点 inorder(root-Rchild);/中序遍历根的右子树/if /inorder中序遍历中序遍历LchilddataRchild-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树cou

29、tdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:A-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:Aroot:B-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/

30、中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:Aroot:Broot:D -voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:Aroot:Broot:D root:NULL-voidinorder(BiTNode*

31、root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:Aroot:Broot:D D-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:Ar

32、oot:Broot:D Droot:NULL-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:Aroot:Broot:D D-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍

33、历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:Aroot:BD B-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:Aroot:BD Broot:E-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/

34、访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:Aroot:BD Broot:Eroot:G-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:Aroot:BD Broot:Eroot:Groot:NULL-voidinorder(BiTNode*roo

35、t)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:Aroot:BD Broot:Eroot:G G-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：r

36、oot:Aroot:BD Broot:EG E-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:Aroot:BD B G E-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍

37、历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:AD B G E A-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:AD B G E Aroot:C-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/

38、访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:AD B G E Aroot:C root:NULL-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:AD B G E Aroot:C C-voidinorder(BiTNode*root)if(root

39、!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:AD B G E Aroot:CCroot:F-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:AD B G

40、 E Aroot:C Croot:Froot:NULL-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:AD B G E Aroot:CCroot:F F-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(ro

41、ot-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:AD B G E Aroot:CC F-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：root:AD B G E A C F-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild

42、);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inorderBACEDGFroot中序遍历序列：D B G E A C F-BACEDGFrootroot:Aroot:Broot:Eroot:G 栈在中序遍历中的作用栈在中序遍历中的作用中序遍历序列：D B Gn栈用于保存当前结点的祖先结点栈用于保存当前结点的祖先结点-后序遍历后序遍历nLRD：后序遍历左子树、后序遍历右子树、访问根结点DLR312E EGFCDAB后序后序遍历序列:BDFGECA-voidinorder(BiTNode*root)if(root!=

43、NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树/if /inordervoidpreorder(BiTNode*root)if(root!=NULL)coutdata；/访问根结点preorder(root-Lchild);/先序遍历根的左子树 preorder(root-Rchild);/先序遍历根的右子树/if/preordervoidpostorder(BiTNode*root)if(root!=NULL)postorder(root-Lchild);/后序遍历根的左子树

44、后序遍历根的左子树postorder(root-Rchild);/后序遍历根的右子树后序遍历根的右子树coutdata；/访问根结点访问根结点/if/postorder-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rchild);/中序遍历根的右子树中序遍历根的右子树/if/inorderBACEDGFrootroot:Aroot:Broot:EE中序遍历序列：中序遍历序列：D B GvoidInOrder(BiTNode*root)InitS

45、tack(S);Push(S,root);/根指针进栈 while(!StackEmpty(S)while(GetTop(S,p)&p)Push(S,p-Lchild);/向左走到头向左走到头Pop(S,p);/空指针退栈空指针退栈if(!StackEmpty(S)Pop(S,p);coutdata;/访问结点访问结点Push(S,p-Rchild);/向右向右/if/while/InOrder-voidinorder(BiTNode*root)if(root!=NULL)inorder(root-Lchild);/中序遍历根的左子树coutdata；/访问根结点inorder(root-Rc

46、hild);/中序遍历根的右子树中序遍历根的右子树/if/inorderBACEDGFrootroot:Aroot:Broot:EE中序遍历序列：中序遍历序列：D B GvoidInOrder(BiTNode*root)InitStack(S);p=root;/根指针进栈 while(p|!StackEmpty(S)if(p)Push(S,p);p=p-Lchild;else/根指针退栈，访问根结点，遍历右子树根指针退栈，访问根结点，遍历右子树Pop(S,p);coutdata;p=p-Rchild;/if-else/while/InOrder-用二叉树表示表达式用二叉树表示表达式na+b*(

47、c d)e/ff f/e-+*a-bd dc先序先序遍历序列:+a*b c d/e f中序中序遍历序列:a+b*c d e/f后序后序遍历序列:a b c d *+e f /F表达式的前缀、中缀和后缀表示表达式的前缀、中缀和后缀表示-用栈对后缀表达式求值用栈对后缀表达式求值表达式的表达式的后缀表示后缀表示:a b c d *+e f /bacdbat1t2at1=c dt2=b*t1t3=a+t2t3et3ft4=e/ft4t3t5t5=t3 t4-层序遍历层序遍历n先根，后子树；先左子树，后右子树E EGFCDAB队列队头树根结点A入队层序层序遍历序列:-层序遍历层序遍历E EGFCDAB队

48、列队头A层序层序遍历序列:A出队n先根，后子树；先左子树，后右子树-层序遍历层序遍历n先根，后子树；先左子树，后右子树E EGFCDAB队列队头根结点B、C入队A的子树层序层序遍历序列:A-层序遍历层序遍历n先根，后子树；先左子树，后右子树E EGFCDAB队列队头BB出队C层序层序遍历序列:A-层序遍历层序遍历n先根，后子树；先左子树，后右子树E EGFCDAB队列队头C根结点入队B的子树层序层序遍历序列:AB-层序遍历层序遍历n先根，后子树；先左子树，后右子树E EGFCDAB队列队头CC出队层序层序遍历序列:AB-层序遍历层序遍历n先根，后子树；先左子树，后右子树E EGFCDAB队列队

49、头根结点入队C的子树层序层序遍历序列:ABC-层序遍历层序遍历n先根，后子树；先左子树，后右子树E EGFCDAB队列队头DED出队层序层序遍历序列:ABC-层序遍历层序遍历n先根，后子树；先左子树，后右子树E EGFCDAB队列队头E根结点入队D的子树层序层序遍历序列:ABCD-层序遍历层序遍历n先根，后子树；先左子树，后右子树E EGFCDAB队列队头EE出队层序层序遍历序列:ABCD-层序遍历层序遍历n先根，后子树；先左子树，后右子树E EGFCDAB队列队头根结点F、G入队E的子树层序层序遍历序列:ABCDE-层序遍历层序遍历n先根，后子树；先左子树，后右子树E EGFCDAB队列队头

50、FGF出队层序层序遍历序列:ABCDE-层序遍历层序遍历n先根，后子树；先左子树，后右子树E EGFCDAB队列队头G根结点入队F的子树层序层序遍历序列:ABCDEF-层序遍历层序遍历n先根，后子树；先左子树，后右子树E EGFCDAB队列队头GG出队层序层序遍历序列:ABCDEF-层序遍历层序遍历n先根，后子树；先左子树，后右子树E EGFCDAB层序层序遍历序列:ABCDEFG利用队列实现二叉树的层序遍历：构造一个空队列；树根结点入队列；while（队列不空）队头元素出队列；访问结点；刚出队的结点的左孩子、右孩子结点先后入队列；-6.3.2 线索二叉树线索二叉树Ltag=Lchilddat