《数据结构第六章树和二叉树》由会员分享，可在线阅读，更多相关《数据结构第六章树和二叉树（87页珍藏版）》请在金锄头文库上搜索。
1、第六章 树和二叉树,6.1 树的类型定义,6.2 二叉树的类型定义,6.3 二叉树的存储结构,6.4 二叉树的遍历,6.5 线索二叉树,6.6 树和森林,6.7 树和森林的遍历,6.8 哈夫曼树与哈夫曼编码,一、树的定义树是n（n0）个结点的有限集。当n=0时称为空树；在任意一棵非空树中，有且仅有一个称为根的结点，其余的结点可分为m(m 0)个互不相交的有限集T1,T2,Tm,其中每一个集合又称为一棵树，并且称为根的子树。同理，每一棵子树又可以分为若干个互不相交的有限集,6.1 树的类型定义,A,B,C,D,E,F,G,H,I,J,M,K,L,A( B(E, F(K, L), C(G), D(
2、H, I, J(M) ),T1,T3,T2,树根,例如:,线性结构,树型结构,第一个数据元素(无前驱),根结点(无前驱),最后一个数据元素(无后继),多个叶子结点(无后继),其它数据元素 (一个前驱、一个后继),其它数据元素 (一个前驱、多个后继),对比树型结构和线性结构的结构特点,数据对象 D：,D是具有相同特性的数据元素的集合。,若D为空集，则称为空树 。 否则:(1) 在D中存在唯一的称为根的数据元素root；(2) 当n1时，其余结点可分为m (m0)个互不相交的有限集T1, T2, , Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。,数据关系 R：,二、抽象数
3、据类型树的定义,ADT Tree,基本操作：,查 找 类,插 入 类,删 除 类,ADT Tree,Root(T) / 求树的根结点,查找类：,Value(T, cur_e) / 求当前结点的元素值,Parent(T, cur_e) /求当前结点的双亲结点,LeftChild(T, cur_e) /求当前结点的最左孩子,RightSibling(T, cur_e) /求当前结点的右兄弟,TreeEmpty(T) /判定树是否为空树,TreeDepth(T) /求树的深度,TraverseTree( T, Visit() ) /遍历,InitTree(&T) / 初始化置空树,插入类：,Crea
4、teTree(&T, definition) / 按定义构造树,Assign(T, cur_e, value) / 给当前结点赋值,InsertChild(&T, &p, i, c) / 将以c为根的树插入为结点p的第i棵子树,ClearTree(&T) / 将树清空,删除类：,DestroyTree(&T) / 销毁树的结构,DeleteChild(&T, &p, i) / 删除结点p的第i棵子树,树的结点：包含一个数据元素及若干个指向其子树的分支；结点的度：一个结点拥有的子树数目；树的度：一棵树上所有结点度的最大值；叶子结点（终端结点）：度为零的结点；分支结点（非终端结点） ：度大于零的结
5、点；(从根到结点的)路径：由从根到该结点所经分支和结点构成；,三、基本术语,D,H,I,J,M,孩子结点：结点的子树的根称为该结点的孩子结点；双亲结点：相应地，该结点称为孩子的双亲结点；兄弟：具有同一父结点的子结点互称兄弟；堂兄弟：其双亲在同一层的结点互为堂兄弟；祖先结点：从根到该结点所经分支上的所有结点；子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙；,A,B,C,D,E,F,G,H,I,J,M,K,L,结点的层次：从根结点到该结点所经过的路径长度加1；树的深度：树中叶子结点具有的最大层次数；有序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树；第一
6、个孩子：在有序树中，最左边的子树的根称为第一个孩子；最后一个孩子：最右边 的子树的根称为最后一个 孩子；,A,B,C,D,E,F,G,H,I,J,M,K,L,森林：是m(m 0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。,任何一棵非空树是一个二元组Tree = （root，F） 其中：root 被称为根结点F 被称为子树森林,树T的结点总数n(n0)等于其所有结点的出度之和加1。 深度为K的树（K叉树）第i(i 1)层至多有Ki-1个结点。 深度为h的k(k1)叉树至多有 个结点。具有n个结点的k叉树的最小深度为logk(n(k-1)+1) 。,树的性质,一、二叉树的定义
7、,二叉树是n (n0) 个结点的有限集合，这个集合或是空集，或是由一个根结点以及两棵互不相交的、被称为根的左子树和右子树所组成；左子树和右子树分别又是一棵二叉树。 特点： 每个结点至多只有两棵子树， 且二叉树的子树有左右之分，其次 序不能任意颠倒。,6.2 二叉树的类型定义,根结点,左子树,右子树,二、二叉树的五种基本形态：,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,三、二叉树的主要基本操作：,查 找 类,插 入 类,删 除 类,Root(T) /求根函数；Value(T, e); /求结点函数；Parent(T, e); /求双亲函数；
8、LeftChild(T, e)或RightChild(T, e); /求孩子结点函数；LeftSibling(T, e)或RightSibling(T, e); /求兄弟函数；BiTreeEmpty(T); /树判空函数；BiTreeDepth(T); /求树深度函数；PreOrderTraverse(T, Visit(); /先序遍历操作 InOrderTraverse(T, Visit(); /中序遍历操作 PostOrderTraverse(T, Visit(); /后序遍历操作 LevelOrderTraverse(T, Visit(); /层序遍历操作,查找类：,InitBiTree
9、( /插入子树操作；,插入类,ClearBiTree( / 删除子树操作,删除类,性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。(i1),四、二叉树的重要特性：,A,B,D,E,F,H,J,M,K,L,第2层,第3层,第4层,i = 1 时，只有一个根结点，显然 2 i-1 = 20 = 1 正确；,假设对所有的 j，1 j i，命题成立，即第j层上至多有2 j-1个结点。那么可以证明j=i时命题也成立。,用归纳法证明：,由归纳假设：第i-1层上至多有2 i-2个结点。由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2*2 i-2=2
10、 i-1,性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k1）。,证明：,基于上一条性质，深度为 k 的二叉树上的结点数至多为20+21+ +2k-1 = 2k-1 。,性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。,证明：,设 二叉树上结点总数 n = n0 + n1 + n2 又 二叉树上分支总数 b = n1+2n2 除根结点之外，其余结点都有一个分支进入，所以 b = n-1 = n0 + n1 + n2 - 1 由此， n0 = n2 + 1 。,两类特殊的二叉树：,满二叉树：指的是深度为k且含
11、有2k-1个结点的二叉树。,特点: 每一层上的结点数都是最大结点数。,完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。,特点: 叶子结点只可能在层次最大的两层上出现； 对任意结点，若其右分支下的子孙的最大层次为L，则其左分支下的子孙的最大层次必为L或L+1 ；,性质 4 ： 具有 n 个结点的完全二叉树的深度为 log2n +1 。,证明：,设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2
12、i+1 的结点为其右孩子结点。,6.3 二叉树的存储结构,二、二叉树的链式存储表示,一、 二叉树的顺序存储表示,用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。对于一般二叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量中。,1,2,3,4,5,6,7,8,9,10,11,12,1,2,3,4,5,0,0,0,0,6,7,完全二叉树 一般二叉树,1,2,3,4,5,7,8,9,10,11,12,6,1,2,3,4,5,6,7,一、 二叉树的顺序存储表示,#define MAX_TREE_SIZE 100 / 二叉树的最大结点数 typedef
13、TElemType SqBiTreeMAX_TREE_SIZE; / 0号单元存储根结点 SqBiTree bt;,二、二叉树的链式存储表示,1. 二叉链表,2三叉链表,3双亲链表,4线索链表,root,结点结构:,1. 二叉链表,含有两个指针域的结点结构,typedef struct BiTNode / 结点结构TElemType data;struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;,结点结构:,C 语言的类型描述如下:,root,2三叉链表,结点结构:,含有三个指针域的结点结构,typedef struct Tri
14、TNode / 结点结构TElemType data;struct TriTNode *lchild, *rchild; / 左右孩子指针struct TriTNode *parent; /双亲指针 TriTNode, *TriTree;,结点结构:,C 语言的类型描述如下:,一、问题的提出,二、先左后右的遍历算法,三、算法的递归描述,四、中序遍历算法的非递归描述,五、遍历算法的应用举例,6.4 二叉树的遍历,顺着某一条搜索路径巡访二叉树 中的结点，使得每个结点均被访问一 次，而且仅被访问一次。,一、问题的提出,“访问”的含义可以很广，可以对结点作各种处理，如：输出结点的信息等。,“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，,每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。,对“二叉树”而言，可以有三条搜索路径：,1先上后下的按层次遍历；2先左(子树)后右(子树)的遍历；3先右(子树)后左(子树)的遍历。,二、先左后右的遍历算法,先（根）序的遍历算法,中（根）序的遍历算法,后（根）序的遍历算法,若二叉树为空树，则空操作；否则， （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。,
