《数据结构 第06章 树与二叉树》由会员分享，可在线阅读，更多相关《数据结构 第06章 树与二叉树（120页珍藏版）》请在金锄头文库上搜索。
1、第6章 树和二叉树,6.1 树的定义及其存储结构 6.2 二叉树 6.3 遍历二叉树和线索化二叉树 6.4 树、森林和二叉树的关系 6.5 哈夫曼树及其应用,6.1 树的定义及其存储结构,树是 n (n 0) 个结点的有限集合，记为T。,当n=0时，称之为空树； 否则，该集合满足如下条件: (1) 存在唯一的称为根(root)的结点没有前趋，但可以有 0 个或多个直接后继； (2) 其余 n-1 个结点可分为m (m0)个互不相交的有限集 T1, T2, , Tm, 其中每一个子集本身又是一棵符合本定义的树，称为根root的子树。,6.1.1 树的定义及基本术语,A,B,C,D,E,F,G,H
2、,I,J,M,K,L,A( ),树根,例如:,B(E, F(K, L),C(G),D(H, I, J(M),基 本 术 语,结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素+若干指向子树的分支,分支的个数,树中所有结点的度的最大值,度为零的结点,度大于零的结点,D,H,I,J,M,(从根到结点的)路径：,孩子、双亲、 兄弟、堂兄弟 祖先、子孙,结点的层次:,树的深度：,由从根到该结点所经分支和结点构成,假设根结点的层次为1,第l 层结点的孩子结点的层次为l+1,树中叶子结点所在的最大层次,() 有确定的根； () 树根和子树根之间为有向关系。,有向树：,有序树：,子树之间存在确定
3、的次序关系。,无序树：,子树之间不存在确定的次序关系。,任何一棵非空树是一个二元组Tree = （root，F） 其中：root 被称为根结点，F 被称为子树森林,森林：,是 m（m0）棵互 不相交的树的集合,A,root,F,对比树型结构和线性结构的结构特点,线性结构,树型结构,第一个数据元素(无前驱),根结点(无前驱),最后一个数据元素(无后继),多个叶子结点(无后继),其它数据元素 (一个前驱、一个后继),其它数据元素 (一个前驱、多个后继),6.1.2 树的存储结构,1、双亲数组表示法,2、孩子链表表示法,3、树的二叉链表(孩子-兄弟）存储表示法,r=0 n=7,data parent
4、,1、双亲数组表示法P123,typedef struct PTNode TElemType data;int parent; / 双亲位置域 PTNode;,#define MaxTreeSize 100,结点结构:,双亲数组表示法类型描述:,typedef struct PTree PTNode nodesMaxTreeSize;int r, n; / 根结点的位置和结点个数 PTree;,树结构:,r=0 n=7,data parent firstchild,2、孩子链表表示法P124,-1000224,typedef struct CTNode int child; / 数组下标str
5、uct CTNode *next; *ChildPtr;,孩子结点结构:,孩子链表类型描述:,typedef struct CTBoxTElemType data; / 结点的值ChildPtr firstchild; / 孩子链的头指针 CTBox;,顺序表结点：,typedef struct CTBox nodesMaxTreeSize;/ 双亲结点结构数组int n, r ; / 结点数和根结点的位置 CTree;,孩子链表类型（树结构）:,root,3、树的二叉链表 (孩子-兄弟) 表示法-P125,root,森林的 二叉链表表示,typedef struct CSNode TElem
6、Type data;struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;,树的二叉链表类型描述:,结点结构:,6.2 二 叉 树,6.2.1 二叉树的定义,二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,根结点,左子树,右子树,E,F,二叉树的 5 种基本形态：,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,6.2.2 二叉树的性质,性质 1 ： 在二叉树的第 i (i1)层上至多有 2i-1 个结点。,用归纳法证明：归纳基：归纳假设：归纳证
7、明：,i = 1 层时，只有一个根结点，2i-1 = 20 = 1；,假设对所有的 j，1 j i，命题成立;,二叉树上每个结点至多有两棵子树， 则第 i 层的结点数 = 2i-1-1 2 = 2i-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 +
8、2n2,而 b = n-1 = n0 + n1 + n2 - 1,由此， n0 = n2 + 1,两类特殊的二叉树：,满二叉树：指的是深度为k且含有2k-1个结点的二叉树。,完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。,完全二叉树：如果一颗二叉树只有最下一层结点数可能未达到最大，并且最下层结点都集中在该层的最左端，则称为完全二叉树；,(a),(c),(b),、(b)完全二叉树 (c) 不是完全二叉树,性质 4 ： 具有 n 个结点的完全二叉树的深度为 log2n +1,证明：,设 完全二叉树的深度为 k,由性质2得2k-1-1 n 2k-1，即 2k-1n
9、 2k,即 k-1 log2 n n，则结点 i 无左孩子， 否则，结点 i 的左孩子编号为 2i (3) 若 2i+1n，则结点 i 无右孩子结点， 否则，结点 i 的右孩子编号为2i+1。,6.2.3 二叉树的存储结构,二、二叉树的链式存储表示,一、 二叉树的顺序存储表示,#define MaxTreeSize 100 / 二叉树的最大结点数 typedef TElemType SqBiTreeMaxTreeSize +1； / 0号单元不用 SqBiTree bt;,一、 二叉树的顺序存储P130,顺序存储结构:按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。,A B
10、 C D E F G H I,问： 顺序存储后能否复原成唯一对应的二叉树形状？ 答： 若是完全/满二叉树则可以做到唯一复原。而且有规律：下标值为i的结点，其左孩子的下标值必为2i，其右孩子的下标值必为2i1（即性质5）例如，对应2的两个孩子必为4和5,即B的左孩子必是D,右孩子必为E。,T0一般不用,讨论：不是完全二叉树怎么办？,答：一律转为完全二叉树！方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。,A B C D E,缺点：浪费空间；插入、删除不便,例如:,2,5,1,14,3,7,对应的完全二叉树结点数为n=15,二、二叉树的链式存储表示,1. 二叉链表,2三叉链表,3双亲链表,
11、4线索链表,root,结点结构:,1. 二叉链表,typedef struct BiTNode / 结点结构TElemType data;struct BiTNode *lchild, *rchild; / 左、右孩子指针 BiTNode, *BiTree;,结点结构:,二叉链表类型描述如下:,root,2三叉链表,结点结构:,typedef struct TriTNode / 结点结构 TElemType data;struct TriTNode *lchild, *rchild; / 左右孩子指针struct TriTNode *parent; / 双亲指针 TriTNode, *TriT
12、ree;,结点结构:,C 语言的类型描述如下:,6.3 遍历二叉树和线索化二叉树,一、遍历的概念,二、先左后右的遍历算法,三、算法的递归描述,四、中序遍历算法的非递归描述,五、建立二叉树的二叉链表存储结构,6.3.1 二叉树的遍历,顺着某一条搜索路径巡访二叉树 中的结点，使得每个结点均被访问一 次，而且仅被访问一次。,一、遍历的概念,“访问”的含义可以很广，例如：输出或修改结点的信息等。,“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径，故不需要另加讨论。而二叉树是非线性结构，,每个结点有两个后继，则存在如何遍历即按什么样的搜索路径进行遍历的问题。,对“二叉树”而言，可以有三条搜
13、索路径：,1先上后下的按层次遍历； 2先左（子树）后右（子树）的遍历； 3先右（子树）后左（子树）的遍历。,遍历二叉树（Traversing Binary Tree）,遍历定义 指按某条搜索路线遍访每个结点且不重复（又称周游）。 遍历用途 它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。 遍历方法 牢记一种约定，对每个结点的查看都是“先左后右” 。,二、先左后右的遍历算法（约定算法）,先（根）序的遍历算法,中（根）序的遍历算法,后（根）序的遍历算法,根,左 子树,右 子树,根,根,根,根,根,若二叉树为空树，则空操作；否则， （1）访问根结点； （2）先序遍历根
14、结点的左子树； （3）先序遍历根结点的右子树。,先(根)序遍历算法（DLR）,若二叉树为空树，则空操作；否则， （1）中序遍历根结点的左子树； （2）访问根结点； （3）中序遍历根结点的右子树。,中(根)序遍历算法（LDR）,若二叉树为空树，则空操作；否则， （1）后序遍历根结点的左子树； （2）后序遍历根结点的右子树； （3）访问根结点。,后(根)序遍历算法（LRD）,例如：,先序序列：,中序序列：,后序序列：,A B C D E F G H K,B D C A E H G K F,D C B H K G F E A,三、算法的递归描述P132,void PreOrderTraverse ( BiTree T ) / 先序遍历二叉树算法6.1if (T) VisitElement(T-data); / 访问结点PreOrderTraverse (T-lchild); / 遍历左子树PreOrderTraverse (T-rchild);/ 遍历右子树 ,
