第十章树和二叉树.pptVIP

曾祖父;树型结构是一类重要的非线性结构。;树的定义和基本术语;只有根结点的树;基本术语 结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支 结点的度(degree)——结点拥有的子树数 叶子(leaf)——度为0的结点 孩子(child)——结点子树的根称为该结点的孩子 双亲(parents)——孩子结点的上层结点叫该结点的~ 兄弟(sibling)——同一双亲的孩子 树的度——一棵树中最大的结点度数 深度(depth)——树中结点的最大层次数;A;树的其它表示方法;b. 层次表示法;二叉树;根据定义，二叉树通常具有 5 种基本形态:;二叉树与树的区别 树：1、树最少有一个根结点（n0） 2、树的度≥ 0 3、树不要求子树顺序 二叉树： 1、二叉树可以为空(n ≥0) 2、二叉树的度≤2 3、二叉树是有序树，有左、右子树之分。 例10-1：试写出具有3个结点的所有不同形态的树和二叉树。 ;二叉树的性质;性质2 : 深度为 k 的二叉树至多有 2k –1 个结点(k≥1) 。;引论: 一棵树有 n 个结点，则必有 n – 1 条分支。;性质3 : 对任何一棵二叉树 T ，如果其终端结点数为 n0，度为 2 的结点数为 n2 ，则 n0 = n2 + 1 。;两种特殊形态二叉树: 满二叉树、完全二叉树。;对满二叉树的结点进行连续编号，从根结点起，自上而下，自左至右，1、2、3、…… 、2k-1 。; 1;满二叉树和完全二叉树的区别： 1、满二叉树一定是完全二叉树，它是完全二叉树的特例。 2、完全二叉树不一定是满二叉树。 3、满二叉树中n1=0，完全二叉树中n1=0或1.;性质4:具有 n 个结点的完全二叉树的深度为 log2n」+ 1。 ;性质5: 如果对一棵有n个结点的完全二叉树的结点按层序编号(从第 1 层到第 log2n」+ 1 层，每层从左到右)，则对任一结点 i(1≤i≤n)，有 ;证明 (2) 和 (3) :;设对结点 i 成立，即结点 i 的左儿子为结点 2i，右儿子为结点 2i+1；;i+1;二叉树的存储结构 (顺序、链式); 1;例10-3 一个深度为K且只有K个结点的二叉树顺序存储最多需要多少个存储空间？最少需要多少个？ 例10-4 一个完全二叉树结点个数为1000，则n0、n1、n2和高度h各为多少？;2. 链式存储结构;二叉链表存储表示;A;有时还可以在结点结构中增加一个指向父亲的指针。;基本操作 P:;PreOrderTraverse ( T ，visit() );二叉树的基本操作;若限定先左后右的原则，则只有 3 种情况: 先(根)序遍历、中(根)序遍历、后(根)序遍历。;先(根)序遍历: ;A;printf(T-data) ; ;算法的C语言实现： void PreOrderTraverse ( BiTree T) { { if(T!=NULL) { printf(%d\t,T-data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); } } ;A;中(根)序遍历: ;A;printf(T-data) ; ;A;后(根)序遍历: ;A;printf(T-data) ; ;A;例，表达式 a + b * c – d / e;中缀表示: 适于人的思维;A; {InitStack (S) ; p=T ;;用C语言实现中序遍历的非递归算法 void InOrderTraverse ( BiTree T ) { int i=0; BiTree p,s[M]; p=T; while(p!=NULL||i0) { if(p) //如果当前结点非空 { s[i++]=p; //则当前结点入栈 p=p-lchild; //然后将p的左子树作为新的当前结点(遍历左子树) } else { p=s[--i]; //否则弹出当前栈顶元素 printf(“%d\t”,p-data); //输出元素的值 p=p-rchild; //然后将p的右子树作为新的当前结点(遍历右子树) } };A;对二叉树除可以进行先序、中序、后序的遍历外，还可以进行层次遍历。;队列实现层次遍历;EnQueue(Q , T) ; ; H;二叉树插入操作;//找