数据结构(第二版) 郑泳 方风波 第六章 树新.pptVIP

第六章 树 知识教学目标 树和二叉树的概念、存储结构及相互转换的方法 二叉树性质的应用 二叉树遍历算法的应用 哈夫曼树的生成及编码 能力培养目标 树和二叉树的概念、存储结构及相互转换的方法 二叉树的定义、性质和存储结构 二叉树的遍历方法及算法 树与二叉树的相互转换 二叉树遍历算法的应用 二叉树的非递归遍历算法 线索二叉树的生成、存储及遍历 二叉树的递归编程应用 6.1 树的概念 6.1.1 树的定义 树（tree）是n（n≥0）个结点的有限集合T，当n=0时称为空树，在一棵非空树（n＞0）中满足如下两个条件： 1）有且仅有一个特定的称为根（root）的结点； 2）当n1时，其余结点可分为m（m ≥ 0）个互不相交的有限集合T1 ，T2，…，Tm，其中每个集合又是一棵树，并称其为根的子树（subtree）。 除树形表示外，通常还有三种表示法 6.1.2 树的基本术语 1) 结点的度 2) 树的度 3) 分支结点 4) 叶子结点 5) 子结点 6) 双亲结点（父结点） 7)祖先结点、子孙结点 8) 兄弟结点、堂兄弟结点 9) 结点层数 10) 树的深度（高度） 11) 有序树 12) 无序树 13) 森林 6.1.3 树的基本操作 1) SetNull（T） 2) Root（T）或Root(x) 3) Parent（T，x） 4) Child（T，x，i） 5) Create（x，F） 6) AddChild（y，i，x） 7) DelChild（x，i） 8) Traverse（T） 6.2 二叉树 6.2.1二叉树的定义 递归定义：二叉树是n(n ≥0)个结点有限集，当n=0时称为空树；当 n0 时，有而且仅有一个结点为根结点，其余结点构成2个互不相交的子集T1，T2，其中每一个子集又是一棵二叉树，分别称做为根结点的左子树和右子树。 6.2.2 二叉树的性质 【性质1】 在二叉树的第i层上至多有2i-1个结点(i≥1)。 【性质2】 深度为k的二叉树至多有2k-1个结点（k≥1）。 【性质3】 对任意一棵二叉树T，若终端结点数为n0，而其度数为2的结点数为n2，则n0= n2+1。 【性质4】 具有n个结点的完全二叉树的深度为+1。其中表示不大于log2n的最大整数。 【性质5】 对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点有： 1) 如i=1，则序号为i的结点是根结点，无双亲结点；如i1，则序号为i的结点的双亲结点序号为。 2) 如2×in，则序号为i的结点无左孩子；如2×i≤n，则序号为i的结点的左孩子结点的序号为2×i。 3) 如2×i＋1n，则序号为i的结点无右孩子；如2×i＋1≤n，则序号为i的结点的右孩子结点的序号为2×i＋1。 6.2.3 二叉树的存储结构 1. 顺序存储结构 二叉树顺序存储的类型定义类似于顺序表，如下表示： #define MaxSize 101 //假定最大容量为101 typedef char DataType; typedef struct { DataType data[MaxSize]; //data[0]存放二叉树结点的个数，data[1]存放根结点 int n; //存放最后一个结点的下标，表当前的长度为n+1 }SeqTree; 2.链式存储结构 二叉链表和三叉链表的结点表示 6.3 遍历二叉树 6.3.1 二叉树遍历方法 1) 先序遍历（DLR）操作过程： 若二叉树为空，则空操作；否则： 访问根结点；按先序遍历左子树；按先序遍历右子树。 2) 中序遍历（LDR）操作过程： 若二叉树为空，则空操作；否则： 按中序遍历左子树；访问根结点；按中序遍历右子树。 3) 后序遍历（LRD）操作过程： 若二叉树为空，则空操作；否则： 按后序遍历左子树；按后序遍历右子树；访问根结点。 6.3.2 二叉树遍历的递归算法 【算法6.1】 先序遍历递归算法。 void Prev(NODE *root) { if(root!=NULL) { printf(“%d”,root-data); //输出结点 Prev(root-Lchild); //先序遍历左子树 Prev(root-Rchild); //先序遍历右子树 } } 【算法6.2】 中序遍历递归算法。 void Mid(NODE *root) { if(root!=NULL) { Mid(root-Lchild); //中序遍历左子树