第6章 树 (后半部分).ppt

1、Chapter 6 树和二叉树,树的基本定义 二叉树的基本定义与性质 二叉树的物理实现 二叉树的遍历 二叉树的其他操作 树和森林 赫夫曼树及其应用,6.1树的基本定义,树的基本定义,树是由有限个（n个）相同结点构成的集合。如果n=0，称为空树；如果n0，则 有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱； 当n1，除根以外的其它结点划分为 m (m 0) 个互不相交的有限集 T1, T2 , Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。 如果和线性表相对比，则树 有一个根节点，它没有前驱 有多个尾节点，它们没有后继 对于其他节点，有唯一的

2、前驱和不止一个的后继,树的基本定义,A,只有根结点的树,有13个结点的树,其中：A是根；其余结点分成三个互不相交的子集， T1=B,E,F,K,L； T2=C,G； T3=D,H,I,J,M, T1,T2,T3都是根A的子树，且本身也是一棵树,树的基本术语,结点 结点的度 叶结点 分支结点,子女 双亲 兄弟,祖先 子孙,树的深度 结点层次,树的基本操作,课本P118,森林,有m(m=0)棵互不相交的树构成的集合。,6.2二叉树的基本定义与性质,二叉树的定义,二叉树是一种特化的树。 首先它是一棵树，其元素遵从树的定义。 特化体现在结构方面，每个节点至多只有两个子树，并且子树是有顺序的，不能颠倒。

3、,二叉树的定义,与树类似，二叉树也有一个递归的定义。 二叉树或者为空，或者是由一个根节点加上两棵分别成为左子树和右子树的、互不相交的二叉树组成。并且这两棵子树也是二叉树。 二叉树的五种形态。,二叉树的定义,思考：如何递归的定义一个线性表？,二叉树的基本操作,课本P121,二叉树的性质,性质1：在二叉树的第i层上至多有 2(i1)个结点。(i1),二叉树的性质,性质2：深度为 k 的二叉树至多有2k-1个结点(k1)。,二叉树的性质,性质3：对任何一棵二叉树T, 如果其叶结点数为 n0, 度为2的结点数为 n2,则n0n21.,二叉树的性质,新的定义： 满二叉树 完全二叉树,二叉树的性质,完全二

4、叉树： 课本定义，P124 更直观的定义：若设二叉树共有h层。除第 h 层外，其它各层 (0 h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树,二叉树的性质,非完全二叉树,完全二叉树,二叉树的性质,性质4：具有 n (n 0) 个结点的完全二叉树的深度为log2(n)1,6.3二叉树的物理实现,二叉树的顺序存储,用一组连续的地址自上而下、自左至右的存储二叉树的节点，并且将节点与完全二叉树对照，不存在节点存为特定的标志值。,二叉树的顺序存储,完全二叉树 一般二叉树 的顺序表示 的顺序表示,二叉树的链式存储,二叉链表 回忆：链表的节点，由一个数据域和一个指针域组

5、成。 二叉树每个节点至多有两个子树，则可以由一个数据域和两个指针域构成。,二叉树的链式存储,二叉树的链式存储,某些特定问题中，为了能够方便的访问上层节点，也可以再加入一个指针域。,lChild data parent rChild,三叉链表,二叉树的链式存储,二叉树的链式存储,二叉链表的类型定义。 课本P127 用BiTree代表一棵二叉树，它实际上是一个指向树的根节点的指针（与链表类似）。 树的某个节点：BiTNode T; 指向树某个节点的指针：BiTNode *T,BiTree *T 节点的左子树：T-lchild 节点的右子树：T-rchild,6.4二叉树的遍历,二叉树的遍历,遍历：

6、按某种次序访问数据结构中的元素，要求每个元素访问一次且仅访问一次。 线性表的遍历：有一定的方向，很容易实现。 树的遍历：难点在于确定访问的顺序。,二叉树的遍历,二叉树常用的四种遍历方法 先序。 中序。 后序。 层序。,二叉树的先序遍历,二叉树的先序遍历 如果二叉树为空，则什么都不做。 如果二叉树不为空，则 访问根节点 先序遍历左子树 先序遍历右子树 先序遍历是一个递归的过程，因为在描述这个过程时使用了它本身。,二叉树的先序遍历,先序遍历示例 访问根节点 A 先序遍历节点A的左子树 节点A左子树的根节点 B 先序遍历节点B的左子树 节点B左子树的根节点 D 先序遍历节点D的左子树 空，直接结束

7、先序遍历节点D的右子树 空，直接结束，至此对节点B左子树的遍历结束。,二叉树的先序遍历,先序遍历示例 先序遍历节点B的右子树 节点B右子树的根节点 E 先序遍历节点E的左子树 空，直接结束 先序遍历节点E的右子树 空，直接结束，至此对节点B右子树的遍历结束。同时：对节点A的左子树的遍历也已经完成。,二叉树的先序遍历,先序遍历示例 先序遍历节点A的右子树 节点A右子树的根节点 C 先序遍历节点C的左子树 空，直接退出，对节点C左子树的遍历完成。 先序遍历节点C的右子树 节点C右子树的根节点 F 先序遍历节点F的左子树 空，直接结束 先序遍历节点F的右子树 空，直接结束，遍历全部结束,二叉树的先序

8、遍历,先序遍历较复杂的例子 - + a * b - c d / e f,二叉树的中序遍历,二叉树的中序遍历 如果二叉树为空，则什么都不做。 如果二叉树不为空，则 中序遍历左子树 访问根节点 中序遍历右子树 中序遍历仍然是递归进行的,二叉树的中序遍历,中序遍历示例 中序遍历节点A的左子树 中序遍历节点B的左子树 中序遍历节点D的左子树 空，直接结束 访问节点B左子树的根节点 D 中序遍历节点D的右子树 空，直接结束，至此对节点B左子树的遍历结束。 访问节点A左子树的根节点 B,二叉树的中序遍历,中序遍历示例 中序遍历节点B的右子树 中序遍历节点E的左子树 空，直接结束 访问节点B右子树的根节点

9、E 中序遍历节点E的右子树 空，直接结束，至此对节点B右子树的遍历结束。对节点A左子树的遍历也结束了。 访问整个树的根节点 A,二叉树的中序遍历,中序遍历示例 中序遍历节点A的右子树 中序遍历节点C的左子树 空，直接结束 访问节点A右子树的根节点 C 中序遍历节点C的右子树 访问节点F的左子树 空，直接结束 访问节点C右子树的根节点 F 访问节点F的右子树 空，直接结束，全部遍历结束,二叉树的中序遍历,中序遍历较复杂的例子 a + b * c - d - e / f,二叉树的后序遍历,二叉树的后序遍历 如果二叉树为空，则什么都不做。 如果二叉树不为空，则 后序遍历左子树 后序遍历右子树 访问根

10、节点,二叉树的后序遍历,后序遍历较复杂的例子 a b c d - * + e f / -,二叉树的层序遍历,从上到下，每一层自左至右的遍历二叉树 - + / a * e f b c d,二叉树先序遍历的实现,不难发现，先序遍历完全符合一个递归程序设计的三要素 结束条件：空树 与原问题形式一样，规模更小的子问题：先序遍历子树 对子问题的操作：访问跟节点，解决子问题1，解决子问题2.,二叉树先序遍历的实现,结束条件：,if ( T = NULL ) /T是树的根节点 return;,二叉树先序遍历的实现,与原问题形式一样，规模更小的子问题：先序遍历子树,PreOrderTraverse(T-lch

11、ild) 或者 PreOrderTraverse(T-rchild),二叉树先序遍历的实现,对子问题的操作：访问根节点，解决左子树遍历（子问题1），解决右子树遍历（子问题2）.,void PreOrderTraverse ( BinTreeNode *T ) if ( T != NULL ) printf(T-data); PreOrderTraverse ( T-leftChild ); PreOrderTraverse ( T-rightChild ); ,二叉树先序遍历的实现,经过以上分析，二叉树先序遍历就基本实现了，但作为一个“好”的遍历程序，还有两个因素必须考虑 对元素操作的灵活性

12、差错处理,二叉树先序遍历的实现,对元素操作的灵活性 大家喜闻乐见的办法：函数指针 差错处理 在每次访问之后进行判断，如果访问失败了就不再继续执行，并返回错误信息。,二叉树先序遍历的实现,Status PreOrderTraverse (BinTreeNode *T，Status (*visit)(TElemType e) ) if (T) code = visit(T-data); if(code) code = PreOrderTraverse ( T-leftChild ); if(code) code = PreOrderTraverse ( T-rightChild ); if(cod

13、e) return OK; return Error; else return OK; ,二叉树先序遍历的实现,把上页的代码进行精简，便得到了算法6.1。 同理可以写出中序和后序遍历的递归实现。,二叉树先序遍历程序的原理,程序遍历过程的分析.,void PreOrderTraverse ( BinTreeNode *T ) if ( T != NULL ) printf(T-data); PreOrderTraverse ( T-leftChild ); PreOrderTraverse ( T-rightChild ); /如果有一个指针Root，指向了这树的根节点（节点A），则可以像下面这

14、样使用 PreOrderTraverse ( Root ),遍历示例,二叉树先序遍历程序的原理,进入函数内部. printf(Root-data);.输出A PreOrderTraverse (Root-leftChild);/节点B printf(节点B-data);.输出B PreOrderTraverse (节点B-leftChild);/节点D printf(节点D-data);.输出D PreOrderTraverse (节点D-leftChild);/空节点 为空，不执行任何操作，函数退出，回到上一层 PreOrderTraverse (节点D-rightChild);/空节点 为

15、空，不执行任何操作，函数退出，回到上一层 以节点D为根的子树遍历完成（节点B左子树遍历完成）,二叉树先序遍历程序的原理,进入函数内部. PreOrderTraverse (节点B-rightChild);/节点E printf(节点E-data);.输出E PreOrderTraverse (节点E-leftChild);/空节点 为空，不执行任何操作，函数退出，回到上一层 PreOrderTraverse (节点E-rightChild);/空节点 为空，不执行任何操作，函数退出，回到上一层 以节点E为根的子树遍历完成，节点B右子树遍历完成，这样节点B为根的子树遍历完成，函数退出，转到上一层

16、,二叉树先序遍历程序的原理,进入函数内部. PreOrderTraverse (Root-rightChild);/节点C printf(节点C-data);.输出C PreOrderTraverse (节点C-leftChild);/空节点 为空，什么都不做，函数直接退出，回到上一层 PreOrderTraverse (节点C-rightChild);/节点F printf(节点F-data);.输出F PreOrderTraverse (节点F-leftChild);/空节点 为空，不执行任何操作，函数退出，回到上一层 PreOrderTraverse (节点F-rightChild);/

17、空节点 为空，不执行任何操作，函数退出，回到上一层 以节点F为根的子树遍历完成，节点C右子树遍历完成，这样节点C为根的子树遍历完成，而整个函数的执行也就完成了。,二叉树先序遍历程序的原理,可见，遍历操作这种“不可思议”的简单性，完全是由于递归本身的特性所决定的。 递归这种方法在树的操作中应用及其广泛，后面将会看到更多的例子。,二叉树中序遍历的非递归实现,算法6.2与算法6.3，不要求能写出，但建议课下进行理解。,二叉树的层次遍历,层次遍历需要借助一个队列完成，基本过程如下： 根节点入队 如果队列不空，则做以下循环 出队并访问 如果出队节点的左右子树不为空，则按顺序将左右子树的根节点入队,二叉树

18、的建立,二叉树的建立是在遍历算法的基础上实现的，在一个递归的过程中逐渐将其建立。,二叉树的建立,不妨仍然以递归程序设计的三要素来分析二叉树的建立过程。 结束条件：输入了一个约定的特殊字符，则建立空树并结束。 与原问题形式相同，但规模更小的子问题：建立根节点的左（右）子树。 对子问题的操作：建立根节点，建立根节点的左子树，建立根节点的右子树。 思考：如果运用如上描述的过程建立一棵树，应该按照何种遍历（顺序）输入数据？ 算法6.4,二叉树的建立,以一个简单的序列为例分析这个程序。,输入：A B C ,二叉树的建立,输入A，建立树的根节点A 开始建立A的左子树 接受到输入B，建立节点A左子树的根节点

19、B 开始建立节点B的左子树 接受到特殊字符，结束 开始建立节点B的右子树 接受到特殊字符，结束。 A的左子树完成,二叉树的建立,开始建立A的右子树 接受到输入C，建立节点A右子树的根节点C 开始建立节点C的左子树 接受到特殊字符，结束 开始建立节点C的右子树 接受到特殊字符，结束。 A的右子树完成 整个树建立完成,二叉树的建立,另一个简单的序列。,输入：A B ,二叉树的建立,课本给出的输入序列,输入：A B C D E G F ,根据遍历序列确定二叉树,对一棵二叉树，可以写出前/中/后序三种遍历序列，根据遍历序列能够“倒推”出二叉树吗？ 尽管上一部分展示的二叉树建立过程使用的就是一个遍历序列

20、，但是这个序列中包含了表示空树的特殊符号，它并不是“标准的”遍历序列。 思考：给定一个标准的遍历序列（不含表示空树的符号），能确定唯一的二叉树吗？如果给定两个呢？,根据遍历序列确定二叉树,下面两个树具有相同的先序遍历序列,根据遍历序列确定二叉树,下面两个树具有相同的中序遍历序列。,根据遍历序列确定二叉树,而下面两个树具有相同的，包含空树符号的中序遍历序列。 B A C ,根据遍历序列确定二叉树,所以，根据单个序列无法确定唯一的二叉树，那么两个呢？ 有以下结论成立：根据先序序列和中序序列，或是后序序列和中序序列，可以确定唯一的一棵二叉树，但根据先序序列和后序序列是不行的。,根据遍历序列确定二叉树

21、,先序序列：A B C D E F G 中序序列: C B E D A F G 根据这两个序列来确定一棵唯一的二叉树,根据遍历序列确定二叉树,先序序列和中序序列的特点 先序序列：根节点是序列中的第一个 中序序列：左子树的遍历序列在根节点之前，右子树的遍历序列在根节点之后。,根据遍历序列确定二叉树,根据先序序列，可以知道该树的根节点是A，而根据先序序列，可以知道左子树包含BCDE三个节点，而右子树包含FG两个节点。但左右子树的具体结构尚不清楚。,A,B,C,D,E,F,G,根据遍历序列确定二叉树,可知对节点A的左子树而言，其先序序列为BCDE，中序序列为CBED。于是左子树的根节点为B，左子树的

22、左子树只有一个节点C，右子树有两个节点E和D。,A,B,D,E,F,G,C,根据遍历序列确定二叉树,现在只关注节点B的右子树，其先序序列为DE中序序列为DE，因此D为根节点，E为左子树。,A,B,F,G,C,D,E,根据遍历序列确定二叉树,再关注根节点A的右子树，其先序序列和中序序列都为FG，因此F为根节点，G为右子树。,A,B,C,D,E,F,G,根据遍历序列确定二叉树,复杂一点的例子： 先序序列：E B A D C F H G I K J 中序序列：A B C D E F G H I J K 如何用程序实现这一过程？建议课下研究和练习。,根据遍历序列确定二叉树,6.5二叉树的其他操作,递归

23、,正如我们在前面的分析中所见，与树相关的概念和操作大都会涉及到递归。,递归,一个函数调用另一个函数是非常常见的，那么思考：一个函数能不能自己嵌套调用自己？ 从原理上讲，是完全可能的 如果“原封不动”的调用自身，就会陷入循环调用直到栈溢出，所以函数调用自身必须是有条件的，即在特定情况下可以退出,递归,一个函数调用另一个函数是非常常见的，那么思考：一个函数能不能自己嵌套调用自己？ 从原理上讲，是完全可能的 如果“原封不动”的调用自身，就会陷入循环调用直到栈溢出，所以函数调用自身必须是有条件的，即在特定情况下可以退出,调用自身的例子,递归,递归：一个函数在执行过程中，直接或者间接地调用自己。 适于用

24、递归方法解决的问题的两个特征 当问题小于一定的规模时，可以直接给出答案 当问题的规模较大时，可以化简为对一个“与原问题相同，但规模小一些的问题”的简单操作来完成,递归,递归程序设计的三要素 寻找结束条件：当问题简单到某个程度时，可以直接得到答案。 寻找子问题：与原问题结构一样，但规模更小 设计利用子问题解决原问题的方法，如何操作子问题才能解决原问题,递归,例子一：求N的阶乘,int N(int n) if(n = 0) return 1; else return n * N(n-1); ,递归,例子二：求字符串的长度,int Len(char* s) if(*s = 0) return 0;

25、else return 1 + Len(s+1); ,求树中节点的个数,思路1:在任意一种遍历过程中，当遇到一个节点时就令计数器+1. 思路2：直接计算 结束条件：空树有零个节点。 子问题：左子树的节点数，右子树的节点数 对子问题的操作：树的节点数=左子树节点数+右子树节点数+1,求树中叶子节点的个数,思路1:在任意一种遍历过程中，当判断某个节点的左右子树都为空时就令计数器+1. 思路2：直接计算 结束条件：当一个树的左右子树都为空时，则有一个叶子节点。当一个树为空时，有零个叶子节点。 子问题：左子树的叶子节点数，右子树的叶子节点数 对子问题的操作：树的叶子节点数=左子树叶子节点数+右子树叶子

26、节点数,求树的高度,结束条件：空树的高度为0 子问题：左子树的高度，右子树的高度 对子问题的操作：树的高度=max(左子树高度+右子树高度)+1,判断两棵树是否具有相同的结构,结束条件：两棵空树的结构相同。如果一个不空一个空，则不相同 子问题：左子树结构相同，右子树结构相同 对子问题的操作：两棵树结构相同 if 他们的左子树结构相同 /结点数据 typedef struct /树结点定义 TreeData data; int parent; TreeNode; typedef TreeNode TreeMaxSize; /树,树的物理存储,优点：节省存储空间，求双亲很简便 缺点：寻找子节点复杂

27、,树的物理存储,孩子表示法 思路一：照搬二叉链表的实现方法，但如何才能处理不确定个数的子节点呢？ 所有节点都是同样的结构，包含“最大度”个指针域。（浪费空间，操作简便） 节点不同构，每个节点依包含的子节点个数而具有不同的构造。（浪费空间，操作复杂） 可见，思路一的实用性并不强。,树的物理存储,孩子表示法思路二 将树的节点设计为一个结构体变量，每个结构体变量有两个成员，一个是数据，一个是指针域。 将所有节点组织成线性表。 线性表中每个元素的指针域指向一个单链表，链表中每个元素数据域的含义为“树中该节点的子节点在线性表中的位置”。 用一个指针指向线性表中表示根节点的元素。 图6.14（a).,树的

28、物理存储,可以将上面的思路与双亲表示法相结合 图6.14（b).,树的物理存储,孩子表示法的类型定义,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;,树的物理存储,孩子-兄弟表示法 仍然用二叉链表表示树的结点，只不过两个指针域进

29、行分工。 左指针域指向第一棵子树的根结点，右指针域指向第一个兄弟结点。,树的物理存储,孩子-兄弟表示法,结点结构,树与二叉树的转换,孩子-兄弟表示法使得树与二叉树都可以用二叉链表来表示。 也可以理解为，对于一棵用二叉链表构成的树，即可以理解为二叉树，也可以理解为一个普通的树。 从这个角度，树与二叉树是对应的。,树与二叉树的转换,树的观点,二叉树的观点,二叉树与森林的转换,容易发现，由树转化而成的二叉树，其根节点只有左子树。 对于一个包含N棵树的森林，以其中第一棵树的根节点作为根节点，第一棵树的其余部分构成根节点的左子树，剩余N-1棵树转化成的二叉树作为根节点的右子树。 这个过程仍然是递归的，因

30、为在其描述中，用到了这一过程本身。 结束条件：一棵树可以直接转化成二叉树。 子问题：N-1棵树组成的森林转化为二叉树。 子问题的操作：第一棵二叉树+其余部分转化成的树。,二叉树与森林的转换,二叉树与森林的转换,二叉树与森林的转换,从二叉树到森林的转化，以根节点和其左子树转化成森林中的第一棵树。剩余部分仍然是一个二叉树，针对剩余部分组成的二叉树重复这个过程。,树与森林的遍历,遍历树 先序遍历树 后序遍历树,树与森林的遍历,先序：ABEFCDG 后序：EFBCGDA,先序：ABEFCDG 中序：EFBCGDA,树与森林的遍历,树的先序遍历中：根节点最先被访问，节点的子树其次访问，节点的兄弟最后访问。而当树转化成二叉树时，子树变为左子树，节点的兄弟变为右子树，因此树先序遍历的结果与其对应二叉树表示的先序遍历结果相同。,树与森林的遍历,树的后序遍历中：节点的子