第八章 树与二叉树.ppt

分支(branch)：结点之间的二元关系（序偶）。 结点(node)：一个数据元素及指向其子树的分支。 结点的度(degree)：结点拥有的子树个数。 叶结点(leaf)：度为零的结点。 分支结点(branch node):有后继的结点称为分支结点。 儿子(sons)：结点x的子树的根。 父亲(parent):结点x的前驱结点称为x的父亲。 兄弟(brother)：同一父亲的结点的子女结点。 祖先(ancestor)：根到该结点路径上的所有结点。 子孙(descendant)：某结点为根的子树上的任意结点。 堂兄弟(cousin):父亲是兄弟关系或堂兄弟关系的结点。 结点层次(level)：从根开始，根为第一层，根的子女为第二层，以此类推。 树的深度（高度）(depth)：树中结点的最大层次数 树的度：一棵树中最大的结点度数。 结点按层编号（层中编号）：将树中结点按从上层到下层，同层从左到右的次序排成一个线性序列，依次给他们编以连续的自然数。 祖辈（上层）：层号比结点x小的结点，称为x的祖辈。 后辈（下层）：层号比结点x大的结点，称为x的后辈。 有序树：若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。 无序树：若一棵树中所有子树的次序无关紧要，则称为无序树。 森林(forest)：m(m ? 0)棵互不相交的树。 三、树的基本术语 二叉树的基本操作 （1）creat_tree(bt,str) 根据二叉树的括号表示法str建立一棵二叉树bt。 （2）disptree(bt) 以凹入法显示一棵二叉树bt。 （3）depth_bttree(bt) 求一棵二叉树bt的深度。 （4）count_bttree(bt) 求一棵二叉树bt的结点个数。 （5）leafcount_bttree(bt) 求一棵二叉树bt的叶子结点个数。 （6）nleafcount_bttree(bt) 求一棵二叉树bt 的非叶子结点个数。 性质2 深度为 k 的二叉树至多有 2k -1个结点(k ? 1)。 证明：由性质1可见，深度为k的二叉树的最大结点数为 8.3 二叉树的存储结构 8.4 二叉树遍历 树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。 设访问根结点记作 V 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有 前序 VLR 中序 LVR 后序 LRV 中序遍历 (Inorder Traversal) 中序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则 中序遍历左子树 (L)； 访问根结点 (V)； 中序遍历右子树 (R)。 遍历结果 a + b * c - d - e / f 前序遍历 (Preorder Traversal) 前序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则 访问根结点 (V)； 前序遍历左子树 (L)； 前序遍历右子树 (R)。 遍历结果 - + a * b - c d / e f 后序遍历 (Postorder Traversal) 后序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则 后序遍历左子树 (L)； 后序遍历右子树 (R)； 访问根结点 (V)。 遍历结果 a b c d - * + e f / - 非递归实现先序遍历二叉树 利用一个一维数组作为栈，来存储二叉链表中结点，算法思想为： 1、从二叉树根结点开始，先将根结点入栈。 2、然后将栈顶结点出栈，输出结点的值，同时判断该结点有没有右子树，有则将右子树的根结点入栈；再判断有没有左子树，有则将左子树的根结点入栈。如果栈不空则重复第2步，直到栈为空。 void preorder (bitree root) {bitree p, stack[100]; int top=-1; //top为栈顶指针 if(root!=NULL) {top++; stack[top]=root;//将根结点压入栈内 while(top!=-1) {p=stack[top]; top--; printf(“%d ”,p-data); if(p-rchild!=NULL) { stack[++top]=p-rchlid;}