《数据结构-树和二叉树》由会员分享，可在线阅读，更多相关《数据结构-树和二叉树（84页珍藏版）》请在金锄头文库上搜索。
1、6 树和二叉树,本章重点讨论二叉树的存储结构及其各种操作，研究树和森林与二叉树之间的转换关系，最后给出一些应用实例。,6.1 树的定义和基本术语,一、树的定义树（Tree)是n(n=0)个结点的有限集。在任意一棵非空树中：（1）有且仅有一个根(Root)结点；（2）除根结点外，其余结点可分为m(m=0)个互不相交的有限集 T1, T2, , Tm, 其中每一个集合本身又是一棵树，称为根的子树(SubTree)。,二、基本术语,结点：包含一个数据元素及若干指向其子树的分支 结点的度：孩子个数 树的度（3） 叶子（d, i, j, f, g, h） 分枝结点（a, b, c, e） 结点的层数、树
2、的层数 父结点、孩子结点 兄弟、堂兄弟 祖先、子孙 树的高度或深度 路径和路径长度,森林是m（m=0）棵互不相交的树的集合。,一、二叉树的定义或空，或由根和左子树、右子树构成。二、基本形态,6.2 二叉树 6.2.1 基本概念,二叉树示例:,a,b,c,d,f,g,e,a,c,d,g,性质1：在二叉树的第i (i0)层上至多有2i-1个结点。性质2：深度为k的二叉树中至多有2k-1个结点(k0)。性质3：对任何一棵二叉树T，如果其终端结点数为n0, 度为2的结点数为n2，则 n0=n2+1。,6.2.2 二叉树的性质,性质3：n0=n2+1。 证明：设n为二叉树中的结点总数， n1为二叉树中度
3、为1的结点个数。 则有：n=n0+n1+n2 (1)考察二叉树的分支情况:B=n-1=2n2+n1 (2)由(2)得：n= 2n2+n1+1 (3)由（1）和（3）得：n0=n2+1,a,b,c,d,g,e,f,满二叉树：在二叉树的第i 层上有2i-1个结点, 深度为k的二叉树有2k-1个结点的二叉树。则此二叉树称为“满二叉树”。完全二叉树：如果一棵二叉树至多只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则此二叉树称为“完全二叉树”。,性质4：有n个结点的完全二叉树的深度为 +1。证明：假设深度为k，则根据性质2和完全二叉树的定义有：2k-1-1n =
4、 2k-1 或 2k-1 = n 2k于是 k-1=log2n k因k是整数，所以 k= +1,性质5：如果对一棵有n个结点的完全二叉树按层序从1开始编号，则对任一结点(i1, 则其双亲结点是i/2。 (2)如果2i=n, 则结点i的左孩子是结点2i ；否则结点i无左孩子。 (3)如果2i+1data); /访问根结点 preOrder(T-lchild); /先序遍历左子树preOrder(T-rchild); /先序遍历右子树 ,1,2,3,4,5,6,7,a,b,c,d,f,g,e,遇到一个结点， 访问它，再把它推入 栈中，去遍历它的左 子树，遍历它的左子 树后，从栈顶弹出这 个结点并找
5、到它的右 子树，再去遍历它的 右子树。,先序遍历二叉树非递归算法的思想,void preOrder(BTree T) /先序遍历以T为根的二叉树initstack(s);/设置一个空栈while (T !=NULL |!empty(s) )if (T !=NULL) /若T不空，则访问结点 Visite(T-data);/访问根结点push(s,T);/入栈lchild;/沿左子树遍历else pop(s,T); /栈顶元素出栈T=T-rchild； /沿右子树遍历 ,2、中序遍历 void inOrder(BTree T)/中序遍历以T为根的二叉树if (T) inOrder(T-lchil
6、d); /中序遍历左子树Visite(T-data);/访问根结点 inOrder(T-rchild);/中序遍历右子树 ,void inOrder(BTree T) /中序遍历以T为根的二叉树initstack(s);/设置一个空栈while (T|!empty(s) )if (T) /若T不空，则访问结点 push(s,T);lchild;/入栈，沿左子树遍历 else pop(s,T); /栈顶结点T出栈visite(T-data);/访问根结点T=T-rchild;/遍历右子树 ,3、 后序遍历 void postOrder(BTree T)/后序遍历以T为根的二叉树if (T) po
7、stOrder(T-lchild); /后序遍历左子树postOrder(T-rchild);/后序遍历右子树 Visite(T-data);/访问根结点 思考：后序遍历非递归算法的设计。,1、先序遍历void preorder( int p ) /前序遍历以p为根的二叉树if (p0) cout0) inorder(treep.llink); /中序遍历左子树cout0) postorder(treep.llink); /后序遍历左子树postorder(treep.rlink); /后序遍历右子树 cout0) qr+=treep.rlink; / 右子树入队 ,四、层次遍历,例6.4 二
8、叉树的建立（1）利用层次遍历方法建立静态二叉链表提示：借助“队列”实现 （2）利用“扩展后序序列”建立静态二叉链表提示：借助“队列”实现 （3）利用“扩展先序序列”建立动态二叉链表提示：利用“先序遍历”算法 （4）利用层次遍历方法建立动态二叉链表提示：借助“队列”实现,例6.5 以二叉链为存储结构，编写算法实现： （1）求二叉树中的结点数目。 （2）求二叉树中的叶子数目。 （3）求二叉树中的高度（深度）。 （4）将二叉树中所有结点的左孩子和右孩子互换。,（1）求二叉树中的结点数目。,算法1： void nodes(struct btnode *bt)/* 求二叉树中的结点数目。n:全程变量，初值为0 */if (bt !=NULL) n+; /* 计数 */nodes(bt-lchild); /* 求左子树的结点数 */nodes(bt-rchild); /* 求右子树的结点数 */ ,（1）求二叉树中的结点数目。,算法2： int nodes(struct btnode *bt)/* 求二叉树中的结点数目 */if (bt =NULL) return 0; /* 空的二叉树中结点个数为0 */else return nodes(bt-lchild)+nodes(bt-rchild)+1; /* 左子树上的结点数+右子树上的结点数+1（根）*/ ,
