数据结构与算法第四章清华大学出版社赵玉兰.ppt

《数据结构与算法第四章清华大学出版社赵玉兰.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法第四章清华大学出版社赵玉兰.ppt（130页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第4章章 树与二叉树树与二叉树4.1 树的定义和基本术语树的定义和基本术语4.2 二叉树二叉树4.3 树与森林树与森林4.4 森林与二叉树的关系森林与二叉树的关系4.5 Huffman 树与编码树与编码24.1 树（树（Tree）的定义和基本术语）的定义和基本术语树形结构是一种非线性结构，应用十分广泛树形结构是一种非线性结构，应用十分广泛u例如，行政机构、家谱、磁盘目录等例如，行政机构、家谱、磁盘目录等内蒙古大学内蒙古大学理工学院理工学院计算机学院计算机学院生命科学学院生命科学学院外国语学院外国语学院人文学院人文学院数数学学系系物物理理系系电电子子系系计计算算机机系系计计算算中中心心网网络络

2、中中心心汉汉语语系系历历史史系系哲哲学学系系生生物物系系环环境境系系动动物物中中心心生生物物工工程程中中心心资资源源所所英英语语系系日日语语系系 行政机构行政机构34.1 树（树（Tree）的定义和基本术语）的定义和基本术语u磁盘目录磁盘目录44.1 树（树（Tree）的定义和基本术语）的定义和基本术语树的定义树的定义 树是由树是由 n（n 0）个结点组成的有限集合）个结点组成的有限集合u如果如果n0，称为空树，称为空树u如果如果n 0，则：，则：有一个特定的称之为根（有一个特定的称之为根（root）的结点，它只有直接后）的结点，它只有直接后继，但没有直接前驱；继，但没有直接前驱；除根以外的其

3、它结点划分为除根以外的其它结点划分为m（m 0）个互不相交的有）个互不相交的有限集合限集合 T0,T1,Tm-1，每个集合又是一棵树，并且称，每个集合又是一棵树，并且称之为根的子树（之为根的子树（subTree）。每棵子树的根结点有且仅）。每棵子树的根结点有且仅有一个直接前驱，但可以有有一个直接前驱，但可以有0个或多个直接后继。个或多个直接后继。树的定义具有递归性树的定义具有递归性54.1 树（树（Tree）的定义和基本术语）的定义和基本术语例，例，Tree=(D,R)uD=Book,C1,C2,C3,S1.1,S1.2,S2.1,S2.2,S2.3,S2.1.1,S2.1.2 uR=,Boo

4、k C1 C2 C3 S1.1 S1.2 S2.1 S2.2 S2.3 S2.1.1 S2.1.2 ChapterSectionSection64.1 树（树（Tree）的定义和基本术语）的定义和基本术语树的术语树的术语结点结点(node)结点的度结点的度(degree)分支分支(branch)结点结点叶叶(leaf)结点结点子女子女(child)结点结点双亲双亲(parent)结点结点兄弟兄弟(sibling)结点结点祖先祖先(ancestor)结点结点子孙子孙(descendant)结点结点结点所处层次结点所处层次(level)树的高度树的高度(depth)树的度树的度(degree)有序

5、树有序树 无序树无序树 森林森林74.1 树（树（Tree）的定义和基本术语）的定义和基本术语术语主要来源于家谱和树术语主要来源于家谱和树u双亲、子女（双亲、子女（parent，child）若若 R，则称，则称a是是b的双亲，的双亲，b是是a的子女（孩子）的子女（孩子）u结点的度（结点的度（degree）结点所拥有的子女数结点所拥有的子女数u叶（叶（leaf）结点）结点度为度为0的结点的结点u分枝结点（分枝结点（branch node）度大于度大于0的结点的结点u树的度（树的度（degree）树中最大的结点度树中最大的结点度84.1 树（树（Tree）的定义和基本术语）的定义和基本术语u结点所

6、在的层次（结点所在的层次（level）树根的层次为树根的层次为1其它任一结点所在的层次是其双亲的层次加其它任一结点所在的层次是其双亲的层次加1u深度或高度（深度或高度（depth）结点所在的层次的最大层数结点所在的层次的最大层数12345u兄弟（兄弟（sibling）具有同一双亲的结点互称具有同一双亲的结点互称兄弟兄弟u堂兄弟（堂兄弟（cousin）在同层的非兄弟结点互称在同层的非兄弟结点互称堂兄弟堂兄弟94.1 树（树（Tree）的定义和基本术语）的定义和基本术语u祖先、子孙（祖先、子孙（descendant，ancestor）一个结点是它所有子树中的结点的祖先，这些结点是它一个结点是它所有

7、子树中的结点的祖先，这些结点是它的子孙的子孙u路径（路径（path）是一结点序列是一结点序列 n1,n2,n3,nk，并且前，并且前1个结点是后个结点是后1个个结点的双亲结点的双亲它的长度是它的长度是 k-1u有序树（有序树（ordered tree）每个结点的子女由左到右是有次序的；否则是无序树每个结点的子女由左到右是有次序的；否则是无序树ABCACB无序无序有序有序104.1 树（树（Tree）的定义和基本术语）的定义和基本术语ABCDEFGHIJKLM结点结点A的度：的度：3结点结点B的度：的度：2结点结点M的度：的度：0叶子：叶子：K，L，F，G，M，I，J结点结点A的孩子：的孩子：B

8、，C，D结点结点B的孩子：的孩子：E，F结点结点I的双亲：的双亲：D结点结点L的双亲：的双亲：E结点结点B，C，D为兄弟为兄弟结点结点K，L为兄弟为兄弟树的度：树的度：3结点结点A的层次：的层次：1结点结点M的层次：的层次：4树的高度：树的高度：4结点结点A是结点是结点F、G的祖先的祖先114.1 树（树（Tree）的定义和基本术语）的定义和基本术语u森林（森林（Forest）是是 m（m 0）棵互不相交的树的集合）棵互不相交的树的集合ArootBCDEFGHIJMKLF124.2 二叉树二叉树ADT二叉树二叉树二叉树（二叉树（Binary Tree）u是有限个结点的集合（可以为空是有限个结点

9、的集合（可以为空）u当二叉树非空时，其中有且仅有一个称为根的结当二叉树非空时，其中有且仅有一个称为根的结点，余下的结点（如果有的话）被分为两棵互不点，余下的结点（如果有的话）被分为两棵互不相交的二叉树，分别称为根的左子树和右子树相交的二叉树，分别称为根的左子树和右子树134.2 二叉树二叉树ADT二叉树二叉树例例ABCDEFGHK根结点根结点左子树左子树右子树右子树注意：二叉树不是树，它是另外单独定义的一种树形注意：二叉树不是树，它是另外单独定义的一种树形注意：二叉树不是树，它是另外单独定义的一种树形注意：二叉树不是树，它是另外单独定义的一种树形结构，并非一般树的特例。它的子树有顺序规定，分结

10、构，并非一般树的特例。它的子树有顺序规定，分结构，并非一般树的特例。它的子树有顺序规定，分结构，并非一般树的特例。它的子树有顺序规定，分为左子树和右子树，不能随意颠倒。为左子树和右子树，不能随意颠倒。为左子树和右子树，不能随意颠倒。为左子树和右子树，不能随意颠倒。144.2 二叉树二叉树ADT二叉树二叉树二叉树的二叉树的5种基本形态种基本形态 空空 只有根只有根 右子树空右子树空 左子树空左子树空 左、右子树非空左、右子树非空问题：具有问题：具有3 3个结点的二叉树可能有几种不同形态？个结点的二叉树可能有几种不同形态？154.2 二叉树二叉树ADT二叉树二叉树ADT二叉树的定义二叉树的定义AD

11、T BinaryTree is Data 是有限个结点的集合是有限个结点的集合D。当。当D非空时，其中有一根结点非空时，其中有一根结点t，余下的结点被分为余下的结点被分为t的左子树和右子树。的左子树和右子树。Operations Constructor Process：建立一棵空二叉树：建立一棵空二叉树 Delete Process：删除二叉树：删除二叉树 IsEmpty Process：判断二叉树是否是空：判断二叉树是否是空 Output：若二叉树为空，则返回：若二叉树为空，则返回true，否则返回，否则返回false164.2 二叉树二叉树ADT二叉树二叉树 Size Process：计算

12、二叉树的结点数：计算二叉树的结点数size Output：size Height Process：计算二叉树的高度：计算二叉树的高度height Output：height Root Process：x Output：置二叉树的根结点的值为：置二叉树的根结点的值为x Parent Input：node是二叉树中的一个结点是二叉树中的一个结点 Process：求：求node的双亲的双亲p，若，若node 是根，则是根，则p为空为空 Output：p 174.2 二叉树二叉树ADT二叉树二叉树 CreateBinaryTree Input：二叉树的某种形式的定义：二叉树的某种形式的定义defini

13、tion Process：根据此定义：根据此定义definition构造二叉树构造二叉树 MakeTree Input：data是根结点值，是根结点值，left是左子树，是左子树，right是右子树是右子树 Process：创建二叉树，：创建二叉树，data是根结点值，是根结点值，left是其左子是其左子 树，树，right是其右子树是其右子树 BreakTree Process：拆分二叉树，：拆分二叉树，data是根结点数据，是根结点数据，left是左子树，是左子树，right是右子树是右子树 Output：data，left，right PreOrder Input：Visit()是结点访

14、问函数是结点访问函数 Process：按前序遍历对二叉树中每个结点调用：按前序遍历对二叉树中每个结点调用Visit()1次且仅次且仅1次次 Output：根据：根据Visit()，按前序遍历序列得到结果，按前序遍历序列得到结果184.2 二叉树二叉树ADT二叉树二叉树 InOrder Input：Visit()是结点访问函数是结点访问函数 Process：按中序遍历对二叉树中每个结点调用：按中序遍历对二叉树中每个结点调用Visit()1次且仅次且仅1次次 Output：根据：根据Visit()，按中序遍历序列得到结果，按中序遍历序列得到结果 PostOrder Input：Visit()是结点

15、访问函数是结点访问函数 Process：按后序遍历对二叉树中每个结点调用：按后序遍历对二叉树中每个结点调用Visit()1次且仅次且仅1次次 Output:根据根据Visit()，按后序遍历序列得到结果，按后序遍历序列得到结果 LevelOrder Input：Visit()是结点访问函数是结点访问函数 Process：按层次对二叉树中每个结点调用：按层次对二叉树中每个结点调用Visit()1次且仅次且仅1次次 Output：根据：根据Visit()，按层次遍历序列得到结果，按层次遍历序列得到结果 ADT BinaryTree 194.2 二叉树二叉树二叉树的性质二叉树的性质性质性质1u在二叉

16、树的第在二叉树的第 i 层最多有层最多有 2i-1 个结点（个结点（i 1 1）。）。用归纳法证明：用归纳法证明：归纳基：归纳基：归纳假设：归纳假设：归纳证明：归纳证明：i=1 层时，只有一个根结点，层时，只有一个根结点，2i-1=20=1i=k-1（1k i）时命题成立时命题成立i=k 时，二叉树上每个结点至多有两棵时，二叉树上每个结点至多有两棵子树，则第子树，则第 i 层的结点数层的结点数=2k-2 2=2k-2+1=2k-1=2i-1 204.2 二叉树二叉树二叉树的性质二叉树的性质性质性质2 u高度为高度为 k 的二叉树最多有的二叉树最多有 2k1个结点。（个结点。（k 1）证明：证明

17、：基于上一条性质，深度为基于上一条性质，深度为 k 的二叉树上的结点的二叉树上的结点数至多为数至多为 20+21+2k-1=2k-1 214.2 二叉树二叉树二叉树的性质二叉树的性质性质性质3 u任一二叉树，若其叶结点个数为任一二叉树，若其叶结点个数为 n0，度为，度为2的非叶的非叶结点个数为结点个数为 n2，则，则 n0n21证明：证明：若设度为若设度为1的结点有的结点有 n1 个，总结点个数为个，总结点个数为n，则则 n=n0+n1+n2 再设总边数为再设总边数为e，则根据二叉树的定义，则根据二叉树的定义，e=2n2+n1=n-1 因此，有因此，有 2n2+n1=n0+n1+n2-1 n2

18、=n0-1 n0=n2+1 224.2 二叉树二叉树二叉树的性质二叉树的性质性质性质4 u具有具有 n 个结点的二叉树的高度最小为个结点的二叉树的高度最小为 log2(n+1)证明：由性质证明：由性质2，高度为，高度为 h 的二叉树最多有的二叉树最多有 2h-1个结个结 点，即点，即 n 2h-1 因此因此 hlog2(n+1)因为因为 h 只能是整数，所以，只能是整数，所以，h log2(n+1)注：注：x x ：表示不小于：表示不小于x的最小整数的最小整数 x x ：表示不大于：表示不大于x的最大整数的最大整数234.2 二叉树二叉树二叉树的性质二叉树的性质满二叉树（满二叉树（Full B

19、inary Tree）u每一层的结点数都达到了最大的二叉树每一层的结点数都达到了最大的二叉树完全二叉树（完全二叉树（Complete Binary Tree）u若设二叉树的高度为若设二叉树的高度为h，除第，除第h层外，其它各层层外，其它各层（0h-1）的结点数都达到最大个数，第）的结点数都达到最大个数，第 h 层从右层从右向左连续缺若干结点，这就是完全二叉树向左连续缺若干结点，这就是完全二叉树A15234678 9 10BCDEFGH I JA15234678910BCDEFGHIJKLM N O1112 13 14 15244.2 二叉树二叉树二叉树的性质二叉树的性质性质性质5 u在编号的完

20、全二叉树中，有以下关系：在编号的完全二叉树中，有以下关系：若若i=1，则，则 i 无双亲无双亲 若若i1，则，则 i 的双亲的编号为的双亲的编号为 i/2 若若2*in，则，则 i 的左子女的编号为的左子女的编号为 2*i 若若2*i+1n，则，则 i 的右子女的编号为的右子女的编号为 2*i+1若若 i 为偶数，且为偶数，且in，则其右兄弟的编号为，则其右兄弟的编号为 i+1 若若 i 为奇数，且为奇数，且i1，则其左兄弟的编号为，则其左兄弟的编号为 i-1254.2 二叉树二叉树二叉树的实现二叉树的实现顺序存储表示顺序存储表示u完全二叉树的顺序存储表示完全二叉树的顺序存储表示根据性质根据性

21、质5：STi 的的双亲双亲是是ST i i/2/2 ,左子女左子女是是ST2*i，右子女右子女是是ST2*i+1。123456789 1011121 23 456789 10 11 12264.2 二叉树二叉树二叉树的实现二叉树的实现u一般二叉树的顺序存储表示一般二叉树的顺序存储表示注：注：注：注：由于一般二叉树必由于一般二叉树必由于一般二叉树必由于一般二叉树必须仿照完全二叉树那样须仿照完全二叉树那样须仿照完全二叉树那样须仿照完全二叉树那样存储，可能会浪费很多存储，可能会浪费很多存储，可能会浪费很多存储，可能会浪费很多存储空间，单支树就是存储空间，单支树就是存储空间，单支树就是存储空间，单支树

22、就是一个极端情况。一个极端情况。一个极端情况。一个极端情况。1346789131521 2 3 4 5 6 7 8 9 10 11 12 13 14 15274.2 二叉树二叉树二叉树的实现二叉树的实现链表存储表示链表存储表示284.2 二叉树二叉树二叉树的实现二叉树的实现u例例294.2 二叉树二叉树二叉树的实现二叉树的实现u二叉链表结点类的定义二叉链表结点类的定义class BinaryTreeNode DataType data;BinaryTreeNode*leftChild,*rightChild;/左、右指针左、右指针 public:BinaryTreeNode(DataType&

23、e,BinaryTreeNode *l=NULL,BinaryTreeNode*r=NULL)data=e;leftChild=l;rightChild=r;/BinaryTreeNode 304.2 二叉树二叉树二叉树的实现二叉树的实现u二叉链表类的定义二叉链表类的定义class BinaryTree BinaryTreeNode*root;/根结点指针根结点指针 public:BinaryTree()root=NULL;/创建一个空的二叉树；创建一个空的二叉树；bool IsEmpty();/如果二叉树为空，则返回如果二叉树为空，则返回true，否则返，否则返 回回false bool R

24、oot(DataType&x);/置置x为根结点值；若操作失败，为根结点值；若操作失败，则返回则返回false，否则返回，否则返回true void CreateBinaryTree(BinaryTreeNode*&t=root);/通过扩充二叉树的前序遍历序列，创建二叉树通过扩充二叉树的前序遍历序列，创建二叉树 void MakeTree(DataType&data，BinaryTree&left，BinaryTree&right);/创建二叉树，创建二叉树，data为根结点为根结点 值，值，left作为左子树，作为左子树，right作为右子树作为右子树314.2 二叉树二叉树二叉树的实现二

25、叉树的实现void BreakTree(DataType&data，BinaryTree&left，BinaryTree&right);/拆分二叉树拆分二叉树void PreOrder(void Visit(BinaryTreeNode*&),BinaryTreeNode*&=root);void InOrder(void Visit(BinaryTreeNode*&),BinaryTreeNode*&=root);void PostOrder(void Visit(BinaryTreeNode*&),BinaryTreeNode*&=root);void LevelOrder(void Vi

26、sit(BinaryTreeNode*&);/逐层遍历逐层遍历void Delete(BinaryTreeNode*&=root);/删除一棵二叉树，删除一棵二叉树，释放其结点释放其结点int Size(BinaryTreeNode*&=root);/返回二叉树中结点数返回二叉树中结点数int Height(BinaryTreeNode*&=root);/返回二叉树的高度返回二叉树的高度;/BinaryTree324.2 二叉树二叉树二叉树的实现二叉树的实现u基本操作的实现基本操作的实现判断二叉树是否为空判断二叉树是否为空bool IsEmpty()return(root?false:true

27、);置置x为根结点的值，如果没有根结点，则返回为根结点的值，如果没有根结点，则返回falsebool Root(DataType&x)if(root)root-data=x;return true;return false;/没有根结点没有根结点334.2 二叉树二叉树二叉树的实现二叉树的实现用用 left、right 和和 data 构成一棵新树构成一棵新树void MakeTree(DataType&data,BinaryTree&left,BinaryTree&right)/left,right与当前二叉树必须是不同的对象与当前二叉树必须是不同的对象 root=new BinaryTre

28、eNode(data,left.root,right.root);/创建新二叉树创建新二叉树 left.root=right.root=NULL344.2 二叉树二叉树二叉树的遍历二叉树的遍历二叉树的遍历（二叉树的遍历（Traversing Binary Tree）u遵从某种次序，遍访二叉树中的所有结点，要求遵从某种次序，遍访二叉树中的所有结点，要求每个结点访问一次且仅访问一次。每个结点访问一次且仅访问一次。“访问访问”的含义可以很广，如：输出结点的信息等。的含义可以很广，如：输出结点的信息等。设设访问根结点访问根结点 记作记作 V 遍历根的左子树遍历根的左子树 记作记作 L 遍历根的右子树遍

29、历根的右子树 记作记作 R 则可能的遍历次序有则可能的遍历次序有 前序前序 VLR 镜像镜像 VRL 中序中序 LVR 镜像镜像 RVL 后序后序 LRV 镜像镜像 RLVVLR123354.2 二叉树二叉树二叉树的遍历二叉树的遍历前序遍历二叉树（前序遍历二叉树（Preorder Traversal）u若二叉树为空，则空操作；若二叉树为空，则空操作；u否则否则访问根结点访问根结点(V)；前序遍历左子树前序遍历左子树(L)；前序遍历右子树前序遍历右子树(R)。u例例遍历结果遍历结果 -+a*b-c d/e f364.2 二叉树二叉树二叉树的遍历二叉树的遍历中序遍历（中序遍历（Inorder Tr

30、aversal）u若二叉树为空，则空操作；若二叉树为空，则空操作；u否则否则中序遍历左子树中序遍历左子树(L)；访问根结点访问根结点(V)；中序遍历右子树中序遍历右子树(R)。u例例遍历结果遍历结果 a+b*c-d-e/f374.2 二叉树二叉树二叉树的遍历二叉树的遍历后序遍历（后序遍历（Postorder Traversal）u若二叉树为空，则空操作；若二叉树为空，则空操作；u否则否则后序遍历左子树后序遍历左子树(L)；后序遍历右子树后序遍历右子树(R)；访问根结点访问根结点(V)。u例例遍历结果遍历结果 a b c d-*+e f/-384.2 二叉树二叉树二叉树的遍历二叉树的遍历例例AB

31、CEFHGABCEFHG前序遍历序列：前序遍历序列：A B E H G C F中序遍历序列：中序遍历序列：ABCEFHGE B G H A F C后序遍历序列：后序遍历序列：ABCEFHGE G H B F C A394.2 二叉树二叉树二叉树的遍历二叉树的遍历前序遍历的递归算法前序遍历的递归算法outType PreOrder(outType visit(BinaryTreeNode*&),BinaryTreeNode*&t=root)/前序遍历前序遍历 if(t)Visit(t);PreOrder(Visit,t-leftChild);PreOrder(Visit,t-rightChild

32、);/preorder404.2 二叉树二叉树二叉树的遍历二叉树的遍历中序遍历的递归算法中序遍历的递归算法outType InOrder(outType visit(BinaryTreeNode*&),BinaryTreeNode*&t=root)/中序遍历中序遍历 if(t)InOrder(Visit,t-leftChild);Visit(t);InOrder(Visit,t-rightChild);/preorder414.2 二叉树二叉树二叉树的遍历二叉树的遍历u中序遍历二叉树的递归过程图解中序遍历二叉树的递归过程图解424.2 二叉树二叉树二叉树的遍历二叉树的遍历后序遍历的递归算法后序

33、遍历的递归算法outType PostOrder(outType visit(BinaryTreeNode*&),BinaryTreeNode*&t=root)/后序遍历后序遍历 if(t)PostOrder(Visit,t-leftChild);PostOrder(Visit,t-rightChild);Visit(t);/preorder434.2 二叉树二叉树二叉树的遍历二叉树的遍历建立二叉树建立二叉树u以以前序遍历序列前序遍历序列建立二叉树建立二叉树u说明：二叉树用根字符序列和左右子树的字符序说明：二叉树用根字符序列和左右子树的字符序列表示，空树用空格（或某一字符，如列表示，空树用空格

34、（或某一字符，如0）表示）表示DBFEAC该扩充二叉树的前序遍历序列该扩充二叉树的前序遍历序列ABD00EF000C00 (字符序列与二叉树一一对应）字符序列与二叉树一一对应）该算法是一递归算法，递归三要素：该算法是一递归算法，递归三要素：1.递归出口：当遇到递归出口：当遇到0时，是空树。时，是空树。2.若不是若不是0，创建根结点；，创建根结点；3.建立根的左子树和右子树；建立根的左子树和右子树；444.2 二叉树二叉树二叉树的遍历二叉树的遍历u以前序遍历序列建立二叉树的算法以前序遍历序列建立二叉树的算法void CreateBinaryTree(BinaryTreeNode*&t=root)

35、DataType u;cinu;if(!u)t=NULL;else t=new BinaryTreeNode(u);CreateBinaryTree(t-leftChild);CreateBinaryTree(t-rightChild);454.2 二叉树二叉树二叉树的遍历二叉树的遍历u例例00 00 0A BCDATBCD464.2 二叉树二叉树二叉树的遍历二叉树的遍历若已知一棵二叉树的前序（或中序，或后序，或若已知一棵二叉树的前序（或中序，或后序，或层序）序列，能否唯一确定这棵二叉树呢？层序）序列，能否唯一确定这棵二叉树呢？ABC例：已知前序序列为例：已知前序序列为ABC，则可能的二叉树有

36、，则可能的二叉树有5种。种。ABC474.2 二叉树二叉树二叉树的遍历二叉树的遍历例：已知前序遍历序列为例：已知前序遍历序列为ABC，后序遍历序列为，后序遍历序列为 CBA，则下列二叉树都满足条件。，则下列二叉树都满足条件。ABCABC若已知一棵二叉树的前序序列和后序序列，能否若已知一棵二叉树的前序序列和后序序列，能否唯一确定这棵二叉树呢？唯一确定这棵二叉树呢？484.2 二叉树二叉树二叉树的遍历二叉树的遍历若已知一棵二叉树的前序序列和中序序列，能否若已知一棵二叉树的前序序列和中序序列，能否唯一确定这棵二叉树呢？怎样确定？唯一确定这棵二叉树呢？怎样确定？例如：已知一棵二叉树的前序遍历序列和中序

37、遍历例如：已知一棵二叉树的前序遍历序列和中序遍历序列分别为序列分别为ABCDEFGHI 和和BCAEDGHFI，如何构造该二叉树呢如何构造该二叉树呢?494.2 二叉树二叉树二叉树的遍历二叉树的遍历前序：前序：A B C D E F G H I中序：中序：B C A E D G H F I前序：前序：B C中序：中序：B C B C D EF GH IA前序：前序：D E F G H I中序：中序：E D G H F IABCDEFGHI504.2 二叉树二叉树二叉树的遍历二叉树的遍历前序：前序：F G H I中序：中序：G H F I前序：前序：D E F G H I中序：中序：E D G

38、H F IABCDEFGHIABCDEFIGH514.2 二叉树二叉树二叉树的遍历二叉树的遍历说明说明u任意一棵二叉树的任一种遍历序列都是唯一的任意一棵二叉树的任一种遍历序列都是唯一的u由二叉树的前序序列和中序序列可唯一确定一棵由二叉树的前序序列和中序序列可唯一确定一棵二叉树二叉树u由二叉树的后序序列和中序序列可唯一确定一棵由二叉树的后序序列和中序序列可唯一确定一棵二叉树二叉树524.2 二叉树二叉树二叉树的遍历二叉树的遍历遍历二叉树是二叉树各种操作的基础，遍历算法中对遍历二叉树是二叉树各种操作的基础，遍历算法中对每个结点的访问操作可以是多种形式及多个操作每个结点的访问操作可以是多种形式及多个

39、操作根据遍历算法的框架，适当修改访问操作的内容，可根据遍历算法的框架，适当修改访问操作的内容，可以派生出很多关于二叉树的应用算法。以派生出很多关于二叉树的应用算法。void InOrder(BiNode*root)if(root=NULL)return;else InOrder(root-lchild);cout-data;InOrder(root-rchild);534.2 二叉树二叉树二叉树的遍历二叉树的遍历u设计算法求二叉树的结点个数设计算法求二叉树的结点个数 void Count(BiNode*root)/n为全局量并已初始化为为全局量并已初始化为0 if(root)Count(roo

40、t-lchild);n+;Count(root-rchild);544.2 二叉树二叉树二叉树遍历的非递归实现二叉树遍历的非递归实现递归算法递归算法u简洁，但执行效率不高，因为系统需要维护一个简洁，但执行效率不高，因为系统需要维护一个系统工作栈以保证递归函数的正确执行系统工作栈以保证递归函数的正确执行有时需要把递归算法转换为非递归算法有时需要把递归算法转换为非递归算法关键关键u如何实现由系统完成的递归工作栈如何实现由系统完成的递归工作栈u方法：仿照递归算法执行过程中工作栈的状态变方法：仿照递归算法执行过程中工作栈的状态变化得到化得到554.2 二叉树二叉树二叉树遍历的非递归实现二叉树遍历的非递

41、归实现先观察一下三种遍历行走的路线先观察一下三种遍历行走的路线u前序遍历（前序遍历（VLR）例，例，ABEHGCFDIABCEFHGDI*564.2 二叉树二叉树二叉树遍历的非递归实现二叉树遍历的非递归实现u中序遍历（中序遍历（LVR）例，例，EBGHAFDCI1#1#2#2#3#3#4#4#5#5#6#6#7#7#9#9#8#8#ABCEFHGDI574.2 二叉树二叉树二叉树遍历的非递归实现二叉树遍历的非递归实现u后序遍历（后序遍历（LRV）例，例，EGHBDFICA&ABCEFHGDI584.2 二叉树二叉树二叉树遍历的非递归实现二叉树遍历的非递归实现u结论结论三种遍历的路线是完全一样的

42、，每个结点都被经过三次三种遍历的路线是完全一样的，每个结点都被经过三次但访问时间是不同的但访问时间是不同的l前序：第一次经过时访问前序：第一次经过时访问*l中序：第二次经过时访问中序：第二次经过时访问#l后序：第三次经过时访问后序：第三次经过时访问&u遍历线路的核心规则是：先左后右遍历线路的核心规则是：先左后右u用一个栈记录走过的位置，以便返回用一个栈记录走过的位置，以便返回594.2 二叉树二叉树二叉树遍历的非递归实现二叉树遍历的非递归实现中序遍历的递归工作栈中序遍历的递归工作栈u遍历序列：遍历序列：EBGHAFDCIu栈的变化栈的变化A入栈；入栈；B入栈；入栈；E入栈；空入栈；空出栈；访问

43、入栈；空入栈；空出栈；访问E；空入栈；空出栈；空入栈；空出栈；E出栈；访问出栈；访问B；H入栈；入栈；G入栈；入栈；空入栈；空出栈；访问空入栈；空出栈；访问G；空入栈；空出栈；空入栈；空出栈；G出栈；出栈；访问访问H；空入栈；空出栈；空入栈；空出栈；H出栈；出栈；B出栈；访问出栈；访问A；C入栈；入栈；F入栈；空入栈；空出栈；访问入栈；空入栈；空出栈；访问F；D入栈；入栈；空入栈；空出栈；访问空入栈；空出栈；访问D；空入栈；空出栈；空入栈；空出栈；F出栈；出栈；访问访问C；I入栈；空入栈；空出栈；访问入栈；空入栈；空出栈；访问I；空入栈；空入栈；空出栈；空出栈；I出栈；出栈；C出栈；出栈；A出

44、栈。出栈。ABCEFHGDI604.2 二叉树二叉树二叉树遍历的非递归实现二叉树遍历的非递归实现中序遍历二叉树的非递归算法思想中序遍历二叉树的非递归算法思想u建立栈建立栈 Stack；ut 指向根结点；指向根结点；u当当 t 不空不空 或或 Stack 不空时反复做：不空时反复做：若若 t 不空，则不空，则 t 入入 栈；栈；t 指向左子女；指向左子女；否则否则l出栈顶元素到出栈顶元素到 t 中；中；l访问访问 t；lt 指向右子女；指向右子女；u结束结束614.2 二叉树二叉树二叉树遍历的非递归实现二叉树遍历的非递归实现u中序遍历的非递归算法中序遍历的非递归算法void InOrder(vo

45、id Visit(BinaryTreeNode*)/中序遍历中序遍历 BinaryTreeNode*t=root;Stack stack;/建立栈建立栈 while(t|!stack.IsEmpty()if(t)stack.Push(t);t=t-leftChild;/t向左走一步向左走一步 else t=stack.Pop();Visit(t);t=t-rightChild;/t向右走一步向右走一步 /while/InOrder 624.2 二叉树二叉树二叉树遍历的非递归实现二叉树遍历的非递归实现ABCDEFGt访问序列访问序列&A&B&Ct=NULLC Bttt&Dt&Et=NULLEt&

46、GGt=NULLDt&Ft=NULLF At=NULL634.2 二叉树二叉树二叉树遍历的非递归实现二叉树遍历的非递归实现前序遍历二叉树的非递归算法思想前序遍历二叉树的非递归算法思想u建立栈建立栈 Stack；ut 指向根；指向根；u当当 t 不空不空 或或 Stack 不空时反复做：不空时反复做：若若 t 不空，访问不空，访问t，t 入入 栈；栈；t 指向左子女；指向左子女；否则：否则：l出栈顶元素到出栈顶元素到 t 中；中；lt 指向右子女；指向右子女；u结束结束与中序遍历二叉树类似与中序遍历二叉树类似644.2 二叉树二叉树二叉树遍历的非递归实现二叉树遍历的非递归实现后序遍历二叉树的非递

47、归算法后序遍历二叉树的非递归算法u后序遍历时，访问一个结点的时间是第后序遍历时，访问一个结点的时间是第3次经过时次经过时u第第3次经过第次经过第2次返回从右边返回次返回从右边返回u如何区分从左返回还是右返回的呢？如何区分从左返回还是右返回的呢？t 入栈时带一标记入栈时带一标记l向左走时带向左走时带Ll向右走时带向右走时带R654.2 二叉树二叉树二叉树遍历的非递归实现二叉树遍历的非递归实现u算法思想算法思想建立栈建立栈 Stack；t 指向根；指向根；当当 t 不空不空 或或 Stack 不空时反复做：不空时反复做：l若若 t 不空：不空：(t,L)入栈；入栈；t 指向左子女；指向左子女；l否

48、则：出栈顶元素到否则：出栈顶元素到 t 和和 tag 中；中；若若 tag=R：访问：访问 t；t 置空；置空；否则（否则（t,R）入栈；并让）入栈；并让 t 指向右子女；指向右子女；结束结束664.2 二叉树二叉树二叉树遍历的非递归实现二叉树遍历的非递归实现u后序遍历二叉树非递归算法后序遍历二叉树非递归算法void PostOrder(void Visit(BinaryTreeNode*)/后序遍历后序遍历 BinaryTreeNode*t=root;Stack stack;/建立栈建立栈 while(t|!stack.IsEmpty()if(t)stack.push(t,L);/(t,L)

49、入栈入栈 t=t-leftChild;/t向左走一步向左走一步 else e=stack.pop();t=e.t;tag=e.tag;if(tag=R)Visit(t);t=NULL;else stack.push(t,R);t=t-rightChild;/t向右走一步向右走一步 /if /while/postOrder 674.2 二叉树二叉树二叉树遍历的非递归实现二叉树遍历的非递归实现BEACroot(A.L)入栈入栈 (A.L)(B.L)入栈入栈 (A.L)(B.L)(B.L)退栈退栈 (A.L)(B.R)入栈入栈 (A.L)(B.R)(E.L)入栈入栈 (A.L)(B.R)(E.L)(

50、E.L)退栈退栈 (A.L)(B.R)(E.R)入栈入栈 (A.L)(B.R)(E.R)(E.R)退栈退栈 (A.L)(B.R)访问访问E(B.R)退栈退栈 (A.L)访问访问B(A.L)退栈退栈 k(A.R)入栈入栈 (A.R)l(C.L)入栈入栈 (A.R)(C.L)m(C.L)退栈退栈 (A.R)n(C.R)入栈入栈 (A.R)(C.R)o(C.R)退栈退栈 (A.R)访问访问Cp(A.R)退栈退栈 访问访问A12345678910111213141516684.2 二叉树二叉树二叉树遍历的非递归实现二叉树遍历的非递归实现层次遍历二叉树层次遍历二叉树u从二叉树的第一层（根结点）开始，从上