数据结构第6章(树和二叉树)

数据结构(C++版)第6章桂林电子科技大学信息科技学院赵莹莹由NordriDesign提供@126.com1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面[e-mail]数据结构第六章树和森林[e-mail]本节要点：6.1树的概念6.2二叉树6.3二叉树的存储结构6.4遍历二叉树6.5线索二叉树6.6二叉树的应用6.7树和森林6.8等价类及其表示本章小结[e-mail]树的例子（1）[e-mail]树的例子（2）[e-mail]树（Tree）的定义树(Tree)是n(n≥0)个结点的有限集。(1)当n＝0时，称这棵树为空树。在一棵非空树T中：(2)在n0时，有且仅有一个结点没有前驱，称该结点为根（root）结点。(3)若n1，除根结点之外的其余数据元素被分成m(m0)个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti(1≤i≤m)本身又是一棵树。树T1，T2，…，Tm称为这个根结点的子树（subtree）。ACGT2DHIT3JMBELKT1F空树仅有根结点的树[e-mail]下面列出一些树结构和非树结构的示意图：[e-mail]2.树的表示方法1)直观表示法（a）树的直观表示法是以倒着的分支树的形式表示。2)嵌套集合表示法(b)3)凹入表示法(c)4)广义表表示法(d)6.1.1树的定义及其表示（a）（b）（d）（c）[e-mail]*(b＋c/d)＋e*h－g*f(s，t，x＋y)•(1)表达式中的每一个运算符在树中对应一个结点，称为运算符结点。•(2)运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）。•(3)运算对象中的单变量均为叶子结点。树表示的应用注意：表达式的树型表示不唯一[e-mail]•画出以下表达式的树：•（1+2）*(3-4)+5/6+7课堂练习[e-mail]•结点（node）：树中的每个元素及指向其子树根的分支。•结点的度（degreeofnode）：一个结点的子树。•终端结点（terminalnode）(叶子（leaf)）：度为0的结点。•非终端结点（nonterminalnode）（分支结点）：度不为0的结点。•树的度（degreeoftree）：树结点中最大的度•结点的层次（level）：根为第一层，依次类推。•树的深度（depth）（高度（height））：树中结点的最大层次•有序树：树中结点的子树是有次序的。•无序树：树中结点的子树是无次序的。•森林（forest）：m（m=0）棵不相交的子树的集合。6.1.2树的术语[e-mail]在树结构中，结点之间的关系又可以用家族关系描述，定义如下：•孩子（child）和双亲（parent）：结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。•兄弟（sibling）：同一个双亲的孩子之间互为兄弟。•堂兄弟：双亲在同一层的结点互为堂兄弟。•祖先（ancestor）：从根结点到该结点路径上的所有结点。6.1.2树的术语[e-mail]6.1.3树的基本操作和抽象数据类型ADTtreeisDATA树的根结点OperationRoot()//求树的根结点的指针，若树为空，则返回空指针CreateRoot（d）//建立树的根结点，根结点的数据元素的值为dParent（x）//求树中给定的结点x的双亲的指针，若x为根结点，则返回空FirstChild（x）//求树中给定结点x的第一个孩子结点的指针，若x为叶子，返回空NextSibling（x，y）//给定结点x，y，y是x的孩子结点，求树中y结点的下一个兄弟结点的指针。若y是最后一个孩子，则返回空Retrive（x）//求给定结点x中数据元素的值InsertChild（x，d）//在x结点下插入数据元素值为d的新孩子结点DeleteChild（x，i）//删除以结点x的第i个结点为根的子树IsEmpty（）//判断树是否为空Travers（）//遍历树，按某种次序依次访问树中的每一个结点[e-mail]本节要点：6.1树的概念6.2二叉树6.3二叉树的存储结构6.4遍历二叉树6.5线索二叉树6.6二叉树的应用6.7树和森林6.8等价类及其表示本章小结[e-mail]二叉树（BT）是一种特殊的树型结构。它与树型结构的区别是：(1)每个结点最多有两棵子树；二叉树结构的图形表示示例如右图所示：(2)子树有左右之分(lefttree，righttree)。二叉树的五种基本形态如下图所示：6.2.1二叉树(binarytree)的定义二叉树的五种基本形态空二叉树仅有根结点右子树为空左子树为空左右子树均非空[e-mail]二叉树树•三个结点的树和二叉树的区别：[e-mail]二叉树的递归定义•二叉树是n个结点的有限集，满足如下两个条件：•(1)有且仅有一个根结点。•(2)其余的结点分成两颗互不相交的左子树和右子树。[e-mail]6.2.1二叉树的性质（1）•性质1在二叉树的第i层上最多有2i－1个结点（i=1）423167891011121314155第3层，最多4个第1层，最多1个第2层，最多2个第4层，最多8个20212223第i层，最多?个[e-mail]二叉树的性质（2）•性质2深度为k的二叉树最多有2k－1个结点（k=1）1*1nnaaqSq423167891011121314155第3层，最多4个第1层，最多1个第2层，最多2个第4层，最多8个20212223012222112KK依据：共：[e-mail]二叉树的性质（3）（补充）•性质3有n个结点的二叉树分支数为[e-mail]二叉树的性质（4）•性质4在一颗任意二叉树中，若叶结点的个数为n0，双分支结点数为n2，则n0＝[e-mail]二叉树的性质（5）（定义）•性质5若高度为h的二叉树具有最大数目的结点数（2h－1）个结点，则称为满二叉树。[e-mail]二叉树的性质（6）定义•性质6若高度为h的二叉树，除了第h层外，其它各层结点数都达到最大值，并且第h层的结点自左到右连续分布．则称为完全二叉树[e-mail]课堂练习•完全二叉树的结点个数为11，则它的叶结点个数为?•[e-mail]本节要点：6.1树的概念6.2二叉树6.3二叉树的存储结构6.4遍历二叉树6.5线索二叉树6.6二叉树的应用6.7树和森林6.8等价类及其表示本章小结[e-mail]用一组连续的存储单元去存储二叉树结点的数据元素。二叉树的顺序存储结构10ABcFED●●●●●●●●●0137894526111213140000FE000DC0BA15141312111098765432100数组的下标与编号对应存储空间存在一定程度的浪费,什么情形下才能有效利用存储空间？[e-mail]较好的情况：完全二叉树的顺序存储DBCAFGHIJKLE0000LKJIGFEDCBA1514131211109876543210H01234567891011对于完全二叉树，其顺序存储结构形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。[e-mail]较坏的情况：单分支较多的二叉树的顺序存储CAFL01234567891011大量空的存储空间，存储密度不高[e-mail]二叉树的链式存储结构——二叉链表•其中，Lchild和Rchild是分别指向该结点左孩子和右孩子，data是数据元素的内容。•对应的结构类型定义如下：Typedefstructnode{Elemtypedata;structnode*lchild;structnode*rchild;}Btree,*[e-mail]^DB^C^^E^^F^下图二叉树的二叉链表结构如下：AECBDF二叉链表实例特点：1，n个结点，多少个指针域2，多少个空指针域3，找孩子易，找双亲难[e-mail]带双亲指针二叉链表•其中，Lchild和Rchild是分别指向该结点左孩子和右孩子，parent指向该结点的双亲data是数据元素的内容。•对应的结构类型定义如下：Typedefstructnode{Elemtypedata;structnode*lchild;structnode*rchild;structnode*parent;}Btree,*[e-mail]^^DB^C^^E^^F^下图二叉树的带双亲指针的二叉链表结构如下：AECBDF带双亲指针的二叉链表实例[e-mail]1.二叉树的链式存储结点的定义typedefintDataTypeclassBinaryTree;ClassBinTreeNode{public:DataTypedata;BinTreeNode*leftChild;BinTreeNode*rightChild;BinTreeNode(){leftChild=NULL;rightChild=NULL;}//构造函数，构造一个空结点};6.3.2二叉树的存储结构[e-mail]{public:BinTreeNode*root;BinaryTree(){root=NULL;}~BinaryTree(){DeleteTree();}boolInsertLeft(BinTreeNode*current,DataTypex);//将元素x插入作为current所指结点的左孩子voidPreorder(BinTreeNode*current);//先序遍历voidInOrder(BinTreeNode*current);//中序遍历voidPostorder(BinTreeNode*current);//后序遍历voidDestroy(BinTreeNode*current);//删除指定子树voidDeleteTree(){Destroy(root);root=NULL;}//删除整棵树boolIsEmpty(){returnroot==NULL}//判树空否};6.3.2二叉树的存储结构(8)[e-mail]二叉树部分成员函数的实现(1)boolBinaryTree::InsertLeft(BinTreeNode*current,DataTypeitem)//插入左孩子{if(current==NULL)returnfalse;BinTreeNode*p=newBinTreeNode;p-data=item;current-leftChild=p;returntrue;}[e-mail]::destroy(BinTreeNode*current)//删除指定子树{if(current!=NULL){destroy(current-leftChild);dest