数据结构-树(2)-严蔚敏版.ppt

第六章 树树是一类重要的非线性数据结构，是以分支 关系定义的层次结构 § 6.1 树的定义 «定义 v定义：树(tree)是n(n>0)个结点的有限集T，其中： l有且仅有一个特定的结点，称为树的根(root) § 当n>1时，其余结点可分为m(m>0)个互不 相交的有限集T1,T2,……Tm，其中每一个集 合本身又是一棵树，称为根的子树 (subtree) v特点： l树中至少有一个结点——根 l树中各子树是互不相交的集合A只有根结点的树ABCDEFGHIJKLM有子树的树根子树从逻辑结构看： 1）树中只有根结点没有前趋； 2）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继； 4）除根外的其他结点，都存在唯一一条从 根到该结点的路径；5）树是一种分支结构§ADT Tree { §数据对象D：D是具有相同特性的数据元素的集合 § 数据关系R： § 若D为空集，则称为空树； § 否则为非空树: §在D中存在唯一的称为根的数据元素root, § (2) 当n>1时，其余结点可分为m(m>0)个互不相交的有限集 T1, T2, …, Tm, 其中每 一个子集本身又是一棵符合本定义的树，称为根root的子树。

§ 基本操作： v InitTree( v DestroyTree( v CreateTree( v ClearTree( v TreeEmpty(T); v TreeDepth(T); v Root(T); v Value(T, v Assign(T, cur_e, value); v Parent(T, cur_e); v LeftChild(T, cur_e); v RightSibling(T, cur_e); v InsertChild( v DeleteChild( v TraverseTree(T, Visit( )); §}树的表示形式还有：嵌套集合的形式、广义表的形式、凹入 表示法AB EK L FC G D HM I J(c) 凹入表示法(a) 嵌套集合的形式(A(B(E(K,L),F),C(G),D(H(M),I,J))) (b) 广义表的形式ACGBE KLFDHIJM«二、基本术语 v结点(node)——表示树中的元素，包括数据项及若 干指向其子树的分支 v结点的度(degree)——结点拥有的子树数 v叶子(leaf)——度为0的结点 v孩子(child)——结点子树的根称为该结点的孩子 v双亲(parents)——孩子结点的上层结点叫该结点的~ v兄弟(sibling)——同一双亲的孩子 v树的度——一棵树中最大的结点度数 v结点的层次(level)——从根结点算起，根为第一层 ，它的孩子为第二层…… v深度(depth)——树中结点的最大层次数 v森林(forest)——m(m0)棵互不相交的树的集合ABCDEFGHIJKLM结点A的度：3 结点B的度：2 结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D 结点B的孩子：E，F结点I的双亲：D 结点L的双亲：E结点B，C，D为兄弟 结点K，L为兄弟树的度：3结点A的层次：1 结点M的层次：4树的深度：4结点F，G为堂兄弟 结点A是结点F，G的祖先树和线性结构的比较：线性结构 树结构 第一个数据元素(无前驱) 根结点(无前驱) 最后一个数据元素(无后继) 多个叶子结点(无后继) 其它数据元素(一个前驱、一个后继) 树中其它结点(一个前驱、多个后 继)§ 6.2 二叉树 «定义 v定义：二叉树是n(n0)个结点的有限集，它或为空树 (n=0)，或由一个根结点和两棵分别称为左子树和右子 树的互不相交的二叉树构成 v特点 l每个结点至多有二棵子树(即不存在度大于2的结点) l二叉树的子树有左、右之分，且其次序不能任意颠倒 l二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念 v基本形态A只有根结点 的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树 均非空二叉树的基本操作：InitBiTree( §DestroyBiTree( §CreateBiTree( §ClearBiTree( §BiTreeEmpty(T); §BiTreeDepth(T); §Root(T); §Value(T,e); §Assign(T, §Parent(T,e); §LeftChild(T,e); §RightChild(T,e); §LeftSibling(T,e); §RightSibling(T,e); §InsertChild(T,p,LR,c); §DeleteChild(T,p,LR); §PreOrderTraverse(T,visit()); §InOrderTraverse(T,visit()); §PostOrderTraverse(T,visit()); §LevelOrderTraverse(T,Visit());«二叉树性质 v性质1：证明：用归纳法证明之i=1时，只有一个根结点， 是对的 假设对所有j(1j1，则其 双亲是i/2(2) 如果2i>n，则结点i无左孩子；如果2in，则其左孩子是2i(3) 如果2i+1>n，则结点i无右孩子；如果2i+1n，则其右孩子 是2i+1«三、二叉树的存储结构 v1.顺序存储结构l实现：按满二叉树的结点层次编号，依次存放二叉树中的 数据元素 l特点： u结点间关系蕴含在其存储位置中 u浪费空间，适于存满二叉树和完全二叉树abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11v2.链式存储结构l二叉链表typedef struct BiTnode { Telemtype data;struct BiTnode *lchild, *rchild; } BiTnode, *BiTree;lchild data rchild ABCDEFG在n个结点的二叉链表中，有n+1个空指针域ABC DE FG^^^^^^^^基于该存储结构的二叉树基本操作有：status CreateBiTree(BiTree §//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树， §//构造二叉链表表示的二叉树T。

status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)); §//采用二叉链表存储结构,Visit是对结点操作的应用函数 §//先序遍历二叉树T,对每个结点调用函数Visit一次且仅一次 §//一旦visit()失败,则操作失败 status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)); §//采用二叉链表存储结构,Visit是对结点操作的应用函数 §//中序遍历二叉树T,对每个结点调用函数Visit一次且仅一次 §//一旦visit()失败,则操作失败 status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e)); §//采用二叉链表存储结构,Visit是对结点操作的应用函数 §//后序遍历二叉树T,对每个结点调用函数Visit一次且仅一次 §//一旦visit()失败,则操作失败 status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e)); §//采用二叉链表存储结构,Visit是对结点操作的应用函数， §//层序遍历二叉树T,对每个结点调用函数Visit一次且仅一次， §//一旦visit()失败,则操作失败l三叉链表typedef struct Thrnode { TElemtype data;struct Thrnode *lchild, *rchild, *parent; }Thrnode, *ThrTree;lchild data parent rchildABCDEFGAB C DE FG^^^^^^^^^例1：在一棵度为3的树种，度为3的结点数为2，度为2的结点数为1个， 度为1的结点数为2个，则度为0的结点数为（ ）。

解：树中的分支数为3*2+2*1+1*2=10，因为根结点的入度为0，所以树 中的结点数为10+1=11，n0=11-2-1-2=6 例2:一棵完全二叉树第6层有7个结点，则共有（ ）个结点，其中度为 1的结点有（ ）个，度为0的结点有（ ）个，编号最大的非叶子 结点是（ ），编号最小的叶子结点是（ ） 解：一棵完全二叉树除去最底层结点，则是一棵满二叉树，而一棵5层的 满二叉树有25-1=31个结点，因此共有31+7=38个结点，最低层的结 点数是奇数，因此度为1的结点有1个，度为0的结点数为38/2=19，度 为2的结点数19-1=18，编号最大的非叶子结点是38/2=19，编号最小的叶子结点是38/2+1=20 例3：深度为k的完全二叉树至少有 个结点，至多有 个结点 解：前k-1层共有2k-1-1个结点，所以深度为k的完全二叉树至少2k-1- 1+1=2k-1个结点，至多有2k-1个结点 例4：深度为7的完全二叉树，第7层上有5个结点，该树共有 个结点 解：前6层共有26-1=63个结点，所以共有63+5=68个结点 6.3 遍历二叉树«定义：按某种搜索路径访问二叉树的每个结点 ，而且每个结点仅被访问一次。

遍历二叉树的 过程，实际上是按某种规律把二叉树的结点排 成序列（对非线性结构线性化） v“访问”的含义可以很广，如：修改结点数据、输出 结点数据等«二叉树的遍历 v方法 l先序遍历：先访问根结点,然后分别先序遍历左子树、右子 树 l中序遍历：先中序遍历左子树，然后访问根结点，最后中 序遍历右子树 l后序遍历：先后序遍历左、右子树，然后访问根结点 l按层次遍历：从上到下、从左到右访问各结点DLRLDR、LRD、DLR RDL、RLD、DRLADBCD L RA D L RD L R>B>>D>>CD L R先序遍历序列：A B D C先序遍历:ADBCL D RBL D RL D R>A>>D>>CL D R中序遍历序列：B D A C中序遍历:ADBCL R DL R DL R D>A>>D>>CL R D后序遍历序列： D B C A后序遍历:B-+/a*b-efcd先序遍历：中序遍历：后序遍历：层次遍历：- + a * b - c d / e f-+a*b-cd/ef- +a *b - c d/e f-+a*b-c d/e fv算法 l递归算法 l1、先序遍历递归算法 void (PreOrder Traverse (BiTree T, Status (*Visit)(TElemType e)){ //采用二叉链表存贮二叉树， visit( )是访问结点的函数。

本算法 先序遍历以为根结点指针。