《第6章 树和森林.ppt》由会员分享，可在线阅读，更多相关《第6章 树和森林.ppt（114页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、上海大学计算机学院沈 俊第六章 树和森林JShenstaf 主要内容 树的概念 树的概念 二叉树 二叉树 二叉树的存储结构 二叉树的存储结构 遍历二叉树 遍历二叉树 线索二叉树 线索二叉树 二叉树的应用 二叉树的应用树的概念某家族的血统关系如下：张宇有四个孩子分别是：张山、张川、张星和张月；张山有二个孩子张冰和张雪；张星有三个孩子张雨、张云和张风；张云有两个孩子张亮和张丽。树的定义：树（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 of nod
3、e）：一个结点的子树数目称之为该结点的度。例如在图（c）所示的树中,结点A的度为3，结点C的度数为1,结点E的度数为0。3终端结点(terminal node)：在树中，度为0的结点称为终端结点或叶子(leaf)。如在图6-2（c）所示的树中，结点E，K，L，G，H，M，N，J都是树的叶子。4非终端结点(nonterminal node)：在树中，度不为0的结点称为非终端结点或分支结点。除根结点之外的分支结点也称内部结点。如在图6-2（c）所示的树中，结点A、B、C、D、F、I都是树的分支结点，且结点B、C、D、F、I是树T的内部结点。5树的度（degree of tree）：树的结点中，最大
4、的度称为该树的度。如图6-2（c）所示的树，其度为3。6孩子(child)和双亲(parent)：在树中，结点p的子树的根称为结点p的孩子；反之,这个结点p称为其孩子的双亲（父亲）。如在图6-2（c）所示的树中，结点D为结点A的子树的根，因此结点D是结点A的孩子，结点A是结点D的双亲结点（父结点）。7兄弟(sibling)：在树中，同一个双亲的孩子之间互称为兄弟。例如，在图6-2（c）所示的树中，结点B、C、D互为兄弟。8祖先(ancestor)：在树中，从根结点到结点x所经的分支上的所有结点称为结点x的祖先。如在图6-2（c）所示的树中，结点M的祖先为：A、D、I。9子孙（descendan
5、t）：在树中，以某结点p为根的子树中的所有结点都称为结点p的子孙。例如在图6-2（c）所示的树中，D的子孙有H、I、J、M、N。10结点的层次（level）：在树中，从根结点开始，根为第一层，根的孩子为第二层，依次类推，树中任一结点的层次是其双亲结点层次数加1。例如在图6-2（c）所示的树中，结点K、L、M、N的层次数为4。11树的深度（depth）：树中结点的最大层次称为树的深度或树的高度（height）。例如图6-2（c）所示的树的深度为4。12堂兄弟：双亲在同一层的结点互称为堂兄弟。如在图6-2（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)：求树中给定结点x的双
7、亲结点的指针，若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）Assign(x，d)：对二叉树中给定结点x赋值为d。（9）I
8、nsertChild(x,d)：在结点x下插入数据元素值为d的新孩子结点，若插入成功，则返回1；否则返回0。（10）DeleteChild(x,i)：删除以结点x的第i个孩子为根的子树，若删除成功，则返回1；否则返回0。（11）DeleteSubTree(x)：删除以结点x为根的子树；（12）IsEmpty()：判断树是否为空树。若树为空树，则返回1；否则返回0。（13）Travers（）：遍历树，按某种次序依次访问树中的每一个结点，并使每一个结点只被访问一次。二叉树 二叉树的定义:二叉树BT是有限个结点的集合。当集合非空时，其中有一个结点称为二叉树的根结点，用BT表示，余下的结点（如果有的话
9、）最多被组成两棵分别被称为BT的左子树（left subtree）和右子树（right subtree）、互不相交的二叉树。二叉树的五种形态:二叉树的性质:性质1：有n(n0)个结点的二叉树的分支数为n-1。证明：因为在二叉树中，除根结点以外的其它每个结点有且仅有一个父结点。而子结点与父结点间有且只有一条分支，因此对于有n(n0)个结点的二叉树，其分支的数目为n-1。性质 2：若二叉树的高度为h（h0），则该二叉树最少有h个结点，最多有2h-1个结点。证明：因为在二叉树中，每一层至少要有1个结点，因此对于高度为h的二叉树，其结点数至少为h个。在二叉树中，第一层只有一个根结点；又因为每个结点最多
10、有2个孩子结点，所以第i层的结点最多为2i-1个，所以高度为h（h0）的二叉树结点总数最多为：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 层
11、外，其它各层(1 h-1)的结点数都达到最大个数，并且第 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+1
12、n，则 i 的左孩子为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+11=n，说明二叉树中只有一个结点i，结点i的左孩子结点不存在。同理，如果2i+22n，说明结点i的右孩子存在且编号为2；如果2*i+22=n，说明
13、二叉树中不存在编号为2的结点，即结点i的右孩子不存在。假设对于编号为j(0ji）的结点，(2)和(3)成立。当ij+1时，根据完全二叉树的定义，若其左孩子结点存在则其左孩子结点的编号等于编号为j的结点的右孩子的编号加1，即其左孩子结点的编号等于2*j+2+12*i+1；同样，当ij+1时，根据完全二叉树的定义，若其右孩子结点存在，则其右孩子结点的编号等于其左孩子结点的编号加1，即其右孩子结点的编号等于2i+1+1=2*i+2，因此性质5的(2)，(3)得证。由上述(2)和(3)可很容易证明(1)，证明如下：当i0时，显然该结点为根结点，所以它没有双亲结点。当i0时，设编号为i的结点的双亲结点的
14、编号为f。如果i是其双亲结点的左孩子结点，根据性质5的(2)有i2*f+1（i为奇数），即f(i-1)/2；如果结点i是其双亲结点的右孩子结点，根据性质5的(3)有i2*f+2（i为偶数），即fi/2-1。综合这两种情况可以得到，当i0时，其双亲结点的编号等于i/2-1。因此性质5的(1)得证。二叉树的基本操作:（1）IsEmpty()：判断二叉树是否为空。若二叉树为空，则返回1；否则返回0。（2）Root()：求二叉树根结点的指针，若二叉树为空，则返回空指。（3）CreateRoot(d):建立二叉树的根结点，使根结点的数据元素值为d。（4）Parent(p)：求二叉树中给定结点p的双亲结点
15、的指针，若p为根结点，则返回空。（5）LeftChild(p)：求二叉树中给定结点p的左孩子结点的指针；若结点p没有左孩子，则返回空。（6）RightChild(p)：求二叉树中给定结点p的右孩子结点的指针；若结点p没有右孩子，则返回空。（7）LeftSibling(p)：求二叉树中给定结点p的左兄弟结点的指针；若结点p是其双亲的左孩子或结点p是其双亲的右孩子但其双亲没有左孩子，则返回空。（8）RightSibling(p)：求二叉树中给定结点p的右兄弟结点的指针；若结点p是其双亲的右孩子或结点p是其双亲的左孩子但其双亲没有右孩子，则返回空。（9）Retrieve(p)：求给定结点p中的数据元
16、素的值。（10）Assign(p，d)：对二叉树中给定结点p赋值为d。（11）InsertLeftChild(p,d)：在二叉树中插入数据元素值为d的结点作为结点p的左孩子，若结点p原来有左子树PL，则插入完成后PL作为新结点的左子树。（12）InsertRightChild(p,d)：在二叉树中插入数据元素值为d的结点作为结点p的右孩子，若结点p原来有右子树PR，则插入完成后PR作为新结点的右子树。（13）DeleteLeftChild(p)：删除结点p的左子树。（14）DeleteRightChild(p)：删除结点p的右子树。（15）PreOrderTravers（）：先序遍历二叉树。（
17、16）InOrderTravers（）：中序遍历二叉树。（17）PostOrderTravers（）：后序遍历二叉树。（18）LevelOrderTravers（）：按层次顺序遍历二叉树。二叉树的存储结构 数组表示法:二叉树的数组表示就是采用一组连续存储空间存储二叉树结点中的数据元素，利用数组下标来反映数据元素之间的关系。对具有n个结点的完全二叉树按从上到下、自左向右的顺序连续给结点编号0、1、2、n-1。按此结点编号将二叉树中各结点中的数据元素顺序地存放于一个一维数组中，首先将根结点中的数据元素储存在数组的0号位置；对于二叉树中任一个结点，如果它的数据元素存储在数组的第i个位置，就把它的左、
18、右孩子结点中的数据元素分别存放在数组的第2*i+1个位置和第2*i+2个位置。这样就得到了二叉树的一种数组表示法。采用这种方法表示一般的二叉树时，空间利用效率低是一个主要的问题。当被表示的二叉树结构很不完整时，在数组中就会出现很多空位置，因此空间浪费就变得非常大。用这种方法表示二叉树时，还有一个问题需要注意的是：必须处理结点不存在的情况。如果一个结点不存在，就必须在数组中相应位置设置一个特殊标志，指明在这个位置没有结点。链表表示法:在二叉树的链表表示中，树中的每一个元素用一个结点表示，结点一般包括三个域，其结构如图(a)所示。其中，Data域用于存放数据元素的信息；leftChild域用于存放
19、指向其左孩子结点的指针；rightChild域用于存放指向其右孩子结点的指针。二叉树的这种链表表示称为二叉链表。二叉树的二叉链表表示，对于大多数的应用来说是适合的。但是，在二叉链表中要想找出一个结点的双亲是比较困难的，必须通过二叉树的遍历才能实现。如果在应用中需要方便地找到任何一个结点的双亲，可以在结点中增加一个Parent域来指向该结点的双亲，二叉树的这种表示方法称为三叉链表。二叉树的二叉链表类声明:二叉链表中结点的类定义如下：template struct BinTreeNodeElemType data;/数据域BinTreeNode*leftChild;/左孩子指针域BinTreeNode*rightChild;/右孩子指针域BinTreeNode();/无参数的构造函数 BinTreeNode(const ElemType&valBinTreeNode*lChild=NULL,BinTreeNode*rChild=NULL);二叉树结点类的实现部分1template BinTreeNode:BinTreeNode()/操作结果：构造一个叶结点leftChild=rightChild=NULL;/叶结点左右孩子为空