《129633294700781250树形结构》由会员分享，可在线阅读，更多相关《129633294700781250树形结构（101页珍藏版）》请在金锄头文库上搜索。
1、数据结构（C语言描述）第七章 树形结构7.1 树n树(非线性数据结构)q一棵空树，即不含有任何结点（元素）；q一棵非空树，即至少含有一个结点。n有且仅有一个根(root)结点；n其余所有结点分属于m个(m0)互不相交的集合，每个集 合又构成一棵树，称它为根结点的子树(subtree)；n并且，树的根结点是每棵子树根结点的前驱，相反，每棵 子树的根结点是所在树的根结点的后继。q树是一种递归定义的数据结构。 7.1 树n非线性数据结构；A只有根结点的树ABCDEFGHIJKLM有子树的树根子树子树有什么特点？互不相交； 子树还可以有子树。7.1.1 树的定义n若采用第一章介绍的二元组来描述一棵树，
2、则为：Tree=(K,R)K=ki | 1in, n0, kiElemType其中n为树中结点数，n=0则为空树，n0则为非空树。对于一棵非空树，关系R应满足下列条件：q (1) 有且仅有一个结点没有前驱，该结点被称为树的根；q (2) 除树根结点外，其余每个结点有且仅有一个前驱结点；q (3) 包括树根结点在内的每个结点，可以有任意多个(含0个)后继。n对于上图的树T，若采用二元组表示，则结点的集合K和K上二元 关系R分别为：K=A,B,C,D,E,F,G,H,IR=,7.1.2 树的表示n树形表示法n二元组表示法n广义表表示法qA(B(D,E(H,I),F),C(G)7.1.3 树的基本术
3、语n1. 结点的度（degree）和树的度q结点拥有的非空子树数或后继结点数或分支数；q树中所有结点的度的最大值为树的度。nB结点的度为3，H结点的度为0；n树的度为3。树的基本术语n2. 分支结点和叶子结点q叶子(终端)结点：度为0的结点；q分支(非终端)结点：度大于0的结点。每个结点的分 支数就是该结点的度数。树的基本术语n3. 孩子结点、双亲结点和兄弟结点q孩子：结点的子树的根（即结点的后继）；叶子结 点无孩子q双亲：结点的前驱；根结点的双亲？q兄弟：同一双亲的孩子；q堂兄弟：其双亲在同一层次上的结点；q祖先：结点的祖先是从整个树的根结点到该结点的 路径上所经过的所有分支结点。nI结点的
4、祖先是：A,B,Eq子孙：以某结点为根的子树中的 任一结点都称为该结点的子孙。B 结点的子孙是D,E,F,H,I树的基本术语n4. 结点的层数和树的深度q结点的层数：从根结点算起，根为第一层，它的孩 子为第二层q树中结点的最大层数称为树的深度或高度；树的基本术语n5. 有序树和无序树q若树中各结点的子树是按照一定次序从左到右安排 的，称为有序树；q一般情况下，无特殊说明时，树是有序的。树的基本术语n6. 森林qm(m 0)棵互不相交的树的集合；q如果仅关注结点A的子树，则子树T1和T2构成森林 ；7.1.4 树的性质n性质1 树中的结点数等于所有结点的度数加1 。q除根结点外，每个结点有且仅有
5、一个分支连接到它 ，所以结点数-1等于分支数(度数)；n性质2 度为k的树中第i层上最多有ki-1个结点 （i1）。q数学归纳法（自己证明）树的性质n性质3 深度为h的k叉树最多有(kh-1)/(k-1)个结 点。q利用性质2(自己证明)q此时的树称为满k叉树。树的性质n性质4 具有n个结点的k叉树的最小深度为 logk(n(k-1)+1) q深度最小意味着什么？n每个结点尽可能有最多的分支，即度为k；n前h-1层都是满的;最后一层(h层)的结点数可能满，也可能 不满；n利用性质3q自己证明7.2 二叉树n定义递归定义q二叉树（binary tree）是n(n0)个结点的有限集，它或 者是空集
6、(n=0)，或者由一个根结点及两棵互不相交的 、分别称作这个根的左子树和右子树的二叉树组成。n特点q每个结点至多有两棵子树(即不存在度大于2的结点)；q二叉树的子树有左、右之分，且其次序不能任意颠倒；q左子树的根结点称为左孩子，右子树的根结点称为右孩 子；二叉树的五种基本形态A只有根结点 的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树 均非空二叉树的性质n性质1 二叉树上叶子结点数n0等于双分支结点 数n2加1。n证明：q设二叉树中度为1的结点数为n1，二叉树中总结点 数为n，则有：n=n0+n1+n2 q由树的性质1（树中的结点数等于所有结点的度数 加1），有：n=n1+2*n
7、2+1q所以：n0+n1+n2=n1+2*n2+1, 即n0=n2+1二叉树的性质n性质2 二叉树上第i层上至多有2i-1个结点(i1)。q数学归纳法证明(自己证明)q满二叉树：第i层的结点数为2i-1；q完全二叉树：除最后一层外，其余层都是满的，并且最 后一层或者是满，或者结点从左到右连续分布；q理想平衡二叉树：简称理想平衡树或理想二叉树，除最 后一层外，其余层都是满的，而最后一层上的结点可以 任意分布。45671 32 451 32 4571 32若双亲结点的编号为i， 则左右孩子的编号 为2i和2i+1二叉树的性质n性质3 深度为h的二叉树至多有2h-1个结点。q由树的性质可得二叉树的性
8、质n性质4 对完全二叉树中编号为i的结点(n为结点数)有：q(1) 若in/2，即2in，则编号为i的结点为分支结点，否 则为叶子结点。表达式x表示对x进行向下取整。q(2) n若n为奇数，则树中编号最大的分支结点(编号为n/2 ) 既有左孩子，又有右孩子；n若n为偶数，则编号最大的分支结点(编号为n/2)只有 左孩子，没有右孩子n其余分支结点左、右孩子都有。二叉树的性质q(3) 若编号为i的结点有左孩子，则左孩子结点的编号为 2i；若编号为i的结点有右孩子，则右孩子结点的编号为 2i+1。(此规则也适合于一般二叉树)q(4) 除树根结点外，若一个结点的编号为i，则它的双亲 结点的编号为i/2
9、。也就是说，当i为偶数时，其双亲结 点的编号为i/2，它是双亲结点的左孩子，当i为奇数时 ，其双亲结点的编号为(i-1)/2，它是双亲结点的右孩子 。(此规则也适合于一般二叉树)q(5)完全二叉树单分支结点数为0(n为奇数)或1(n为数偶 数)二叉树的性质n性质5 具有n个(n0)结点的完全二叉树的深度为 log2(n+1)或log2n+1。n证明q参照树的性质4；q假设此二叉树的深度为h，则根据性质3及完全二叉树的定义 得到：q2h-1-1BDCD L R先序遍历序列：A B D C二叉树遍历演示中序遍历ADBCL D RBL D RL D RADCL D R中序遍历序列：B D A C二叉
10、树遍历演示后序遍历ADBCL R DL R DL R DADCL R D后序遍历序列： D B C AB二叉树递归遍历算法n无论是前序、中序和后序遍历，都可以用递归 算法。void Preorder(struct BTreeNode* BT) /*前序遍历*/if(BT != NULL) printf(“%c “, BT-data); /*访问根结点*/Preorder(BT-left); /*前序遍历左子树*/Preorder(BT-right); /*前序遍历右子树*/那中序和后序遍历的递归 算法是什么样的？递归遍历算法的时间复 杂度均为O(n)。二叉树非递归遍历算法n上述递归遍历算法均可
11、以利用栈改成非递归算 法n还可以用队列来实现树的按层遍历的非递归算 法。q算法思想：树非空时根结点入队。然后循环出队， 将出队结点的左右孩子(如果存在)入队，直到队为空二叉树非递归遍历算法n按层遍历的序列：ABDCEHFGIAEDHCBGIF二叉树非递归遍历算法void Levelorder(struct BTreeNode *BT) struct BTreeNode *QueueQueueMaxSize; /用来保存按层遍历时结点指针的顺 序队列 int front=0,rear=0; struct BTreeNode *p;if(BT) rear+; Queuerear=BT; /根结点指
12、针入队while(front!=rear) /队不为空,循环出队 front+;p=Queuefront;printf(“%c”,p-data); /出队二叉树非递归遍历算法if(p-left) /左孩子存在，则入队 rear+; Queuerear=p-left; if(p-right) /右孩子存在，则入队 rear+; Queuerear=p-right; 二叉树的其他运算n1. 初始化二叉树void InitBTree(struct BtreeNode *BT) *BT = NULL; 二级指针！二叉树的其他运算n2. 建立二叉树n采用先序序列表示(递归)q在先序序列中某结点的孩子不存
13、在用特殊符号替代 ； ABC#DEF#G#q访问该序列，遇到非特殊字符，表明以该结点为根 的树不为空，建立该结点，然后递归建立该结点的 左子树和右子树；如果遇到特殊字符，表明以该结 点为根的树空，递归结束，返回上一次递归调用处 继续执行。AEDCBGF二叉树的其他运算n2. 建立二叉树struct BTreeNode *CreateBTree() char ch; struct BTreeNode *p; ch=getchar(); /*读入先序序列中的字符*/if(ch=#) return NULL;elsep=(struct BTreeNode *)malloc(sizeof(struct
14、 BTreeNode)p-data=ch;p-left=CreateBTree(); /*递归建立左子树*/p-right=CreateBTree(); /*递归建立右子树*/return p; /*返回建立的树的根结点指针*/ AED CBGFABC#DEF#G#二叉树的其他运算n采用广义表表示(非递归，自学)q每棵树的根结点作为由子树构成的表的名字放在表 前面；A(B(C),D(E(F,G),H(,I)q每个结点的左子树和右子树用逗号分开，若只有右 子树，没有左子树，则逗号不能省略；AEDHCBGIF为什么？二叉树的其他运算n2. 建立二叉树n基本思路q从保存二叉树广义表的字符串a中读取每
15、个字符；q若遇到空格，则不进行任何操作；q若遇到字母（如果结点的值是字母），则建立一个新结点，并把该 结点（非根结点）作为左孩子（k=1）或右孩子（k=2）链接到其 双亲结点上；如是根结点，直接让根指针指向它。q若遇到左括号，则表明子树开始，应首先把其前面字母所在结点的 指针进栈，以便括号内的孩子结点向双亲结点链接，然后置k为1 ，因为左括号后面紧跟的字母（如果有）必为左孩子；q若遇到逗号，则表明以左孩子为根的子树处理完毕，应处理以右孩 子为根的子树，置k=2；q若遇到右括号，则子表结束，退栈；q直到读入字符串结束符为止。A(B(C),D(E(F,G),H(,I)AED HCBGIF二叉树的其他运算n2. 建立二叉树void CreateBTree(struct BTreeNode* BT, char *a) /*根据a所指向的二叉树广义表字符串建立对应的存储结构*/ struct BTreeNode *p; /*定义s数组作为存储根结点指针的栈使用*/ struct BTreeNod
