《大学数据结构课件树和二叉树》由会员分享，可在线阅读，更多相关《大学数据结构课件树和二叉树（51页珍藏版）》请在金锄头文库上搜索。
1、第第6 6章章 树和二叉树树和二叉树前面讲的线性表主要表现的是数据元素之间的前后次序关系，是一种线性结构。树型结构是以分支关系定义的层次结构。树形结构在客观世界中广泛存在，如人类的家庭族谱及各种社会组织机构。又如计算机文件管理和信息组织也用到树形结构。本章讨论树的基本概念，重点讨论二叉树的有关概念、性质、存储结构和各种运算。6.1.1 6.1.1 树的定义树的定义树(tree)是由n(n0)个结点组成的有限集合T。n=0的 树称为空树；对n0的树，有:(1)仅有一个特殊的结点称为根(root)结点，根结点没 有前驱结点；(2)当n1时，除根结点外其余的结点分为m(m0)个互 不相交的有限集合T
2、1,T2，Tm，其中每个集合Ti本身又 是一棵树，称之为根的子树（ subtree）。注：树的定义具有递归性，即“树中还有树”。仅有一个根结点的树是最小树，6.1 6.1 树基本概念和术语树基本概念和术语6.1.2 6.1.2 若干术语若干术语 （从结构上分）（从结构上分）分支结点：度不为0的结点，除叶结点之外的其余结点 。ABCGEIDHFJMLK结点（node）：由数据元素 和构造数据元素之间关系的 指针组成 结点的度：结点所拥有 的子树的个数树的度：树中所有结点的度的最大值叶结点：度为0的结点，也称作终端结点结点的层次：从根结点到树中某结点所经路径上的分支数树的深度：树中所有结点的层次的
3、最大值 森林：m（m0）棵树的集合 6.1.2.6.1.2.若干术语若干术语 （从关系上分）（从关系上分）孩子(child)结点：树中一个结点的子树的根结点双亲(parent)结点：若树中某结点有孩子结点，则这个 结点就称作它的孩子结点的双亲结点 兄弟(sibling)结点：具有相同的双亲结点的结点 ABCGEIDHFJMLK无序树：树中任意一个结点的各孩子结点之间的次序构成 无关紧要的树有序树：树中任意一个结点的各孩子结点有严格排列次序的树6.1.2 6.1.2 若干术语若干术语 （从结构上分）（从结构上分） BEFLKBFELK6.1.36.1.3 树的表示形式树的表示形式(1)倒悬树法(
4、直观表示 ) (2)集合包含关系图法 (3)凹入表示法 ABCGEIDHFJMLKFE KLCGA ABIJMDHA BCDEFGHI JK LM6.1.4 6.1.4 树的抽象数据类型树的抽象数据类型数据集合: 树的结点集合，每个结点由数据元素和构造数 据元素之间关系的指针组成。操作集合: （1）创建MakeTree(T) （2）撤消DestroyTree(T)（3）双亲结点Parent(T, curr) （4）左孩子结点LeftChild(T, curr) （5）右兄弟结点RightSibling(T, curr) （6）遍历树Traverse(T, Visit()6.1.56.1.5 树
5、的存储结构树的存储结构 树的结点之间的逻辑关系主要有双亲-孩子关系，兄弟关系。因此，从结点之间的逻辑关系分，树的存储结构主要有：双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法四种组合。指针有常规指针和仿真指针4H2G1F1E1D0C0B-1AI4data parent012345678(1)双亲表示法(a)一棵树（b)仿真指针的双亲表示法存储结构树及其使用仿真指针的双亲表示法ABCFGEIHD(2)孩子表示法常规指针的孩子表示法BCrootAD EF GIH ABCFGEIHD双亲孩子表示法(3)双亲孩子表示法4H2G1F1E1D0C0B-1AI4data parent head012
6、345678child next87123456ABCFGEIHD(4)孩子兄弟表示法常规指针的孩子兄弟表示法rootBCDEFGHIAABCFGEIHD6.26.2 二叉树二叉树二叉树(binary tree)：是n(n0)个结点的有限集合。n=0的树称为空二叉树；n0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的 二叉树组成 。其逻辑结构： 一对二（1:2）左、右子树也是二叉树，所以子树也可以为空树。下图展现了五种不同形态的二叉树。6.2.16.2.1 二叉树的定义二叉树的定义n=0n=1n1n1n1基本特征: 每个结点最多只有两棵子树（不存在度大于2的结点）； 左子树和
7、右子树次序不能颠倒。所以下面是两棵不同的树6.2.16.2.1 二叉树的定义二叉树的定义BACEDFGBACEDFG满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。BACEDFGHIJKLMNO完全二叉树：如果一棵深度为k，有n个结点的二叉树中各结点能够与深度为k的顺序编号的满二叉树从1到n标号的 结点相对应的二叉树称为完全二叉树。如下图所示BACEDFGHIJBACEDFGHIJKLMNO(a)满二叉树 (b)完全二叉树 数据集合：二叉树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。操作集合：（1）创建
8、MakeTree(T) （2）撤消DestroyTree(T)（3）左插入结点InsertLeftNode(curr, x) （4）右插入结点InsertRightNode(curr, x) （5）左删除子树DeleteLeftTree(curr) （6）右删除子树DeleteRightTree(curr) （7）遍历二叉树Traverse(T, Visit()6.2.26.2.2 二叉树抽象数据类型二叉树抽象数据类型k=i2i -16.2.36.2.3 二叉树的重要性质二叉树的重要性质性质1:二叉树的第二叉树的第i i （i i1 1）层上至多有）层上至多有2 2i-1i-1个结点。个结点。
9、i=1 21-1=20=1i=222-1=21=2i=323-1=22=4BACEDFGHIJKLMNOi=424-1=23=8k=i6.2.36.2.3 二叉树的重要性质二叉树的重要性质性质2:深度为深度为k(k1)k(k1)的二叉树至多有的二叉树至多有2 2k k-1-1个结点。个结点。k3 2 10 00 0 1 200 00 1 0 210 01 0 0 22 + 0 10 0 0 2k-10 11 1 1 2k-1 证明一：证明一：2 20 0+2+21 1+2+22 2+2+2k-1k-1 =2=2k k-1-11+1+-1-1=21=22=23=2k-1=2k=201 00 0
10、0+ 1kBACEDFGHIJKLM NOk=i2i -1证明三：证明三： 等比数列前等比数列前n n项和的计算公式项和的计算公式 ：证明二：证明二：n=ka1=1q=2性质3 对于一棵非空的二叉树，如果叶结点个数为n0，度为2的结点数为n2，则有n0= n2+1。BACEDFGHIJn0 = n2+1。证明：设n为二叉树的结点总数，n1为二叉树 中度为1的结点个数，则有：n = n0 + n1 + n2 (1)由于二叉树中除根结点外 ，每个结点都有一条与其 父结点相连的边。所以， 有n个结点的二叉树总共 有 n-1条边。于是有：n-1=0n0 + 1n1 + 2n2 (2)再把(1)代入(2
11、)，得：n0 + n1 + n2 -1= n1 + 2n2则可以得到:性质性质4:4: 具有具有n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 loglog2 2(n(n) ) +1。 k-1 = loglog2 2(n(n) ) BACEDFGHIJ证明：根据性质2，对于有n个结点的深度为k的完全二叉树有:2 2k-1k-1-11时，其双亲是结点i/2 (“/”表示整除）；若2in，则第i个结点有编号为2i的左孩子；若2i+1n，则第i 个结点有编号为2i+1的右孩子完全二叉树的结点可按从上到下和从左至右的次序存储在一维数组中，其结点之间的关系可由公式计算得到，这就是二叉树的顺序
12、存储结构。下面两棵树在数组中的存储结构分别为：6.2.46.2.4 二叉树的存储结构二叉树的存储结构二叉树的存储结构有多种，最常用的有两种：顺序存储结构和链表存储结构1. 二叉树的顺序存储结构BACEDFGHIJKLMNO1204357611810912 13 14 15DA BCONMLKJIHGFE123456789 10n=151112131415满二叉树：结点：i=5父结点：i/2=5/2=2左孩子：2i=2*5=10右孩子：2i+1=2*5+1=11完全二叉树：BACEDFGHIJ123456789 10n=10120435768910A BCDJIHGFE对于一般的非完全二叉树BA
13、CEGDFA BCGFED1204357611810912数组下标13必须首先在非完全二叉树中增添一些并不存在的空结点使之 变成完全二叉树的形态。然后再用顺序存储结构存储在一维数组中。 显然不能直接使用二叉树的顺序存储结构。所以，顺序存储结构仅适于满二叉树或完全二叉树，一般二叉树 更适宜用链表存储结构二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉 树最常用的的链式表储结构是二叉链和三叉链。二叉链存储结构的每 个结点包含三个域，分别是数据域data、左孩子指针域leftChild和右孩 子指针域rightChild。二叉链存储结构中每个结点的图示结构为：rightChilddata
14、leftChild 三叉链表的结点比前者多了 一个指向双亲的指针域。2. 二叉树的链式存储结构结点结构描为：typedef struct node ElemType data;struct node *lch,*rch; Bnode;typedef struct node ElemType data;struct node *lch,*par,*rch; /*par是双亲指针域*/ Bnode3;parrchdatalch结点结构描为：A BCD F J K ABCDFJK BACDJFK二叉链表三叉链表二叉树二叉树的仿真指针存储结构是用数组存储二叉树中的结点， 数组中每个结点除数据元素域外，
15、再增加仿真指针域用于仿 真常规指针建立二叉树中结点之间的关系。二叉树的仿真二叉链存储结构BACDGEF二叉树的仿真指针6.2.5 二叉树二叉链表的一个生成算法创建二叉树的方法有多种，并且算法都比较复杂，这里我们运 用二叉树的性质5，学习一种较简单的生成算法。对任意二叉树，首先按满二叉树的结构对其结点进行编号。1 21 11 31 41 61 5123456789i123469 x111213141516此树并非完全二叉树，因此结点编号不连续。算法中用一个辅助向量s存放树结点的指针。该向量的类型为：Bnode *sMAXSIZEBnode *creat() Bnode *t=NULL;printf(“n i,x=”);scanf(“%d%d”,while(i!=0q-data=x;q-lch=NULL;q-rch=NULL;si=q; /* Bnode *s20 */if(i=1)t=q; /* t为树根结点 */else j=i/2; /* j为双亲结点编号 */if(i%2)=0)sj-lch=q;else sj-rch=q;printf(“n i,x=”); scanf(“%d%d”,return t
