第七章 树状结构

第七章树状结构第一页，共五十三页，编辑于2023年，星期四7.1何谓树状结构树状结构在计算机信息处理中应用相当广泛，如文件系统、目录组织、菜单管理等。树状结构中常见的是树和二叉树，本章介绍这两种结构的概念、存储结构和相关算法，并研究树、二叉树之间的相互转换，最后给出树形结构在现实生活中的一些具体应用。第二页，共五十三页，编辑于2023年，星期四7.1何谓树状结构树是n（n≥0）个有限元素（习惯称作结点）的集合T。当n=0时，称这棵树为空树；当n>0时，集合T满足如下条件：（1）有且只有一个称为根（Root）的结点，它没有直接前驱，但有零个或多个直接后继；（2）其余的n-1个结点可以划分为m个互不相交的有限集T1，T2，T3，…，Tm，其中每个集合Ti又是一棵树，称为根（Root）的子树。每棵子树的根结点有且只有一个直接前驱，但有零个或多个直接后继。可以看出，树的定义用到了递归的方法，即用树来定义树，这种方法在后面树（特别是二叉树）的遍历、建立等算法中经常用到。

第三页，共五十三页，编辑于2023年，星期四7.1.1何谓树从图中树T可知，节点A为树T的根节点(root)，B,C,D….,M则为节点A的子节点，若包含其下拥有的所有子节点，则为Tree—T的子树(subtree)。例如B是A的子节点，P、Q皆是B的子节点，而B、P、Q为树T的子树。第四页，共五十三页，编辑于2023年，星期四7.1.2树的相关名称及意义(1) 根节点(rootnode)： 一棵树中没有前驱节点的节点，称为根节点。(6) 分支度(度)(degree)：节点的分支度为每个节点所拥有的子节点个数。而一棵树中最大的分支度值，即为该树的分支度。(2) 叶节点(leafnode)或终端节点(terminalmode)：一棵树中没有子节点的节点，称为叶节点。叶节点的分支度为0。(3) 非终端节点(nonterminalmode)除了叶节点以外的其它节点，称为非终端节点。(4) 父节点(parent)和子节点(child)：若节点x有一个以节点y为树根(root)的子树，则x为y的父节点，而y为x的子节点。节点的前驱节点称为该节点的父节点。树中一个节点的子树的根节点称为该节点的子节点。第五页，共五十三页，编辑于2023年，星期四7.1.2树的相关名称及意义(5) 兄弟(sibling)：同一个父节点之节点，称为兄弟。如图，B、C、D的父节点均为A，故B、C、D互为兄弟。(9) 祖先(ancestor)：某节点x的祖先是从根到该节点所经分支上的所有节点。(7) 节点的阶层（层次）(level)： 阶层为节点之特性值，将根节点之阶层设为1，其子节点为2，依此类推。(8) 高度(height)或深度(depth)： 一棵树中的最大阶层值，称为树的高度或深度。(10) 树林(forest)：n≧0个树的集合称为树林。若将一树的根节点移去，所剩这恰是一树林。第六页，共五十三页，编辑于2023年，星期四7.2二叉树7.2.1何谓二叉树 二叉树(Binarytree)是树的一种，二叉树中的节点至多只能有两个子节点。 二叉树的定义如下：(1) 由有限个节点所构成之集合，此集合可以为空的。(2) 二叉树的根节点下可分成两个子树，称为左子树和右子树，左子树和右子树亦称二叉树。第七页，共五十三页，编辑于2023年，星期四7.2.1何谓二叉树由二叉树的定义可知，每个节点只能有0、1或2个子树，且每个子树有左右之分。把位于左边的叫做左子树，右边的叫做右子树。即使只有一棵子树时，也要区分它是左子树还是右子树。第八页，共五十三页，编辑于2023年，星期四7.2.3二叉树的相关特色二叉树的性质：(1)阶层(level)为i的二叉树，最多有2i-1个节点。(2)高度(height)为h的二叉树，最多有2h－1个节点。(3)对任一个非空的二叉树而言，若分支度为i的节点各有ni个，则n0=n2+1第九页，共五十三页，编辑于2023年，星期四(1) 满二叉树(fullbinarytree)一树中所有叶节点均在同一阶层，而其它非终端节点(nonterminalnode)之分支度均为2，则此树为一满二叉树。若该树的高度为h，则此二叉树的节点为2h-1。第十页，共五十三页，编辑于2023年，星期四(2) 完全二叉树(completebinarytree)一棵树扣除掉最大阶层那层后为一满二叉树，且阶层最大那层的节点均向左靠齐，则该二叉树称为完全二叉树。在一棵深度为k，结点为n的二叉树中，对树中结点按从上到下，从左到右的顺序编号，完全二叉树中编号为1~n的结点分别与满二叉树中编号为1~n的结点位置一一对应。第十一页，共五十三页，编辑于2023年，星期四7.3二叉树表示法二叉树节点的表示法，常用的有下列3种方法：(1) 二叉树数组表示法(2) 二叉树结构数组表示法(3) 二叉树链表表示法其中“数组表示法”和“结构数组表示法”是属于静态内存空间配置，而“链表表示法”是利用列表结构的方式，属于动态内存空间配置。第十二页，共五十三页，编辑于2023年，星期四7.3.1二叉树数组表示法对于一棵满二叉树，将其结点从上到下，从左到右顺序编号，再根据编号存入对应下标编号的数组中。如果该树不为满二叉树，也可对各节点编成在满二叉树中相同位置之节点编号值，再以相同的方式存入数组中，若某一编号没有节点存在，则不存值于数组中。假设一父节点的编号为n左子节点的编号为：2n，右子节点的编号为：2n+1。第十三页，共五十三页，编辑于2023年，星期四7.3.1二叉树数组表示法优点：对于任意一个节点都能很容易的找到其父节点、子节点及兄弟。缺点：这样将导致存储空间的浪费，极端的情况是对于一个二叉树，每个结点只有右孩子而无左孩子时，假设该树的深度为k，则需要2k-1个存储单元，而实际只利用了其中的k个存储单元。第十四页，共五十三页，编辑于2023年，星期四7.3.3二叉树链表表示法（二叉链表）链表的节点结构如下：每个节点包含三个域：数据域（Data）：存储结点的数据内容左指针域（left）：指向该节点的左子树右指针域（right）：指向该节点的右子树由这种链式存储结构构成的二叉树称为二叉链表。第十五页，共五十三页，编辑于2023年，星期四7.3.3二叉树链表表示法（二叉链表）二叉链表结构的声明如下：strusttree{structtree*left;intdata;structtree*right;}typedefstructtreetreenode;treenode*b_tree;第十六页，共五十三页，编辑于2023年，星期四7.4二叉树的遍历“遍历”是访问数据结构中的各个数据值，例如：数组和链表可从前端到尾端或从尾端至前端依序访问各个数据值。而二叉树是一种特殊的数据结构，每个节点其下又各有左、右两个分支。“二叉树的遍历”是以固定的顺序，有系统地访问二叉树中的各节点，且每个节点均恰好被访问一次。第十七页，共五十三页，编辑于2023年，星期四一棵二叉树由根结点、左子树和右子树三部分组成，若依次遍历这三部分，也就遍历了整棵树。这里用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，。若按照从左到右的顺序进行遍历，则有LDR、DLR、LRD三种方式，它们分别称为中序遍历、前序遍历和后序遍历。第十八页，共五十三页，编辑于2023年，星期四7.4.1二叉树的前序遍历前序遍历二叉树的算法为：若二叉树为空，则遍历结束，否则依次执行以下操作：（1）访问根结点；（2）前序遍历根结点的左子树；（3）前序遍历根结点的右子树。第十九页，共五十三页，编辑于2023年，星期四其具体算法实现如下：voidpreorder(b_treepoint){if(point!=NULL)/*遍历的终止条件*/{printf("%d",point->data);/*处理打印节点内容*/ preorder(point->left); /*处理左子树*/ preorder(point->right);/*处理右子树*/}}第二十页，共五十三页，编辑于2023年，星期四7.4.2二叉树的中序遍历中序遍历二叉树的算法为：若二叉树为空，则遍历结束，否则依次执行以下操作：（1）中序遍历根结点的左子树；（2）访问根结点；（3）中序遍历根结点的右子树。第二十一页，共五十三页，编辑于2023年，星期四其具体算法实现如下：voidinorder(b_treepoint){if(point!=NULL) /*遍历的终止条件*/{inorder(point->left); /*处理左子树*/printf("%d",point->data); /*处理打印节点内容*/inorder(point->right); /*处理右子树*/}}第二十二页，共五十三页，编辑于2023年，星期四voidinorder(b_treepoint){if(point==NULL) /*遍历的终止条件*/return;else{inorder(point->left); /*处理左子树*/printf("%d",point->data); /*处理打印节点内容*/inorder(point->right); /*处理右子树*/}}第二十三页，共五十三页，编辑于2023年，星期四7.4.3二叉树的后序遍历后序遍历二叉树的算法为：若二叉树为空，则遍历结束，否则依次执行以下操作：（1）后序遍历根结点的左子树；（2）后序遍历根结点的右子树；（3）访问根结点。第二十四页，共五十三页，编辑于2023年，星期四其具体算法实现如下：voidpostorder(b_treepoint){if(point!=NULL) /*遍历的终止条件*/{postorder(point->left); /*处理左子树*/postorder(point->right); /*处理右子树*/printf("%d",point->data); /*处理打印节点内容*/}}第二十五页，共五十三页，编辑于2023年，星期四【例】有一棵二叉树的前序遍历序列为A、C、I、K、N、H、L、M，中序遍历序列为I、C、N、K、A、L、M、H，试画出此二叉树。由于在前序遍历中首先访问根节点，因此，前序序列中的第一个结点为二叉树的根节点，即A为二叉树的根节点。又由于在中序遍历中访问根节点的次序为居中，左子树的节点居前，右子树的节点居后，因此，在中序序列中，以根结点（A）为分界线，前面的子序列（I、C、N、K）一定在左子树中，后面的子序列（L、M、H）一定在右子树中。同样的道理，对于已经划分出的每一个子序列的所有节点中，位于前序序列最前面的一个节点为子树的根节点，而在中序序列中位于该根节点前面的节点构成左子树的节点子序列，位于该根节点后面的节点构成右子树的节点子序列。按此规则不断循环下去，直到所有的子序列为单个节点为止，其求解过程如图所示。第二十六页，共五十三页，编辑于2023年，星期四第二十七页，共五十三页，编辑于2023年，星期四7.5二叉树的建立(递归法)给定一个二叉树数组结构，使用递归方式建立一棵二叉树，并以中序遍历的方式输出二叉树节点内容。第二十八页，共五十三页，编辑于2023年，星期四b_treecreate_btree(int*nodelist,intposition){b_treenewnode;/*声明新节点指针*/

if(nodelist[position]==0||position>15)/*递归的终止条件*/returnNULL;else{/*-----建立新节点的内存空间----*/newnode=(b_tree)malloc(sizeof(treenode));

/*-------------建立节点内容--------------*/newnode->data=nodelist[position];/*------------递归建立左子树------------*/newnode->left=create_btree(nodelist,2*position);/*------------递归建立右子树------------*/newnode->right=create_btree(nodelist,2*position+1);returnnewnode; /*返回复制树的位置*/}}第二十九页，共五十三页，编辑于2023年，星期四7.8二叉树的复制使用递归方式建立二叉树，再复制原来的二叉树，并输出原本的二叉树和备份二叉树的节点内容。第三十页，共五十三页，编辑于2023年，星期四b_treecopy_btree(b_treeroot){b_treenewnode;/*声明新节点指针*/

if(root==NULL) /*递归的终止条件*/returnNULL;else{/*-----建立新节点的内存空间----*/newnode=(b_tree)malloc(sizeof(treenode));/*-------------建立节点内容--------------*/newnode->data=root->data;/*------------递归建立左子树------------*/newnode->left=copy_btree(root->left);/*------------递归建立右子树------------*/newnode->right=copy_btree(root->right);returnnewnode; /*返回复制树的位置*/}}第三十一页，共五十三页，编辑于2023年，星期四7.6二叉查找树二叉查找树(Binarysearchtree)的条件：每个节点的数据要大于左子节点的数据，且要小于右子节点的数据。具体来说：（1）若它的左子树非空，则左子树上所有结点的值均小于根节点的值；（2）若它的右子树非空，则右子树上所有结点的值均大于根节点的值；（3）左、右子树本身也分别为二叉查找树；第三十二页，共五十三页，编辑于2023年，星期四二叉查找树的性质：（1）二叉查找树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字；（2）二叉查找树中，各结点关键字是惟一的（3）按中序遍历该树所得到的中序序列是一个递增有序序列。第三十三页，共五十三页，编辑于2023年，星期四7.6二叉查找树(二叉查找树的插入)二叉查找树的插入：以第一个元素为根节点依序将元素值与根节点做比较若元素值大于根节点值，则将该元素值往根节点之右子节点移动，若此右子节点为空，则将元素值存入，否则就重复比较，直到找到适当的空节点为止。若元素值小于根节点值，则将该元素值往根节点之左子节点移动，若此左子节点为空，则将元素值存入，否则就重复比较，直到找到适当的空节点为止。第三十四页，共五十三页，编辑于2023年，星期四b_treeinsert_node(b_treeroot,intnode){/*声明树根指针*//*声明目前节点指针*//*声明父节点指针*//*建立新节点的内存空间*/newnode=(b_tree)malloc(sizeof(treenode));/*存入节点内容*//*设置右指针初值*//*设置左指针初值*/if(root==NULL)returnnewnode;/*返回新节点的位置*/else{currentnode=root;/*存储目前节点指针*/while(currentnode!=NULL){parentnode=currentnode;/*存储父节点指针*/if(currentnode->data>node)/*比较节点的数值大小*/ currentnode=currentnode->left;/*左子树*/elsecurrentnode=currentnode->right;/*右子树*/}if(parentnode->data>node)/*将父节点和子节点做连结*/parentnode->left=newnode;/*子节点为父节点之左子树*/elseparentnode->right=newnode;/*子节点为父节点之右子树*/}returnroot;/*返回根节点之指针*/}第三十五页，共五十三页，编辑于2023年，星期四二叉查找树的生成二叉查找树的生成，是从空的二叉查找树开始，每输入一个结点数据，就调用一次插入算法将它插入到当前已生成的二叉查找树中。第三十六页，共五十三页，编辑于2023年，星期四二叉查找树的生成算法b_treecreate_btree(int*data,intlen){b_treeroot=NULL; /*根节点指针*/inti;for(i=0;i<len;i++) /*建立树状结构*/root=insert_node(root,data[i]);returnroot;}第三十七页，共五十三页，编辑于2023年，星期四7.6.2二叉树的查找方法在二叉查找树上进行查找是一个从根结点开始，沿某一个分支逐层向下进行比较判断是否相等的过程。即当二叉查找树非空时，将给定值和根结点关键值比较：若相等，则查找成功，返回找到结点的地址；否则根据给定值与根结点关键字之间的大小关系，分别在左子树或右子树上继续查找，直到左子树或右子树空为止，此时查找失败，返回空值。第三十八页，共五十三页，编辑于2023年，星期四b_treebtree_traversal_search(b_treepoint,intfindnode){while(point!=NULL){if(point->data==findnode)/*找到了欲寻找的节点*/returnpoint;/*返回找到节点的指针*/elseif(point->data>findnode) point=point->left; /*往左子树找*/else point=point->right; /*往右子树找*/}returnNULL;/*该节点不在此二叉树中*/}第三十九页，共五十三页，编辑于2023年，星期四7.7二叉树(二叉查找树)的节点删除对于一个二叉树，若欲删除其节点，应先寻找欲删除的节点是否存在于该二叉树中。关于二叉树的节点查找，前面已有详细的介绍，本节将说明如何将节点从二叉树中删除。由于我们在删除一个节点后，必须要维持满足二叉查找树数据排列的原则：左子节点<节点<右子节点。而删除节点的处理可分4种情况，我们将对各种情况做详细的说明。第四十页，共五十三页，编辑于2023年，星期四7.7.1节点无左子树，无右子树当欲删除一无左子树也无右子树的节点时，需要考虑到两种情况：(1)为根节点如欲删除无左、右子树的根节点，只需将根节点指针root指向NULL即可。(2)非根节点若一节点为无左、右子树的非根节点，那么该节点必为叶节点。如果节点为父节点的左子节点，则将父节点的左指针指向NULL，相同地，若节点为父节点的右子节点，则将父节点的右指针指向NULL。第四十一页，共五十三页，编辑于2023年，星期四7.7.2节点有左子树，无右子树当欲删除一有左子树但无右子树的节点时，也需去考虑两种情况：(1)为根节点欲删除有左子树，无右子树之根节点，只需将根节点指针root指向其左子树。(2)非根节点一节点为左子树，无右子树的非根节点，若节点为父节点的左子节点，则将父节点的左指针指向节点的左子节点，相同地，若节点为父节点的右子节点，则将父节点的右指针指向节点的左子节点。第四十二页，共五十三页，编辑于2023年，星期四7.7.3节点无左子树，有右子树如图中节点8。第四十三页，共五十三页，编辑于2023年，星期四7.7.4节点有左子树，有右子树需要找一个替代的节点值，以免大量的移动节点找节点左子树的最右边的点找节点右子树最左边的点第四十四页，共五十三页，编辑于2023年，星期四7.12引线二叉树(线索二叉树)具有n个结点的二叉树，其二叉链表中共有2n个指针域。由于除根结点外，对于每个结点都有一个指针指向该结点，因此实际只有n-1个指针域被使用，而另外n+1个指针域是空的，可以利用这n+1个空指针存放某种遍历方式下指向前驱结点和后继结点的指针，这种附加的指针称为“引线”，加上了引线的二叉树称为引线二叉树。第四十五页，共五十三页，编辑于2023年，星期四Lchild是指针，指向结点的左子结点Lchild是引线，指向结点的前驱结点Rchild是指针，指向结点的右子结点Rchild是印线，指向结点的后继结点第四十六页，共五十三页，编辑于2023年，星期四structthread_tree{intdata;/*节点数据*/structthread_tree*Lchild;/*左指针*/structthread_tree*Rchild;/*右指针*/intLthread;/*标示是否为左引线*/intRthread;/*标示是否为右引线*/};typedefstructthread_treetreenode;/*定义新类型树状结构*/typedeftreenode*t_btree;第四十七页，共五十三页，编辑于2023年，星期四引线二叉树的建立方式了解引线二叉树的节点结构及声明方法后，则要进一步说明引线二叉树的建立方式。事实上，引线二叉树的建立方式和一般二叉树相同，只是要额外考虑指针字段和引线字段的内容，规则如下：if左指针为空then Lchild指到在该树中序遍历的前一个节点 将Lthread设为1if右指针为空then Rch