第五章树和二叉树PPT课件

1、5-1 树的提出v第五章 树和二叉树数据结构（从概念到实现） 清华大学出版社文件系统文件系统许多问题抽象出的数据模型具有层次关系例 1 操作系统的文件目录结构。数据结构（从概念到实现） 清华大学出版社表达式树表达式树例 2 一个算术表达式可以用表达式树来表示，并且具有以下两个特点（1）叶子结点是操作数；（2）分支结点是运算符。进行后序遍历转换为逆波兰式：a b c d - * + e f / -aefbcd-+/*-表达式：a + b * (c d) e / f数据结构（从概念到实现） 清华大学出版社随处可见的树结构随处可见的树结构例 3 计算机系统上随处可见的树结构。数据结构（从概念到实现）

2、 清华大学出版社随处可见的树结构随处可见的树结构例 3 计算机系统上随处可见的树结构。数据结构（从概念到实现） 清华大学出版社随处可见的树结构随处可见的树结构例 4 日常生活中随处可见的树结构。数据结构（从概念到实现） 清华大学出版社随处可见的树结构随处可见的树结构例 4 日常生活中随处可见的树结构。吉林省市区街道朝阳南关二道高新宽城绿园双阳九台湖西桂林永昌红旗清和吉林长春四平通化辽源松原白城白山延边数据结构（从概念到实现） 清华大学出版社知识树知识树数据结构（从概念到实现） 清华大学出版社思维导图思维导图数据结构（从概念到实现） 清华大学出版社关于树结构关于树结构什么是树？在逻辑上有什么特点

3、？有哪些基本术语？如何存储树结构？什么是二叉树？在逻辑上有什么特点？有哪些基本性质？如何存储二叉树？如何实现二叉树的遍历操作？最优二叉树及应用树与森林5-2-1 树的定义和基本术语v第五章 树和二叉树数据结构（从概念到实现） 清华大学出版社12树和森林的概念树和森林的概念两种树：自由树与有根树。两种树：自由树与有根树。自由树自由树：一棵自由树一棵自由树 Tf 可定义为一个二元组可定义为一个二元组 Tf = (V, E) 其中其中V = v1, ., vn 是由是由 n (n0) 个元素组成个元素组成的有限非空集合，称为顶点集合。的有限非空集合，称为顶点集合。E = (vi, vj) | vi,

4、 vj V, 1i, jn 是是n-1个序对的集合，称个序对的集合，称为边集合，为边集合，E 中的元素中的元素 (vi, vj）称为边或分支。）称为边或分支。数据结构（从概念到实现） 清华大学出版社13自由树有根树有根树：一棵有根树一棵有根树 T，简称为树，它是，简称为树，它是n (n0) 个结个结点的有限集合。当点的有限集合。当n = 0时，时，T 称为空树；否称为空树；否则，则，T 是非空树，记作是非空树，记作 数据结构（从概念到实现） 清华大学出版社树的定义树的定义树：n（n0）个结点的有限集合数据元素树的定义是采用递归方法 ，当 n0 时，称为空树；任意一棵非空树 T 满足以下条件：（

5、1）有且仅有一个特定的称为根的结点；（2）当 n1 时，除根结点之外的其余结点被分成 m（m 0）个互不相交的有限集合 T1,T2, , Tm，其中每个集合又是一棵树，并称为这个根结点的子树。数据结构（从概念到实现） 清华大学出版社ACBGFEDHIACBGFDACBGFDE互不相交的具体含义是什么？结点：结点不能属于多个子树边：子树之间不能有关系互不相交没有回路树的逻辑特征树的逻辑特征树结构具有层次性数据结构（从概念到实现） 清华大学出版社16树的基本术语树的基本术语子女子女：若结点的子树非空，结点子树的根即：若结点的子树非空，结点子树的根即为该结点的子女。为该结点的子女。双亲双亲：若结点有

6、子女，该结点是子女双亲。：若结点有子女，该结点是子女双亲。1层2层4层3层depth= 4DACBIJHGFEMLKheight= 4数据结构（从概念到实现） 清华大学出版社17兄弟兄弟：同一结点的子女互称为兄弟。：同一结点的子女互称为兄弟。度度：结点的子女个数即为该结点的度；树中：结点的子女个数即为该结点的度；树中各个结点的度的最大值称为各个结点的度的最大值称为树的度树的度。分支结点分支结点：度不为：度不为0的结点即为分支结点，的结点即为分支结点，亦称为非终端结点。亦称为非终端结点。叶结点叶结点：度为：度为0的结点即为叶结点，亦称为的结点即为叶结点，亦称为终端结点。终端结点。祖先祖先：某结点

7、到根结点的路径上的各个结点：某结点到根结点的路径上的各个结点都是该结点的祖先。都是该结点的祖先。子孙子孙：某结点的所有下属结点，都是该结点：某结点的所有下属结点，都是该结点的子孙。的子孙。数据结构（从概念到实现） 清华大学出版社18结点的层次结点的层次：规定根结点在第一层，其子女：规定根结点在第一层，其子女结点的层次等于它的层次加一。以下类推。结点的层次等于它的层次加一。以下类推。深度深度：结点的深度即为结点的层次；离根最：结点的深度即为结点的层次；离根最远结点的层次即为远结点的层次即为树的深度树的深度。1层2层4层3层depth= 4DACBIJHGFEMLKheight= 4数据结构（从概

8、念到实现） 清华大学出版社19高度高度：规定叶结点的高度为：规定叶结点的高度为1，其双亲结点，其双亲结点的高度等于它的高度加一。的高度等于它的高度加一。树的高度树的高度：等于根结点的高度，即根结点所：等于根结点的高度，即根结点所有子女高度的最大值加一。有子女高度的最大值加一。有序树有序树：树中结点的各棵子树：树中结点的各棵子树 T0, T1, 是有是有次序的，即为有序树。次序的，即为有序树。无序树无序树：树中结点的各棵子树之间的次序是：树中结点的各棵子树之间的次序是不重要的，可以互相交换位置。不重要的，可以互相交换位置。森林森林：森林是：森林是m（m0）棵树的集合。）棵树的集合。 数据结构（从

9、概念到实现） 清华大学出版社树的基本术语树的基本术语ACBGFEDHI双亲：这个结点称为它孩子结点的双亲结点孩子：树中某结点子树的根结点称为这个结点的孩子结点兄弟：具有同一个双亲的孩子结点互称为兄弟a1ana2ai-1ai在线性结构中，逻辑关系表现为前驱后继在树结构中，逻辑关系表现为双亲孩子数据结构（从概念到实现） 清华大学出版社树的基本术语树的基本术语ACBGFEDHI路径：结点序列 n1, n2, , nk 称为一条由 n1 至 nk 的路径，当且仅当满足如下关系：结点 ni 是 ni+1 的双亲（1=ik）路径长度：路径上经过的边的个数在树结构中，路径是唯一的在线性结构中，逻辑关系表现为

10、前驱后继在树结构中，逻辑关系表现为双亲孩子数据结构（从概念到实现） 清华大学出版社树的基本术语树的基本术语ACBGFEDHI树的宽度：树中每一层结点个数的最大值深度=4宽度=4数据结构（从概念到实现） 清华大学出版社线性结构和树结构的比较线性结构和树结构的比较开始结点（只有一个）:无前驱根结点（只有一个）:无双亲终端结点（只有一个）:无后继叶子结点(可以有多个):无孩子其它元素：一个前驱,一个后继其它结点：一个双亲,多个孩子一对一 一对多ACBGFEDHIa1ana2ai-1ai线性结构树结构5-2-2 树的抽象数据类型定义v第五章 树和二叉树数据结构（从概念到实现） 清华大学出版社树的抽象数

11、据类型定义树的抽象数据类型定义树的应用很广泛，在不同的实际应用中，树的基本操作不尽相同ADT TreeDataModel 树由一个根结点和若干棵子树构成，树中结点具有层次关系Operation InitTree：初始化一棵树 DestroyTree：销毁一棵树 PreOrder：前序遍历树 PostOrder：后序遍历树 LeverOrder：层序遍历树endADT简单起见，只讨论树的遍历数据结构（从概念到实现） 清华大学出版社26树的抽象数据类型树的抽象数据类型template class Tree /对象对象: 树是由树是由n (0) 个结点组成的有限集合。在个结点组成的有限集合。在/类界

12、面中的类界面中的 position 是树中结点的地址。在顺序是树中结点的地址。在顺序/存储方式下是下标型存储方式下是下标型, 在链表存储方式下是指针在链表存储方式下是指针/型。型。T 是树结点中存放数据的类型是树结点中存放数据的类型, 要求所有结要求所有结/点的数据类型都是一致的。点的数据类型都是一致的。public: Tree (); Tree (); 27 BuildRoot (const T& value); /建立树的根结点 position FirstChild(position p); /返回 p 第一个子女地址, 无子女返回 0 position NextSibling(

13、position p); /返回 p 下一兄弟地址, 若无下一兄弟返回 0 position Parent(position p); /返回 p 双亲结点地址, 若 p 为根返回 0 T getData(position p); /返回结点 p 中存放的值 bool InsertChild(position p, T& value); /在结点 p 下插入值为 value 的新子女, 若插 /入失败, 函数返回false, 否则返回true28 bool DeleteChild (position p, int i); /删除结点 p 的第 i 个子女及其全部子孙结 /点, 若删除失败

14、, 则返回false, 否则返回true void DeleteSubTree (position t); /删除以 t 为根结点的子树 bool IsEmpty (); /判树空否, 若空则返回true, 否则返回false void Traversal (void (*visit)(position p); /遍历以 p 为根的子树; 5-4-1 二叉树的定义v第五章 树和二叉树数据结构（从概念到实现） 清华大学出版社二叉树的定义二叉树的定义二叉树： n（n0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

15、二叉树是度为 2 的树吗？AB二叉树是度小于等于 2 的树吗？ABACBDEFG数据结构（从概念到实现） 清华大学出版社31LLRR二叉树二叉树 (Binary Tree)(Binary Tree)二叉树的定义二叉树的定义一棵二叉树是结点的一个有限集合，该集合一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉别称为左子树和右子树的、互不相交的二叉树组成。树组成。数据结构（从概念到实现） 清华大学出版社二叉树的特点二叉树的特点ACBDEFG二叉树有什么特点？（1）每个结点最多有两棵子树（2）二叉

16、树是有序的，其次序不能任意颠倒 为什么要研究二叉树？（1）二叉树是最简单的树结构（2）将树转换为二叉树， 从而利用二叉树解决树的有关问题数据结构（从概念到实现） 清华大学出版社斜树斜树斜树：左斜树和右斜树的统称左斜树：所有结点都只有左子树的二叉树ABD右斜树：所有结点都只有右子树的二叉树ABD斜树有什么特点呢？（1）每一层只有一个结点（2）结点个数与其深度相同斜树是树结构的特例，是从树结构退化成了线性结构数据结构（从概念到实现） 清华大学出版社满二叉树满二叉树满二叉树：所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上的二叉树ABCDEFHIJKLMNOGABCDEFLMG所有分支结点

17、都有左右子树，但叶子不在同一层上数据结构（从概念到实现） 清华大学出版社满二叉树满二叉树满二叉树：所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上的二叉树满二叉树有什么特点呢？（1）叶子只能出现在最下一层满二叉树是树结构的特例，是最丰满的二叉树ABCDEFHIJKLMNOG（4）在同样深度的二叉树中叶子结点个数最多（2）只有度为 0 和度为 2 的结点（3）在同样深度的二叉树中结点个数最多数据结构（从概念到实现） 清华大学出版社L完全二叉树完全二叉树完全二叉树：在满二叉树中，从最后一个结点开始，连续去掉任意个结点得到的二叉树ABCDEFHIJKMNOGABCDEFHIJKMG5-4-

18、2 二叉树的基本性质v第五章 树和二叉树数据结构（从概念到实现） 清华大学出版社二叉树的性质二叉树的性质性质 5-1：在一棵二叉树中，如果叶子结点数为 n0，度为 2 的结点数为 n2，则有: n0n21ACBE证明: 设 n 为二叉树的结点总数，n1 为二叉树中度为 1 的结点数，则有： nn0n1n2 在二叉树中，除了根结点外，其余结点都有唯一的一个分枝进入，一个度为 1 的结点射出一个分枝，一个度为 2 的结点射出两个分枝，所以有： nn12n21因此可以得到： n0n21 数据结构（从概念到实现） 清华大学出版社二叉树的性质二叉树的性质性质 5-2：二叉树的第 i 层上最多有2i-1个

19、结点（i1）证明：采用归纳法证明。当 i = 1时，只有一个根结点，而 2i-1 = 20 =1，结论成立。假设 i = k 时结论成立，即第 k 层上最多有 2k -1 个结点。考虑 i = k+1 时的情形。由于第 k+1 层上的结点是第 k 层上结点的孩子，而二叉树中每个结点最多有两个孩子，故在第 k+1 层上的最多大结点个数有 22k-12k 个结点，则在 i = k+1时结论也成立。由此，结论成立。数据结构（从概念到实现） 清华大学出版社二叉树的性质二叉树的性质性质 5-3：一棵深度为 k 的二叉树中，最多有 2k -1个结点证明：设深度为 k 的二叉树中结点个数最多为 n，则深度为

20、 k 且具有 2k-1个结点的二叉树一定是满二叉树数据结构（从概念到实现） 清华大学出版社二叉树的性质二叉树的性质性质 5-4：具有 n 个结点的完全二叉树的深度为 log2n +1证明：设具有 n 个结点的完全二叉树的深度为 k，则2k-1-12k-12k-1第k层第k-1层层对不等式取对数，有： k-1 log2nk即： log2nk log2n+1由于 k 是整数，故必有 k log2n +1数据结构（从概念到实现） 清华大学出版社二叉树的性质二叉树的性质性质 5-5：对一棵具有 n 个结点的完全二叉树中从 1 开始按层序编号，对于任意的序号为 i（1in）的结点（简称结点 i），有：

21、（1）如果 i1，则结点 i 的双亲结点的序号为 i/2，否则结点 i 无双亲结点（2）如果 2in，则结点 i 的左孩子的序号为 2i，否则结点 i 无左孩子（3）如果 2i+1n，则结点 i 的右孩子的序号为2i+1，否则结点 i 无右孩子123456891075-4-3 二叉树的抽象数据类型定义v第五章 树和二叉树数据结构（从概念到实现） 清华大学出版社二叉树的抽象数据类型定义二叉树的抽象数据类型定义ADT BiTreeDataModel 二叉树由一个根结点和两棵互不相交的左右子树构成，结点具有层次关系Operation InitBiTree：初始化一棵空的二叉树 CreatBiTree

22、：建立一棵二叉树 DestroyBiTree：销毁一棵二叉树 PreOrder：前序遍历二叉树 InOrder：中序遍历二叉树 PostOrder：后序遍历二叉树 LeverOrder：层序遍历二叉树endADT简单起见，只讨论二叉树的遍历数据结构（从概念到实现） 清华大学出版社45二叉树的抽象数据类型二叉树的抽象数据类型template class BinaryTree /对象: 结点的有限集合, 二叉树是有序树public: BinaryTree ();/构造函数 BinaryTree (BinTreeNode *lch, BinTreeNode *rch, T item); /构造函数,

23、 以item为根, lch和rch为左、右子 /树构造一棵二叉树 int Height ();/求树深度或高度 int Size ();/求树中结点个数数据结构（从概念到实现） 清华大学出版社46 bool IsEmpty ();/判二叉树空否？ BinTreeNode *Parent (BinTreeNode *t);/求结点 t 的双亲 BinTreeNode *LeftChild (BinTreeNode *t); /求结点 t 的左子女 BinTreeNode *RightChild (BinTreeNode *t);/求结点 t 的右子女 bool Insert (T item);/

24、在树中插入新元素 bool Remove (T item);/在树中删除元素 bool Find (T& item);/判断item是否在树中 bool getData (T& item);/取得结点数据数据结构（从概念到实现） 清华大学出版社47 BinTreeNode *getRoot ();/取根 void preOrder (void (*visit) (BinTreeNode *t);/前序遍历, visit是访问函数 void inOrder (void (*visit) (BinTreeNode *t);/中序遍历, visit是访问函数 void postOrd

25、er (void (*visit) (BinTreeNode *t);/后序遍历, (*visit)是访问函数 void levelOrder (void (*visit)(BinTreeNode *t);/层次序遍历, visit是访问函数;数据结构（从概念到实现） 清华大学出版社二叉树的遍历二叉树的遍历二叉树的遍历：从根结点出发，按照某种次序访问树中所有结点，并且每个结点仅被访问一次 抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据限定先左后右：前序、中序、后序根结点D左子树L右子树R二叉树按照什么次序对二叉树进行遍历呢？二叉树的遍历方式：DLR、LDR、LRD、DRL、RD

26、L、RLD 层序遍历：按二叉树的层序编号的次序访问各结点 数据结构（从概念到实现） 清华大学出版社中序遍历中序遍历若二叉树为空，则空操作返回；否则：（1）中序遍历根结点的左子树（2）访问根结点（3）中序遍历根结点的右子树ACBDEFG中序遍历序列：D G B A E C F数据结构（从概念到实现） 清华大学出版社前序遍历前序遍历若二叉树为空，则空操作返回；否则：（1）访问根结点（2）前序遍历根结点的左子树（3）前序遍历根结点的右子树ACBDEFG前序遍历序列：A B D G C E F数据结构（从概念到实现） 清华大学出版社后序遍历后序遍历若二叉树为空，则空操作返回；否则：（1）后序遍历根结点

27、的左子树（2）后序遍历根结点的右子树（3）访问根结点ACBDEFG后序遍历序列：G D B E F C A数据结构（从概念到实现） 清华大学出版社层序遍历层序遍历从二叉树的根结点开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问ACBDEFG层序遍历序列：A B C D E F G数据结构（从概念到实现） 清华大学出版社53写出右树的前序、中序和后序序列写出右树的前序、中序和后序序列前序：前序：- + a b * - c d / e f中序：中序：a+b * c-d e/f后序：后序：a b c d - * + e f / -随堂练习随堂练习数据结构（从概念到实现） 清华大学

28、出版社54二叉树递归的中序遍历算法二叉树递归的中序遍历算法template void BinaryTree:InOrder (BinTreeNode * subTree, void (*visit) (BinTreeNode *t) if (subTree != NULL) InOrder (subTree-leftChild, visit); /遍历左子树 visit (subTree);/访问根结点 InOrder (subTree-rightChild, visit); /遍历右子树 ;数据结构（从概念到实现） 清华大学出版社55二叉树递归的前序遍历算法二叉树递归的前序遍历算法templ

29、ate void BinaryTree:PreOrder (BinTreeNode * subTree, void (*visit) (BinTreeNode *t) if (subTree != NULL) visit (subTree);/访问根结点PreOrder (subTree-leftChild, visit); /遍历左子树PreOrder (subTree-rightChild, visit); /遍历右子树 ;数据结构（从概念到实现） 清华大学出版社56二叉树递归的后序遍历算法二叉树递归的后序遍历算法template void BinaryTree:PostOrder (Bi

30、nTreeNode * subTree, void (*visit) (BinTreeNode *t ) if (subTree != NULL ) PostOrder (subTree-leftChild, visit); /遍历左子树PostOrder (subTree-rightChild, visit); /遍历右子树visit (subTree); /访问根结点 ;数据结构（从概念到实现） 清华大学出版社57访问树中的结点的数据域访问树中的结点的数据域实际等于实际等于visit（t-data）根据实际需要，可以在根据实际需要，可以在visit中，将每个结点的中，将每个结点的data值

31、返回值返回visit函数数据结构（从概念到实现） 清华大学出版社58层次序遍历的（非递归）算法层次序遍历的（非递归）算法template void BinaryTree:levelOrder (void (*visit) (BinTreeNode *t) if (root = NULL) return; QueueBinTreeNode * Q; BinTreeNode *p = root; visit (p); Q.EnQueue (p); while (!Q.IsEmpty () Q.DeQueue (p); if (p-leftChild != NULL) 数据结构（从概念到实现） 清华

32、大学出版社59 visit (p-leftChild); Q.EnQueue (p-leftChild); if (p-rightChild != NULL) visit (p-rightChild); Q.EnQueue (p-rightChild); ;数据结构（从概念到实现） 清华大学出版社二叉树的前序遍历二叉树的前序遍历- -课后阅读课后阅读template void BiTree : PreOrder(BiNode *bt) if (bt = nullptr) return; /递归调用的结束条件 else cout data; /访问根结点bt的数据域 PreOrder(bt-lc

33、hild); /前序递归遍历bt的左子树 PreOrder(bt-rchild); /前序递归遍历bt的右子树 按照先左后右的方式扫描二叉树，区别仅在于访问结点的时机LR数据结构（从概念到实现） 清华大学出版社ACBDPre(*A) （1）A Pre(A-lchild); Pre(*B) （2）B Pre(B-lchild); Pre() Pre(*D) （3）D Pre(D-lchild); Pre() Pre() Pre(B-rchild); Pre(D-rchild); 约定：*A 表示根指针指向结点 Aif (bt = nullptr) return; else cout data;

34、PreOrder(bt-lchild); PreOrder(bt-rchild); 二叉树的中序遍历二叉树的中序遍历- -课后阅读课后阅读数据结构（从概念到实现） 清华大学出版社ACBDPre(*A) （1）A Pre(A-lchild); Pre(*B) （2）B Pre(B-lchild); Pre() Pre(*D) （3）D Pre(D-lchild); Pre() Pre() Pre(B-rchild); Pre(D-rchild); Pre() Pre() Pre(*C) （4）C Pre(C-lchild); Pre(A-rchild); Pre(C-rchild); 得到前序序

35、列：A B D Cif (bt = nullptr) return; else cout data; PreOrder(bt-lchild); PreOrder(bt-rchild); 二叉树的前序遍历二叉树的前序遍历- -课后阅读课后阅读数据结构（从概念到实现） 清华大学出版社遍历序列：遍历序列：AAB CBDCE F GD E F GACBDEFG1. 队列 Q 初始化；2. 如果二叉树非空，将根指针入队；入队入队出队出队 3.3 若结点 q 存在左孩子，则将左孩子指针入队； 3.4 若结点 q 存在右孩子，则将右孩子指针入队；3. 循环直到队列 Q 为空 3.1 q = 队列 Q 的队头

36、元素出队； 3.2 访问结点 q 的数据域； 二叉树的层序遍历二叉树的层序遍历- -课后阅读课后阅读数据结构（从概念到实现） 清华大学出版社template void BiTree : LeverOrder( ) BiNode *Q100, *q = nullptr; int front = -1, rear = -1; if (root = nullptr) return; Q+rear = root; while (front != rear) q = Q+front; cout data; if (q-lchild != nullptr) Q+rear = q-lchild; if (q

37、-rchild != nullptr) Q+rear = q-rchild; 时间复杂度？每个结点进队出队一次O(n)O(n)二叉树的层序遍历二叉树的层序遍历- -课后阅读课后阅读数据结构（从概念到实现） 清华大学出版社#include #include #include #include using namespace std; templatestruct BiNode /二叉树结点 T value; BiNode *pLeft; BiNode *pRight; BiNode() : pLeft(NULL), pRight(NULL) ; templatestruct BiNodeAux

38、BiNode *pNode; bool hasVisited; BiNodeAux(BiNode *_node, bool _vis) : pNode(_node), hasVisited(_vis) ; templatevoid PreOrderRecursively(BiNode *pRoot) if (pRoot = NULL) return; cout value pLeft); PreOrder(pRoot-pRight); templatevoid PreOrder(BiNode *pRoot) if (pRoot = NULL) return; stackBiNodeAux s;

39、 BiNode *pCur = pRoot; while (pCur != NULL | !s.empty() if (pCur != NULL) cout value t; s.push(BiNodeAux(pCur, false); pCur = pCur-pLeft; else if (s.top().hasVisited = true) s.pop(); else s.top().hasVisited = true; pCur = s.top().pNode-pRight; templatevoid InOrderRecursively(BiNode *pRoot) if (pRoot

40、 != NULL) InOrderRecursively(pRoot-pLeft); cout value pRight); templatevoid InOrder(BiNode *pRoot) if (pRoot = NULL) return; stackBiNode* s; BiNode *pCur = pRoot; while (pCur != NULL | !s.empty() if (pCur != NULL) s.push(pCur); pCur = pCur-pLeft; else cout value pRight; s.pop(); templatevoid PostOrd

41、erRecursively(BiNode *pRoot) if (pRoot != NULL) PostOrderRecursively(pRoot-pLeft); PostOrderRecursively(pRoot-pRight); cout value t; templatevoid PostOrder(BiNode *pRoot) if (pRoot = NULL) return; stackBiNodeAux s; BiNode *pCur = pRoot; while (pCur != NULL | !s.empty() if (pCur != NULL) s.push(BiNod

42、eAux(pCur, false); pCur = pCur-pLeft; else if (s.top().hasVisited = false) s.top().hasVisited = true; pCur = s.top().pNode-pRight; else cout value t; s.pop(); templatevoid LevelOrder(BiNode *pRoot) if (pRoot = NULL) return; queueBiNode* q; BiNode *pCur = pRoot; q.push(pCur); while (!q.empty() pCur =

43、 q.front(); cout value pLeft != NULL) q.push(pCur-pLeft); if (pCur-pRight != NULL) q.push(pCur-pRight); int main() BiNode nodes7; for (int i = 0; i 7; +i) nodesi.value = i + 1; nodes0.pLeft = &nodes1; nodes0.pRight = &nodes2; nodes1.pLeft = &nodes3; nodes1.pRight = &nodes4; nodes2.pL

44、eft = &nodes5; nodes2.pRight = &nodes6; cout 建立一个三层满二叉树成功! endl endl; cout 递归前序遍历该二叉树的结果为：endl; PreOrderRecursively(&nodes0); cout endl; cout 非递归前序遍历该二叉树的结果为：endl; PreOrder(&nodes0); cout endl endl; cout 递归中序遍历该二叉树的结果为：endl; InOrderRecursively(&nodes0); cout endl; cout 非递归中序遍历该二叉

45、树的结果为：endl; InOrder(&nodes0); cout endl endl; cout 递归后序遍历该二叉树的结果为：endl; PostOrderRecursively(&nodes0); cout endl; cout 非递归后序遍历该二叉树的结果为：endl; PostOrder(&nodes0); cout endl endl; cout 层序遍历该二叉树的结果为：endl; LevelOrder(&nodes0); cout endl ; system(pause); return 0;二叉树的遍历二叉树的遍历- -代码示意代码示意数据结

46、构（从概念到实现） 清华大学出版社遍历与二叉树遍历与二叉树若已知一棵二叉树的前序（或中序，或后序，或层序）序列，能否唯一确定这棵二叉树呢？ABCABC前序遍历序列：A B C若已知一棵二叉树的前序序列和后序序列，能否唯一确定这棵二叉树呢？后序遍历序列：C B A数据结构（从概念到实现） 清华大学出版社由先序序列和中序序列恢复二叉树：由先序序列和中序序列恢复二叉树：（1）由先序序列得到二叉树的根结点；）由先序序列得到二叉树的根结点；（2）由上述（）由上述（1）的根结点把中序序列分为左子树）的根结点把中序序列分为左子树的中序序列和右子树的中序序列两个部分；的中序序列和右子树的中序序列两个部分；（3

47、）根据上述左子树的中序序列个数找到对应的左）根据上述左子树的中序序列个数找到对应的左子树先序序列和右子树的先序序列；子树先序序列和右子树的先序序列；（4）按上述（）按上述（1）、（）、（2）、（）、（3）同样的方法依次）同样的方法依次类推，直到所得左、右子树只含一个结点为止。类推，直到所得左、右子树只含一个结点为止。数据结构（从概念到实现） 清华大学出版社示例：由先序序列示例：由先序序列ABCDEFGH和中序序列和中序序列CBEDAGHF恢复二叉树：恢复二叉树：方法：先序序列ABCDEFGH（注：A是根）中序序列CBEDAGHF左子树左子树右子树右子树ABCDEFGH以以A为根的左、为根的左、

48、右子树先序序列右子树先序序列示意图示意图数据结构（从概念到实现） 清华大学出版社由左子树先序序列：由左子树先序序列：BCDE和左子树中序序列：和左子树中序序列：CBED构造构造A的左子树的左子树同理，由右子树先序序列：同理，由右子树先序序列：FGH和右子树中和右子树中序序列序序列GHF构造构造A的右子树：的右子树： DABFC DEGHABFCEGH数据结构（从概念到实现） 清华大学出版社随堂练习练习： 已知一棵二叉树的中序序列为GDJHKBEACFMI，后序序列为GJKHDEBMIFCA，试画出该二叉树 已知一棵二叉树的中序序列为ABCDEFG，层序序列为BAFEGCD，试画出该二叉树 数据

49、结构（从概念到实现） 清华大学出版社随堂练习练习-重构二叉树：1. DJGBAHECKIMLF（中序） JGDBHEKMLIFCA（后序）2.ABCDEFGHI（层序）BFDGAEHIC（中序）数据结构（从概念到实现） 清华大学出版社l若左子树不空，则左子树上所有结点的值均小于它的根结点的值；l若右子树不空，则右子树上所有结点的值均大于它的根结点的值；l左、右子树也分别为二叉排序树；l没有键值相等的结点。二叉排序树二叉排序树数据结构（从概念到实现） 清华大学出版社二叉排序树二叉排序树lBSTBinary Search Treel若根结点的关键字值等于查找的关键字，成功。l否则，若小于根结点的关

50、键字值，递归查左子树。l若大于根结点的关键字值，递归查右子树。l若子树为空，查找不成功。数据结构（从概念到实现） 清华大学出版社二叉排序树二叉排序树l新插入的结点一定是一个新添加的叶子结点l并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。数据结构（从概念到实现） 清华大学出版社二叉排序树二叉排序树l要删除的结点不存在，删除失败l待删除结点为叶子节点，直接删除l待删除结点左孩子或右孩子为空，用非空孩子代替被删除结点l待删除结点有左、右孩子，找到待删结点待删结点的右子树中的最小结点的右子树中的最小结点，将最小结点的值赋给要删除的结点，然后删除最小结点第四种情况 删除25数据结构

51、（从概念到实现） 清华大学出版社二叉排序树二叉排序树l中序序列有什么特征？ 8 6 10 4 7 6 4 8 7 10数据结构（从概念到实现） 清华大学出版社平衡二叉树平衡二叉树 1 2 3 4 5 5 4 3 2 1 3 2 4 1 5 数据结构（从概念到实现） 清华大学出版社平衡二叉树平衡二叉树 理论上，当二叉搜索树是一颗完全二叉树时，查找最高效刻意构造BST为完全二叉树，代价太高引入平衡因子任意结点的左右子树的高度差任意节点的平衡因子满足|rightchild=rc-liftchild;P-liftchild=g;G-parent-left/right child=p;G-parent=

52、PT1-parent=g;数据结构（从概念到实现） 清华大学出版社平衡二叉树平衡二叉树rc=p;g-liftchild=p-rightchild；p-rightchild=g;G-parent-left/right child=p;G-parent=p;g-liftchild-parent=g;数据结构（从概念到实现） 清华大学出版社平衡二叉树平衡二叉树5-5-1 二叉树的顺序存储结构v第五章 树和二叉树数据结构（从概念到实现） 清华大学出版社二叉树的顺序存储结构二叉树的顺序存储结构顺序存储结构的要求是什么？用一组连续的存储单元依次存储数据元素，由存储位置表示元素之间的逻辑关系如何利用数组下标

53、来反映结点之间的逻辑关系?完全二叉树中结点的编号可以唯一地反映结点之间的逻辑关系 二叉树的顺序存储结构是用一维数组存储二叉树的结点，结点的存储位置（下标）应能体现结点之间的逻辑关系父子关系 数据结构（从概念到实现） 清华大学出版社二叉树的顺序存储结构二叉树的顺序存储结构ABCDEFHIJ编号为下标 A1 2 3 4 5 6 7 8 9 10 B C D E F G H I Jconst MaxSize = 100;template struct SeqBiTree DataType dataMaxSize; int biTreeNum; ;如何定义二叉树的顺序存储结构

54、呢？数据结构（从概念到实现） 清华大学出版社二叉树的顺序存储结构二叉树的顺序存储结构ABCDFEG152361310以编号为下标 A1 2 3 4 5 6 7 8 9 10 11 12 13 B C D F E G将二叉树按完全二叉树编号：（1）根结点的编号为 1（2）若某结点 i 有左孩子，则其左孩子的编号为 2i（3）若某结点 i 有右孩子，则其右孩子的编号为 2i+1对于普通的二叉树，如何顺序存储呢？数据结构（从概念到实现） 清华大学出版社二叉树的顺序存储结构二叉树的顺序存储结构二叉树的顺序存储结构一般仅存储完全二叉树顺序存储一棵右斜树会发生什么情况？ACOG缺点：浪费存储空间5-5-2

55、 二叉链表v第五章 树和二叉树数据结构（从概念到实现） 清华大学出版社如何用链接存储方式存储二叉树呢？ACBDEFGfirsta1a2an二叉链表：二叉树的每个结点对应一个链表结点，链表结点存放结点的数据信息和指示左右孩子的指针二叉链表的存储方法二叉链表的存储方法 lchild data rchild数据结构（从概念到实现） 清华大学出版社二叉链表的存储方法二叉链表的存储方法ACBDEFGGFEDBCAroot数据结构（从概念到实现） 清华大学出版社二叉链表的存储结构定义二叉链表的存储结构定义GFEDBACtemplate struct BiNode DataType data; BiNode

56、 *lchild, *rchild;叶子结点的标志？左右孩子指针均为空root数据结构（从概念到实现） 清华大学出版社二叉链表的存储结构定义二叉链表的存储结构定义GFEDBACn 个结点的二叉链表有多少个空指针？2n-(n-1) = n+1 个空指针roottemplate struct BiNode DataType data; BiNode *lchild, *rchild;数据结构（从概念到实现） 清华大学出版社三叉链表的存储方法三叉链表的存储方法GFEDBAC如何查找双亲？时间性能？O(n)在二叉链表中增加一个指向双亲的指针域 lchild data parent rchildroot

57、数据结构（从概念到实现） 清华大学出版社三叉链表的存储方法三叉链表的存储方法A BDEFCGACBDEFGroot数据结构（从概念到实现） 清华大学出版社二叉链表的类定义二叉链表的类定义二叉树的抽象数据类型定义？template class BiTreepublic: BiTree( )root = Creat(root); BiTree( )Release(root); void PreOrder( )PreOrder(root); void InOrder( )InOrder(root); void PostOrder( )PostOrder(root); void LeverOrder(

58、 ); private: BiNode *Creat(BiNode *bt); void Release(BiNode *bt); void PreOrder(BiNode *bt); void InOrder(BiNode *bt); void PostOrder(BiNode *bt); BiNode *root; ;InitBiTree：初始化一棵空的二叉树 CreatBiTree：建立一棵二叉树 DestroyBiTree：销毁一棵二叉树PreOrder：前序遍历二叉树InOrder：中序遍历二叉树PostOrder：后序遍历二叉树LeverOrder：层序遍历二叉树数据结构（从概念到

59、实现） 清华大学出版社双亲表示法双亲表示法如何定义树的双亲表示法?012345678 A - -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 data parenttemplate struct PNode DataType data; int parent; ;数据结构（从概念到实现） 清华大学出版社遍历将二叉树审视一遍，将非线性结构转换为线性结构遍历是二叉树各种操作的基础，可以在遍历的过程中建立一棵二叉树LR在内存中建立一棵二叉链表，如何输入二叉树的信息？二叉链表的建立二叉链表的建立数据结构（从概念到实现） 清华大学出版社如何由一种遍历序列生成该二叉树？ACBD扩展二

60、叉树的前序遍历序列：A B # D # # C # #扩展二叉树：将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值如 #ACBD#二叉链表的建立二叉链表的建立数据结构（从概念到实现） 清华大学出版社二叉链表的建立二叉链表的建立template BiNode *BiTree : Creat(BiNode *bt) char ch; cin ch; /输入结点的数据信息，假设为字符 if (ch = #) bt = nullptr; /建立一棵空树 else bt = new BiNode; bt-data = ch; bt-lchild = Creat(bt-lchild); /递归建立左子树 bt-rchild = Creat(bt-rchild); /递归建立右子树 return bt;数据结构（从概念到实现）