《数据结构——C++实现 教学课件 ppt 作者 缪淮扣 顾训穰 沈俊 数据结构-第六章》由会员分享，可在线阅读，更多相关《数据结构——C++实现 教学课件 ppt 作者 缪淮扣 顾训穰 沈俊 数据结构-第六章（168页珍藏版）》请在金锄头文库上搜索。
1、数据结构 C+实现 第六章 树和森林 缪淮扣 顾训穰 沈 俊 编著 科 学 出 版 社,新世纪计算机专业系列教材,主要内容 树的概念 二叉树 二叉树的存储结构 遍历二叉树 线索二叉树 二叉树的应用,树的概念,某家族的血统关系如下： 张宇有四个孩子分别是：张山、张川、张星和张月； 张山有二个孩子张冰和张雪； 张星有三个孩子张雨、张云和张风； 张云有两个孩子张亮和张丽。,树的定义： 树（tree）T是一个包含n(n=0)个数据元素的有限集合。并且有： （1）当n=0时，T称为空树； （2）如果n0，则树有且仅有一个特定的被称为根（root）的结点，树的根结点只有后继，没有前驱； （3）当n1时,除
2、根结点以外的其余结点可分为m(m0)个互不相交的非空有限集T1、T2、.、Tm,其中每一个集合本身又是一棵非空树,并且称它们为根结点的子树（subtree）。,如右图（a）表示了一棵空树，它没有数据元素； 如右图（b）表示了只有一个数据元素的树，树中只有一个没有子树的根结点A； 如右图（c）是有14个数据元素结点的树，其中A是树根，其余结点分成三个互不相交的有限集：T1=B,E,F,K,L、T2=C,G、T3=D,H,I,J,M,N，T1、T2、T3又都是树，且它们是结点A的子树。,树的术语： 1结点（node）：在树中每一个数据元素及指向其子树根的分支称为一个结点。 2结点的度（degree
3、 of node）：一个结点的子树数目称之为该结点的度。例如在图（c）所示的树中, 结点A的度为3，结点C的度数为1, 结点E的度数为0。,3终端结点(terminal node)：在树中，度为0的结点称为终端结点或叶子(leaf)。如在图（c）所示的树中，结点E，K，L，G，H，M，N，J都是树的叶子。 4非终端结点(nonterminal node)：在树中，度不为0的结点称为非终端结点或分支结点。除根结点之外的分支结点也称内部结点。如在图（c）所示的树中，结点A、B、C、D、F、I都是树的分支结点，且结点B、C、D、F、I是树T的内部结点。,5树的度（degree of tree）：树的
4、结点中，最大的度称为该树的度。如图（c）所示的树，其度为3。 6孩子(child)和双亲(parent)：在树中，结点p的子树的根称为结点p的孩子；反之,这个结点p称为其孩子的双亲（父亲）。如在图（c）所示的树中，结点D为结点A的子树的根，因此结点D是结点A的孩子，结点A是结点D的双亲结点（父结点）。 7兄弟(sibling)：在树中，同一个双亲的孩子之间互称为兄弟。例如，在图（c）所示的树中，结点B、C、D互为兄弟。,8祖先(ancestor)：在树中，从根结点到结点x所经的分支上的所有结点称为结点x的祖先。如在图（c）所示的树中，结点M的祖先为：A、D、I。 9子孙（descendant）
5、：在树中，以某结点p为根的子树中的所有结点都称为结点p的子孙。例如在图（c）所示的树中，D的子孙有H、I、J、M、N。,10结点的层次（level）：在树中，从根结点开始，根为第一层，根的孩子为第二层，依次类推，树中任一结点的层次是其双亲结点层次数加1。例如在图（c）所示的树中，结点K、L、M、N的层次数为4。 11树的深度（depth）：树中结点的最大层次称为树的深度或树的高度（height）。例如图（c）所示的树的深度为4。 12堂兄弟：双亲在同一层的结点互称为堂兄弟。如在图（c）所示的树中，结点F、G、H互称为堂兄弟。,13有序树：如果树中结点p的各棵子树是有次序的则称该树为有序树，此时
6、结点p从左到右的k子树分别称为p的第1棵子树、第2棵子树、第k棵子树。 14无序树：如果树中结点的各棵子树的次序是无关的则称该树为称无序树。 15森林(forest)：森林是m(m0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。,树的表示形式： 树形表示法 嵌套集合表示法 凹入目录表示法 广义表形式的表示法。,由于树形表示法比较直观，所以在本书中主要采用树形表示法来表示树形结构。,树的基本操作： （1）Root ( )：求树根结点的指针，若树为空，则返回0。 （2）CreateRoot ( d ):建立树的根结点，使根结点的数据元素值为d。 （3）Parent( x )：求
7、树中给定结点x的双亲结点的指针，若x为根结点，则返回空。,（4）FirstChild ( x )：求树中给定结点x的第一个孩子结点的的指针，若x为叶子结点，则返回空。 （5）NextSibling ( x, y )：给定结点x、y，其中结点y是结点x的一个孩子。该函数求树中结点y的下一个兄弟结点的指针，若结点y是结点x的最后一个孩子，则返回空。,（6）PreSibling ( x, y ) 给定结点x、y，其中结点y是结点x的一个孩子。该函数求树中结点y的前一个兄弟结点的指针，若结点y是结点x的第一个孩子，则返回空。 （7）Retrieve ( x )：求给定结点x中数据元素的值。 （8）As
8、sign (x，d)：对二叉树中给定结点x赋值为d。 （9）InsertChild ( x,d )：在结点x下插入数据元素值为d的新孩子结点，若插入成功，则返回1；否则返回0。,（10）DeleteChild ( x,i )：删除以结点x的第i个孩子为根的子树，若删除成功，则返回1；否则返回0。 （11）DeleteSubTree ( x )：删除以结点x为根的子树； （12）IsEmpty ( )：判断树是否为空树。若树为空树，则返回1；否则返回0。 （13）Travers（ ）：遍历树，按某种次序依次访问树中的每一个结点，并使每一个结点只被访问一次。,树的抽象数据类型： ADT tree
9、is Data 树的根结点 Operation Root 输入：无 前置条件：无 动作：求树根结点的指针，若树为空，则返回空指针。 输出：树的结点的指针 后置条件：无,CreateRoot 输入：数据元素d 前置条件：无 动作：建立树的根结点，使根结点的数据元素值为d。 输出：树的结点指针 后置条件：无,Parent 输入：树中的结点x 前置条件：无 动作：求树中给定结点x的双亲结点的指针，若x为根结点，则返回空。 输出：树中结点的指针 后置条件：无,FirstChild 输入：树中的结点x 前置条件：无 动作：求树中给定结点x的第一个孩子结点的的指针，若x为叶子结点，则返回空。 输出：树中结
10、点的指针 后置条件：无,NextSibling 输入：树中的结点x、y 前置条件：无 动作：给定结点x、y，其中结点y是结点x的一个孩子。该函数求树中结点y的下一个兄弟结点的指针，若结点y是结点x的最后一个孩子，则返回空。 输出：树中结点的指针 后置条件：无,PreSibling 输入：树中的结点x、y 前置条件：无 动作：给定结点x、y，其中结点y是结点x的一个孩子。该函数求树中结点y的前一个兄弟结点的指针，若结点y是结点x的第一个孩子，则返回空。 输出：树中结点的指针 后置条件：无,Retrieve 输入：树中的结点x 前置条件：结点x必须存在 动作：求给定结点x中数据元素的值 输出：树结
11、点中数据元素 后置条件：无,Assign 输入：树中的结点x和数据元素d 前置条件：结点必须存在 动作：对树中给定结点x赋值为d 输出：无 后置条件：无,InsertChild 输入：结点x和数据元素d 前置条件：结点x必须存在 动作：在结点x下插入数据元素值为d的新孩子结点，若插入成功，则 返回1；否则返回0。 输出：无 后置条件：无,DeleteChild 输入：结点x和序号i 前置条件：结点x必须存在且结点x孩子个数超过i 动作：删除以结点x的第i个孩子为根的子树，若删除成功，则返回1；否则返回0。 输出：1或0 后置条件：无,DeleteSubTree 输入：树中结点x 前置条件：树中
12、结点x 动作：删除以结点x为根的子树 输出：无 后置条件：无,IsEmpty 输入：无 前置条件：无 动作：判断树是否为空。若树为空，则返回1；否则返回0。 输出：1或0 后置条件：无,Travers 输入：无 前置条件：无 动作：遍历树，按某种次序依次访问树中的每一个结点，并使每一个结点只被访问一次。 输出：一般为数据元素序列 后置条件：无 end ADT tree,二叉树,二叉树的定义 : 二叉树BT是有限个结点的集合。当集合非空时，其中有一个结点称为二叉树的根结点，用BT表示，余下的结点（如果有的话）最多被组成两棵分别被称为BT的左子树（left subtree）和右子树（right s
13、ubtree）、互不相交的二叉树。 二叉树的五种形态 :,二叉树的性质 : 性质1：有n(n0)个结点的二叉树的分支数为n-1。 证明：因为在二叉树中，除根结点以外的其它每个结点有且仅有一个父结点。而子结点与父结点间有且只有一条分支，因此对于有n(n0)个结点的二叉树，其分支的数目为n-1。,性质2：若二叉树的高度为h（h0），则该二叉树最少有h个结点，最多有2h-1个结点。 证明：因为在二叉树中，每一层至少要有1个结点，因此对于高度为h的二叉树，其结点数至少为h个。 在二叉树中，第一层只有一个根结点；又因为每个结点最多有2个孩子结点，所以第i层的结点最多为2i-1个，所以高度为h（h0）的二
14、叉树结点总数最多为： 20 + 21 + + 2h-1 = 2h - 1,性质3：含有n个结点的二叉树的高度最大值为n，最小值为log2(n+1) 。 证明：因为在二叉树中，每层至少有一个结点，因此对于含有n个结点的二叉树，其高度不会超过n。 根据性质2可以得知，高度为h的二叉树最多有2h-1个结点，即n2h-1，因此hlog2(n+1)。 由于h是整数，所以hlog2(n+1)。,满二叉树的定义：若高度为h的二叉树具有最大数目（2h-1个）的结点，则称其为满二叉树（full binary tree ）。 完全二叉树的定义：若高度为h的二叉树，除第 h 层外，其它各层 (1 h-1) 的结点数
15、都达到最大个数，并且第 h 层的结点是自左向右连续分布的。则称它为完全二叉树（complete binary tree ）。,性质4：具有 n 个结点的完全二叉树的高度为log2(n+1) 。 证明：设完全二叉树的高度为h，则由性质2得： 2h-1-1n2h -1 2h-1n+12h 不等式中的各项取对数得：h-1log2(n+1)h。因为h为整数，所以h=log2(n+1)。,性质5：如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0、1、2、n-1。则有以下关系： （1）若i0，则 i 无双亲，若i0，则 i 的双亲为i/2-1； （2）若2*i+1n，则 i 的左孩
16、子为2*i+1； （3）若2*i+2n，则 i 的右孩子为2*i+2； （4）若i为偶数，且i1，则 i 是其双亲的右孩子，且其有编号为i-1左兄弟； （5）若i为奇数，且in-1，则 i 是其双亲的左孩子，且其有编号为i+1右兄弟。,证明：此性质可以用归纳法证明，在此先证明其中的(2)和(3)。 当i0时，由完全二叉树的定义得知， 如果2*i+11n，说明二叉树中存在两个或两个以上的结点，所以结点i的左孩子存在且编号为1； 反之，如果2*i+11n，说明二叉树中只有一个结点i，结点i的左孩子结点不存在。 同理，如果2i+22n，说明结点i的右孩子存在且编号为2； 如果2*i+22n，说明二叉树中不存在编号为2的结点，即结点i的右孩子不存在。,假设对于编号为j(0ji）的结点，(2)和(3)成立。 当ij+1时，根据完全二叉树的定义，若其左孩子结点存在则其左孩子结点的编号等于编号为j的结点的右孩子的编号加1，即其左孩子结点的编
