《数据结构之树课件》由会员分享，可在线阅读，更多相关《数据结构之树课件（120页珍藏版）》请在金锄头文库上搜索。
1、数据结构,第6章 树,第六章 树,知 识 点 二叉树及二叉树的存储结构 二叉树的遍历 树的基本概念 二叉排序树 哈夫曼树 难 点 二叉树遍历算法的设计 修改二叉树遍历算法，进行二叉树其它相关的操作，解决实际应用问题,要 求熟练掌握以下内容: 理解树形结构的基本概念和术语 二叉树定义和存储结构 二叉树的遍历次序及二叉树遍历算法了解以下内容： 树和二叉树之间的相互转换方法 线索二叉树的建立及遍历算法 树的应用：二叉排序树和哈夫曼树,第6章 树,6.1 树的定义和基本术语 6.2 二叉树 6.3 二叉树的遍历 6.4 线索二叉树 6.5 树的应用 6.6 应用实例及分析 小结 习题与练习,6.1 树
2、的定义,树的定义 树是n个结点的有限集合T，在一棵非空树中（n0）有且仅有一个称作根的结点；其余结点分为m个（m0）互不相交的集合T1，T2Tm，其中，每一个集合本身又是一棵树,并称为根的子树。 当n=0时，称为空树。 有限集合T1，T2Tm “互不相交”，即任意两个集合不能有相同的结点。 树的各个结点有不同层次关系，这种关系通常用图形表示，但与自然界的树木相反，习惯上将整棵树的根画在最上层，如图6.1所示。,图6.1 树的表示法,树的其它表示法,嵌套集合表示法凹入表示法- 杜威(Deway)记数法广义表表示法,树的基本术语,1. 结点的度(Degree)：树中每个结点具有的子树数或者后继结点
3、数称为该结点的度。2.度数为0的结点(即没有子树的结点)叫作末端结点或叶子结点,其它结点称为内部结点。3. 树的度：一棵树中各个结点度数的最大值叫做这个树的度。,4. 儿子结点和父亲结点：一个结点的子树的根或者后继结点称为该结点的儿子结点，反之，该结点则称为其后继结点的父亲结点。 5. 兄弟结点：同一个结点的儿子结点之间互称为兄弟结点。,6. 子孙结点和祖先结点：一个结点的子树中所有结点均称之为该结点的子孙结点。反之，从根结点到达一个结点的路径上的所有结点，都叫做该结点的祖先结点。 7. 树的深度：树是一种层次结构，树中结点的层次（Level）是从根结点算起的。根结点为第一层，其儿子结点为第二
4、层。其余各结点的层数逐层由上而下计算。一棵树中结点的最大层数叫做此树的深度或高度。 8. 森林：n个树的集合叫森林(Forest)。,树形结构的逻辑特征,树形结构的逻辑特征可用树中结点之间的父子关系来描述： 树中任一结点都可以有零个或多个直接后继结点（即儿子结点），但至多只能有一个直接前趋结点（即父亲结点）。 树中只有根结点无前趋，它是开始结点； 叶结点无后继，它们是末端结点。 树形结构是非线性结构。,返回,树的基本操作,1. SETNULL(T)置T为空树2. ROOT(T)或ROOT(x)求树T或求结点X所在树的根 3. PARENT(T, x)求树T中结点X的父亲 4. CHILD(T,
5、 x, i)求树T中结点X的第I个儿子,返回,5. TNULL(T)判断树T是否为空树 6. DEPTH(T)求树T的深度 7. INSERT(T, x)结点的插入 8. DELETE(T, x)结点的删除 9. VISIT(T) 树的遍历,6.2 二叉树的定义及其性质,二叉树的定义一棵二叉树是n个结点的有限集合（n0），此集合或者是空集（n=0），或者是由一个根结点及两棵互不相交的、分别称为左子树和右子树的二叉树组成。 由上述定义可知，二叉树可以是空集，其根可以有左子树或右子树,也可以没有左子树或右紫树.二叉树的子树有左, 右之分, 左右不能颠倒.一般地，二叉树有五种基本形态，如图6.2所示
6、。,图6.2 二叉树的基本形态,(a) 空二叉树 (b) 仅有一个根结点的二叉树 (c) 右子树为空的二叉树 (d)左子树为空的二叉树 (e)左、右子树均非空的二叉树,二叉树的基本术语.二叉树的基本操作,二叉树的性质性质1. 在二叉树第 k 层上至多有2k-1个结 点。性质2. 深度为 k 的二叉树至多有2k -1个结 点。（k=1) .,性质3. 对任一二叉树BT，若其末端结点数为n0，度为2的结点数为n2，则 n0=n2+1 证: 设二叉树有n个结点, 度为1的结点数为n1, 则 n = n0+n1+n2 ;另一方面, 度为1的结点有1个儿子, 度为2的结点有2个儿子, 故二叉树中儿子总数
7、(除根结点外)为 n1+2*n2, 所以二叉树的结点总数又可表示成 n=n1+2*n2+1所以 n0=n2+1,满二叉树,在一个二叉树中，若第 I 层的结点数为2i-1，则称该层的结点数是满的，当树中的每一层都是满的，则称此二叉树为满二叉树。例如果一个二叉树中，除最下一层的各结点度数为0以外，其它各层结点的度数均等于2，则此二叉树为满二叉树。,满二叉树的第一层有一个结点（即根结点），第二层有两个结点，依此类推。每一层的结点数都是上一层结点数的二倍。所以，在满二叉树的第i层共有2i-1个结点（i1），一个深度为k的满二叉树的结点总数为2k1.,图6.3 满二叉树,完全二叉树,如果一个二叉树各层都
8、是“满”的，只是最下面一层从右边起连续缺若干个结点，这种二叉树叫做完全二叉树。,性质4. 一棵具有n个结点的完全二叉树的深度为log2n +1 证：由定义知： 2k-1-1n 2k-1 即 2k-1 n 2k 取对数 k-1logn k由 k-1logn 可知： klogn+1即k log2n +1 有 logn 1，则其父结点编号为 i/2 。 2) 如果2in，则其左儿子结点编号为2i；若2in，则无左儿子结点。 3) 如果（2i+1）n，则其右儿子结点编号为（2i+1）；反之，则无右儿子结点。 例:,二叉树的存储结构1. 二叉树的顺序存储结构：对于满二叉树和完全二叉树来说，可以采用“以编
9、号为地址”的方法，将编号为i的结点存入一维数组的第i个单元。图6.3所示的完全二叉树按此方法存入数组中如下图6.4所示。,图6.4 二叉树的顺序存储结构,这种存储结构适用于完全二叉树和满二叉树。 如果某二叉树不是完全二叉树，中间有一些结点不存在，则采用顺序存储结构时，数组中必然要有一些空闲单元，浪费存储空间.,图6.5 非完全二叉树的顺序表示,图6.5中的二叉树,采用顺序存储结构时,一维数组的21单元中只用上了7个。,2. 二叉树的链式存储结构：由二叉树的定义可知：其结点由信息部分和指向其左右儿子的指针组成，因此可把二叉树的结点定义成：信息域，左指针域，右指针域。也可以增加一个指向父亲的指针，
10、如下：图6。5可表示成：,结点定义,链式存储结构的结点定义如下： typedef struct BTnode elementtype data;struct BTnode *Lchild;struct BTnode *Rchild; BTree; 这里的elemeenttype可以是任何相应的数据类型如int、float或char等。,6.3 二叉树的遍历,二叉树的遍历(Traversal)是指按一定的顺序访问二叉树的每个结点，且每个结点只被访问一次的过程。 对二叉树的遍历过程实际上是将非线性结构的二叉树中的结点排列成一个线性序列的过程。 对于用顺序法表示的二叉树，各结点在数组中的编号很有规律
11、，其遍历较容易进行，但对于用链式存储结构表示的二叉树，进行遍历就复杂一些，故本节仅讨论链式存储形式的二叉树遍历过程。,一个非空的二叉树由根结点及左、右子树这三个基本部分组成，因此若能依次遍历这三部分，便是遍历了整个二叉树。 在任一给定结点上，可以按某种次序执行三个操作：访问结点本身，遍历该结点左子树，遍历该结点右子树，操作排列次序： 左、根、右； 根、左、右； 左、右、根； 右、根、左； 根、右、左； 右、左、根； 由于实际问题一般都是要求左子树较右子树先遍历，故只采用其中、三种遍历次序，分别称为中序遍历、先序遍历和后序遍历。,三种遍历次序以递归的形式定义： (1) 中序（Inorder）遍历
12、 若遍历的二叉树为空，执行空操作；否则依次执行下列操作： 中序遍历左子树； 访问根结点； 中序遍历右子树。 (2) 先序（Preorder）遍历 若遍历的二叉树为空，执行空操作；否则依次执行下列操作： 访问根结点； 先序遍历左子树； 先序遍历右子树。,(3) 后序（Postorder）遍历 若遍历的二叉树为空，执行空操作；否则依次执行下列操作： 后序遍历左子树； 后序遍历右子树； 访问根结点。,图6.9 二叉树遍历,中序遍历序列：H，D，I，B，E，A，F，C，G。 先序遍历序列：A，B，D，H，I，E，C，F，G。 后序遍历序列：H，I，D，E，B，F，G，C，A。,先序遍历递归算法,voi
13、d preorder(btree *BT) if (BT！=NULL)printf(“%d“,BT-data);preorder(BT-lchild);preorder(BT-Rchild); ,先序遍历非递归算法,基本思想：先访问根结点，并进栈，再访问左儿子，并进栈, , 直到左儿子为空；退栈，并访问其右儿子, ；重复以上过程，栈空为止。,先序遍历非递归算法,#define maxsize void Nr-preorder(btree *BT) btree *Smaxsize,*p; /*定义栈S ，中间变量P */int top=0; p=bt;while (p!=null)|(top!=
14、0) while(p!=null) stop=p; /*若P非空，则进栈*/top+;printf(“ %d”, p-data); /*输出p=p-lchild; /*取其左儿子*/,先序遍历非递归算法（续）,if (top!=0) top-;p=stop; /*退栈至P中*/p=p-rchild; /*取其右儿子*/,中序遍历递归算法,void inorder(btree *BT) if (BT！=NULL)inorder(BT-lchild);printf(“%d“,BT-data);inorder(BT-Rchild); ,中序遍历非递归算法,void Nr-inorder(btree
15、*BT) btree *Smaxsize,*p; /*定义栈S ,中间变量P */int top=0; p=bt;while (p!=null) | (top!=0) while(p!=null) stop=p; /*若P非空，则进栈*/top+;p=p-lchild; /*取其左儿子*/,中序遍历非递归算法（续）,if (top!=0) top-;p=stop; /*退栈至P中*/printf(“ %d“, p-data);p=p-rchild; /*取其右儿子*/,后序遍历,方法1:按照 先根、右子树、左子树的顺序遍历二叉树，得到的结果与后序遍历的结果相反。根据这一事实，可以对二叉树按以上顺序遍历，之后颠倒过来即可。,方法2：先序遍历、中需遍历时，每个结点只有1次进栈和1次出栈。后序遍历时，每个结点要2次进栈，也就是说，每个结点要进2次，出2次。所以，要设一个标志flag, 以记住是第1次进栈还是第2次进栈。该标志与指针同时进出栈。取左儿子时，flag=0取右儿子时，flag=1在第二次出栈时访问该结点。,
