数据结构第六章树.ppt

数据结构  第六章 树 重庆一中 葛静 树的基本概念 空树：不含结点的树。 非空树：至少含一个节点的树。只有一个根结 点，其余结点分为m棵互不相交的子树，每棵子 树又都是一棵树。（递归定义） 树的二元组定义： Tree=(K,R) K={ki｜1=i=n,n0,n为树中结点数目,ki∈elemptype} R={r} 当n0时，关系r满足下列条件： （1）有且仅有一个结点没有前驱，即根结点。 （2）其余每个结点有且仅有一个前驱结点。 （3）包括树根结点在内的每个结点，可以有任意多个后继结点。 树的二元组定义 K={A,B,C,D,E,F,G,H,I} R={A,B,A,C,B,D,B,E,B,F,C,G,F,H,F,I} 例2、表达式树 a*b+(c-d/e)*f 树的表示方法： 1、树形图 2、二元组 3、目录结构 4、集合图 5、凹入表 6、广义表 树的基本术语 结点的度：结点的儿子数（注意不包括孙子） 树的度：树中所有结点的度的最大值 分支结点（非终端结点）：度大于0的结点 叶子结点（终端结点）：度为0的结点 孩子结点：某结点的后继叫该结点的孩子。 双亲结点（父结点）：某结点的前驱叫该结点的父亲。 显然，根结点没有双亲，叶结点没有孩子。 结点的层数：根为第一层，其儿子为第二层，孙子为第三层，以此类推。 树的深度（高度）：结点的最大层数。 森林：互不相交的树的集合。对于每个分支结点，其子树的集合就是森林。 二叉树的定义 树的度不超过2的有序树，非常重要的数据结构。 二叉树的性质 二叉树的性质 完全二叉树的深度性质： N个结点的完全二叉树，其深度为trunc(log2n)+1 证明见书上102页 理想平衡树：二叉树中，除最后一层外，其余 层都是满的，则称此树为理想平衡树。 满二叉树是特殊的完全二叉树，完全二叉树是 特殊的理想平衡树。 二叉树的存储结构 1、线性存储 顺序存储二叉树，首先将二叉树按照完全二叉树中对应 的位置进行标号，然后，以每个结点的标号为下标，将对 应的值存储到一个一维数组中。 二叉树的存储结构 2、动态链接存储，三个域的节点： 由广义表生成二叉树 该二叉树的广义表表示： A(B,C) A(B(D,F),C(,G)) A(B(D,F(H,I)),C(,G)) 算法思想： 1、依次输入广义表中每个字符。 2、若遇到字母，则为其新建一个结点，若是第一个字母，则作为根节点，若是孩子节点，则将其连接到它的父节点上。 3、若遇到左括号，则先将其前面字母的指针进栈，以便后面的结点连接到父节点上。并记下将要插入节点的孩子为左孩子（k=1） 4、若遇到逗号，则表明左子树以处理完，标记将要处理的子节点为右节点（k=2）. 5、若遇到右括号，则表明子树处理完毕，则退栈。 这样处理直至结束，通常用“@”表明广义表结束。 算法伪代码： Procedure buildtree; Begin 输入一个字符ch while ch’@’ do begin case ch of ‘A’..’Z’:新建节点，值域赋为ch，左右子树指针置空；若为首结点，则是根节点，否则若k=1,则当前节点为栈顶节点的左子树，否则k=2则将当前节点当做栈顶节点的右子树。 ‘(’：当前节点插入栈顶，k=1; ‘,’ :k=2; ‘)’:栈顶元素出栈； end; 输入下一字符 end; End; 二叉树的运算 1、二叉树的遍历 2、二叉树的输出 3、求二叉树的深度 二叉树的遍历 二叉树常用的存储结构 type bitree=^node node=record data :datatype; lchild,rchild:bitree; end; 1、先序遍历：根左右 Procedure preorder(bt:bitree); Begin if btnil then begin visit(bt^); preorder(bt^.lchild); preorder(bt^.rchild); end; End; 二叉树的遍历 2、中序遍历：左根右 Procedure preorder(bt:bitree); Begin if btnil then begin preorde