《数据结构 第七章 树和二叉树》由会员分享，可在线阅读，更多相关《数据结构 第七章 树和二叉树（54页珍藏版）》请在金锄头文库上搜索。
1、第七章 树和二叉树n7.1 树的基本概念n7.2 二叉树概念和性质n7.3二叉树遍历n7.4二叉树的基本运算及其实现n7.5 线索二叉树n7.6 哈夫曼树7.1 树的基本概念n树的定义n树的表示n相关术语n树的存储树的定义树是由n(n0)个结点组成的有限集合(记为T)。 其中：如果n=0,它是一棵空树,这是树的特例；如果n0,这n个结点中存在(有仅存在)一个结 点 作为树的根结点,简称为根(root),其余结点可分为 m (m0)个互不相交的有限集T1,T2,Tm,其中每 一 棵子集本身又是一棵符合本定义的树,称为根root 的 子树。树的表示树型表示法相关术语n结点的度与树的度树中某个结点的
2、子树的个数称为该结点的度 。树中各结点的度的最大值称为树的度,通常将 度为m的树称为m叉树。相关术语n分支结点与叶结点度不为零的结点称为非终端结点,又叫分支结点度为零的结点称为终端结点或叶结点在分支结点中,每个结点的分支数就是该结点的度n如对于度为1的结点,其分支数为1,被称为单分支结点；n对于度为2的结点,其分支数为2,被称为双分支结点相关术语n孩子结点、双亲结点和兄弟结点在一棵树中,每个结点的后继,被称作该结点的孩子结点(或 子女结点) 该结点被称作孩子结点的双亲结点(或父母结点)。具有同一双亲的孩子结点互为兄弟结点把每个结点的所有子树中的结点称为该结点的子孙结点从树根结点到达该结点的路径
3、上经过的所有结点被称作该 结点的祖先结点。相关术语n结点的层次和树的高度结点的层次从树根开始定义,根结点为第1层,它的 孩子结点为第2层,以此类推,一个结点所在的层次 为其双亲结点所在的层次加1树中结点的最大层次称为树的高度(或树的深度)。相关术语n有序树和无序树若树中各结点的子树是按照一定的次序从左向右 安排的,且相对次序是不能随意变换的,则称为有序 树,否则称为无序树n森林n(n0)个互不相交的树的集合称为森林相关术语n路径与路径长度对于任意两个结点ki和kj,若树中存在一个结点序 列ki,ki1,ki2,kin,kj,使得序列中除ki外的任一结点 都是其在序列中的前一个结点的后继,则称该
4、结点 序列为由ki到kj的一条路径,用路径所通过的结点 序列(ki,ki1,ki2,kj)表示这条路径。路径的长度等于路径所通过的结点数目减1(即路 径上分支数目)。7.2 二叉树概念和性质n二叉树的概念n二叉树的性质n二叉树的存储二叉树的概念n定义二叉树是有限的结点集合,这个集合或者是空, 或者由一个根结点和两棵互不相交的称为左 子树和右子树的二叉树组成。二叉树的概念n5种形态二叉树的概念n满二叉树在一棵二叉树中,如果所有分支结点都有左孩子结点 和右孩子结点,并且叶结点都集中在二叉树的最下一 层,这样的二叉树称为满二叉树。n完全二叉树若二叉树中最多只有最下面两层的结点的度数可以小 于2,并且
5、最下面一层的叶结点 都依次排列在该层最 左边的位置上,则这样的二叉树称为完全二叉树二叉树的性质n性质1非空二叉树上第i层上至多有2i-1个结点,这里应 有i1。n性质2高度为h的二叉树至多有2h-1个结点(h1)。n性质3非空二叉树上结点数满足：n0=n2+1二叉树的性质n性质4具有n个(n0)结点的完全二叉树的高度为 log2n+1或log2n+1。n性质5对完全二叉树中编号为i的结点(1in,n1,n为 结点数)n若i=1，则i为根结点，无双亲；否则结点i的双亲为 i/2n若2idata); /*访问根结点*/PreOrder(b-lchild);PreOrder(b-rchild);先序
6、遍历递归算法应用例：假设二叉树采用二叉链存储结构存储,试设计 一个算法,输出一棵给定二叉树的所有叶子结点 。 解：输出一棵二叉树的所有叶子结点的递归模型 f()如下：f(b)：不做任何事件 若b=NULLf(b)：输出*b结点的data域 若*b为叶子结 点f(b)：f(b-lchild);f(b-rchild) 其他情况先序遍历递归算法应用void DispLeaf(BTNode *b)if (b!=NULL) if (b-lchild=NULL else DispLeaf(b-lchild);DispLeaf(b-rchild);中序遍历n递归算法思想中序遍历左子树；访问根结点；中序遍历右
7、子树。中序遍历递归算法void InOrder(BTNode *b) /*中序遍历的递归算法 */if (b!=NULL) InOrder(b-lchild);printf(“%c “,b-data); /*访问根结点*/InOrder(b-rchild); 后序遍历n递归算法思想后序遍历左子树；后序遍历右子树；访问根结点。后序遍历递归算法void PostOrder(BTNode *b) /*后序遍历递归算法*/if (b!=NULL) PostOrder(b-lchild);PostOrder(b-rchild);printf(“%c “,b-data); /*访问根结点*/ 先序遍历非递
8、归算法void PreOrder2(BTNode *b) BTNode *StMaxSize,*p; int top=-1; top+; Sttop=b; /根结点入栈 while (top-1) /栈不为空时循环 p=Sttop; top-; /退栈并访问该结 点printf(“%c “,p-data);if (p-rchild!=NULL) /右孩子结点入 栈 top+; Sttop=p-rchild; if (p-lchild!=NULL)/左孩子结点入 栈 top+; Sttop=p-lchild; 中序遍历非递归算法void InOrder2(BTNode *b)BTNode *St
9、MaxSize,*p; int top=-1; p=b; while (top-1 | p!=NULL) while (p!=NULL) /扫描*p的所有左结点并进栈 top+; Sttop=p;p=p-lchild;if (top-1) p=Sttop;top-; /出栈*p结点printf(“%c “,p-data); /访问之p=p-rchild; /扫描*p的右孩子结点 后序遍历非递归算法void PostOrder(BTNode *b) /*后序遍历递归算法*/if (b!=NULL) PostOrder(b-lchild);PostOrder(b-rchild);printf(“%
10、c “,b-data); /*访问根结点*/ 树转换为二叉树n在所有相邻兄弟结点(森林中每棵树的根 结点可看成是兄弟结点)之间加一水平连 线。n对每个非叶结点k,除了其最左边的孩子结 点外,删去k与其他孩子结点的连线。n所有水平线段以左边结点为轴心顺时针旋 转45度。二叉树转换为树n对于一棵二叉树中任一结点k0,沿着k0的左孩子 结点k1的右子树方向搜索所有右孩子结点,即搜 索结点序列k2,k3,km,其中ki+1为ki的右孩子 结点(1im),km没有右孩子结点。n删去k1,k2,km之间连线。n若k1有双亲结点k,则连接k与ki(2im)。n将图形规整化,使各结点按层次排列。将一棵二叉树还
11、原为树的过程7.4二叉树的基本运算及其实现n创建二叉树n查找结点n求二叉树的高度n输出二叉树n求二叉树的结点层次创建二叉树查找结点BTNode *FindNode(BTNode *b,ElemType x) BTNode *p;if (b=NULL) return NULL;else if (b-data=x) return b;else p=FindNode(b-lchild,x);if (p!=NULL) return p;else return FindNode(b-rchild,x);求二叉树的高度输出二叉树求二叉树的结点层次7.5 线索二叉树n线索二叉树概念对于具有n个结点的二叉树,
12、采用二叉链存储结 构时,每个结点有两个指针域,总共有2n个指针 域,又由于只有n-1个结点被有效指针所指向(n 个结点中只有树根结点没有被有效指针域所 指向),则共有2n-(n-1)=n+1个空链域,利用这些空链域存放指向结点的前驱和后继 结点的指针。这样的指向该线性序列中的“前 驱”和“后继”的指针,称作线索。线索二叉树存储结构n在结点的存储结构上增加两个标志位来区 分这两种情况：左标志ltag : 0 表示lchild指向左孩子结点1 表示lchild指向前驱结点右标志rtag : 0 表示rchild指向右孩子结点1 表示rchild指向后继结点ltag child datarchild
13、 rtag7.6 哈夫曼树n哈夫曼树定义n构造哈夫曼树n哈夫曼编码哈夫曼树定义n设二叉树具有n个带权值的叶子结点,那么 从根结点到各个叶子结点的路径长度与相 应结点权值的乘积的和,叫做二叉树的带权 路径长度。n具有最小带权路径长度的二叉树称为哈夫 曼树。 构造哈夫曼树n 由给定的n个权值W1,W2,.,Wn构造n棵只有一个叶子 结点的二叉树,从而得到一个二叉树的集合 F=T1,T2,.,Tn;n(2)在F中选取根结点的权值最小和次小的两棵二叉树作 为左、右子树构造一棵新的二叉树,这棵新的二叉树根结 点的权值为其左、右子树根结点权值之和;n (3)在集合F中删除作为左、右子树的两棵二叉树,并 将
14、新建立的二叉树加入到集合F中;n (4)重复(2)、(3)两步,当F中只剩下一棵二叉树时,这 棵二叉树便是所要建立的哈夫曼树。给定权值w=(1,3,5,7)来构造一棵哈夫曼树 。构造一棵哈夫曼树的过程哈夫曼编码具体构造方法如下：设需要编码的字符集合为d1,d2,dn,各个字符在电文中出现的次数集合为w1,w2,wn,以d1,d2,dn作为叶结点,以w1,w2,wn作为各根结点到每个叶结点的权值构造一棵二叉树,规定哈夫曼树中的左分支为0,右分支为1,则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的编码称为哈夫曼编码。 对应的哈夫曼编码如下：1：000 3：001 5：01 7：1
