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

第六章树和二叉树6.1树（tree）的概念在日常生活中，可以见到很多情形可以归结为树结构。如：家族谱系、行政管理机构、DOS和Windows磁盘文件管理系统等。我们讨论的树和自然界的树在生长方向上正好相反，它是倒长的树，即根朝上，枝干和叶子朝下。例1：某家族谱系的一部分例2：国家行政管理机构的一部分景奇宏恩新民意海新主意河意江宏福新华意民宏亮新诚意凌新胜意山意水例3：DOS和Windows磁盘文件的一部分C:\TC20VC6.0数据结构课件数据结构讲稿第一章第二章……MyTc程序Tc1Tc2……MyVc程序国务院河北省廊坊市石家庄市北京市海淀区西城区昌平县天津市内蒙古区Vc1Vc2……树是一种层次结构，属于非线性结构。我们学过的线性表可以灵活组织数据，但它受到线性结构的限制，表达层次结构不太方便。6.1.1树的定义·树T是n（n≥0）个结点的有限集合。它满足：(1)仅有一个特定的结点，称为根（root）结点;(2)其余结点分为m(m≥0)个互不相交的非空有限集合T,1,T2,……,Tm,其中每个集合自身又是一棵树，称为根的子树（subtree）。·为了表述方便，把没有结点的树称为空树。·树的定义具有递归性：即一棵树是由根及若干棵子树构成的，而子树又是由根及若干棵子树构成的，……。表达树的方法通常有4种：树形、凹入、集合和广义表(1)树形表示法(2)凹入表示法(3)集合嵌套表示法A○EC○F○GD○HBBCEFDGHABCDEFGHA(4)广义表表示法T(A(B,C(E,F),D(G,H)))6.1.3树的基本术语为了对树的形态表述清楚和形象，通常引用树和人的特征及术语来描述。（1）结点和树的度（degree）结点所拥有的子树的个数称为该结点的度，而树中各结点的度的最大值称为该树的度。如：·结点B、E、F、G和H的度数是0·结点C和D的度数都是2·结点A的度数是3；显然3也是树的度数（2）叶子（leaf）结点和分支结点度为0的结点称为叶子结点（终端结点）；度不为0的结点称为分支结点（非终端结点）。一棵树除了叶子结点就是分支节点。ABCDEFGH如:·结点B、E、F、G和H是叶子结点·结点A、C和D是分支结点（3）孩子（child）结点、双亲（parents又称父亲）结点、兄弟（brother）及堂兄弟结点树中一个结点的子树的根称为该结点的孩子，该结点称为其孩子结点的双亲结点。同一个双亲的孩子结点互称为兄弟。双亲在同一层的结点互为堂兄弟。如:·结点B、C和D均为结点A的孩子结点；A是B、C和D的双亲结点·结点E和F为孩子C的结点；C是E和F的双亲结点·结点G和H为孩子D的结点；D是G和H的双亲结点ABCDEFGHABCDEFGH·显然结点A没有双亲结点（因为A不是子树的根）·结点B、C和D互为兄弟；结点E和F互为兄弟；结点G和H互为兄弟。但结点E、F为一方和G、H为另一方互为堂兄弟（4）祖先（ancestor）和子孙（descendant）结点的祖先是从根到该所经分支上的所有结点。反之，以某结点为根的子树中的任一结点称为该结点的子孙。显然祖先和子孙关系是父子关系的延伸。如：·结点A是结点B、C、D、E、F、G和H的祖先；反之，结点B、C、D、E、F、G和H是的结点A的子孙（5）结点的层数（level）和树的深度(depth，或称高度height）结点的层次从根结点开始算起，根结点的层数为1，其余结点的层数等于其双亲结点的层数加1。比如，如果某个结点的层数为h，则其子树就在第h+1层。树中各个结点层数的最大值称为树的深度（高度）。ABCDEFGH如:·结点A的层数为1；结点B、C和D的层数为2；结点E、F、G和H的层数为3·树的深度（高度）为3。（6）有序树（orderedtree）和无序树（unorderedtree）若一棵树中结点的各子树从左到右是有次序的，即若交换了某结点各子树的相对位置就构成不同的树，则称这棵树为有序树，否则称为无序树。（7）路径（path）从树中的一个结点到另一个结点的路途如：A-C-E,A-D-H等但B-A-D-G不是路径，因为树不能这样遍历。（8）森林（forest）：m（m≥0）棵互不相交的树的集合ABCDEFGHABCDEFGH树的逻辑关系：（1）树的任一结点都可以有0个或多个直接的后继结点（孩子，这也是非线性的原因），但至多只能有一个直接的前驱结点（双亲结点）；（2）只有根结点没有前驱，叶子结点（终端结点）没有后继；（3）祖先与子孙关系是父子关系的延伸，它定义了树中各结点之间的纵向次序；（4）在有向树中，同一组兄弟结点从左至右有长幼之分。它定义了树中各结点之间的横向次序。6.1.4树的基本操作常见的操作：建立、遍历、查询、求深度、求结点的双亲和孩子、求树的深度、求结点的层数和判空等。6.2二叉树一般的树规律性差，二叉树结构简单，存储和处ABCDABCDEFGH理相对容易，而且一般的树可以转化为二叉树处理。6.2.1二叉树的定义·二叉树是n（n≥0）个结点的有限集合，除了空树（n=0）之外，由一个根结点及两棵不相交的左子树和右子树组成；·二叉树每个结点的度数≤2；·二叉树的定义是一个递归定义。二叉树有5种基本形态：❶空树Φ❷只有根结点○A❸只有右子树○A○C❹只有左子树○A○B❺完整二叉树○A○B○C6.2.2二叉树的性质性质1：二叉树的第i层的结点数量最多为)1(21ii。证明：第1层的结点数目最多为1（20），第2层的结点数目最多为2（21），……，则第i层的结点数目最多为21i。性质2：深度为k的二叉树结点数目最多为)1(12kk。证明：当其每层的结点数达到最大值时，该二叉树的结点数最多，由性质1可知，深度为k的二叉树结点数是：1222221210......kk。性质3：在任意二叉树中，若叶子（终端）结点的个数为n0，度为2的结点数为n2，则有120nn。证明：设n为结点总数，n1为1度的结点数，则nnnn210（公式1）先分析二叉树的结点度数和分支数的关系：由于度数为2的结点有两个分支，度数为1的结点有一个分支，度数为0的结点没有分支，所以总的分支数为nn212；ABCDEFG此外，再分析二叉树的双亲结点和分支数的关系：除根结点之外的每个结点都是其双亲结点的一个分支，所以总分支数为1n，可得关系式1212nnn，即1212nnn（公式2）；由公式1和2，可得120nn，证毕。如：叶子数为3（C，E，F），度数为2的结点数为2（A，B），满足性质3。又如：叶子数为2（F，G），度数为2的结点数为1（A），满足性质3。ABDFEC●满二叉树的定义：深度为k（k≥1）且结点数为12k的二叉树。满二叉树的结点数达到最大值。如：深度为3的满二叉树结点达到7个●完全二叉树的定义：对于满二叉树的结点，按下列规则编号：❶从根结点开始，自上而下；ABDFCEGA1B2C3D4E5F6G7❷同一层自左至右。满二叉树的结点编号后，任意取满二叉树的前若干个连续的结点所对应的二叉树，称为完全二叉树。完全二叉树中，除最后一层外，其余各层均是满的，最后一层，结点连续出现在左边。如：深度为4的完全二叉树又如：第2层结点不是连续出现在左侧，所以不是完全二叉树ABDHIEJCFG再如：第3层未满，所以不是完全二叉树性质4：具有n个结点的完全二叉树的深度为：1+nlog2(int)。证明：由完全二叉树和满二叉树的关系可知，一棵ABCDEABDFEC深度为k的完全二叉树的结点数必介于深度为k-1和深度为k的满二叉树的结点数之间，则有12121kkn（取等号的情况是：完全二叉树是深度为k的满二叉树），由此推出21221kkkn，即knklog21，所以nklog2(int)1性质5：如果一棵完全二叉树有n个结点，对所有结点按层次编号（即从上到下），每层从左到右从1开始编号，则对任意结点i（1≤i≤n），有：❶若i=1，则其为根，没有双亲。若i1，则其双亲为(int)(i/2);❷若2i≤n（即它有左子树），则其左子树编号为2i;若2in，则其无左子树。若2i+1≤n（即它有右子树），则其右子树的编号为2i+1;若2i+1n，则其无右子树。A1B2D4H8I9E5J10C3F6G7分析：编号为i=4的结点D，该树的结点数n=10；因i1，所以其双亲结点是(int)(i/2)=2(即B)；又因2i=2*4≤10，所以该结点有左子树，左孩子编号为2i=8（即H）；再因2i+1=9≤10,所以该结点有右子树，右孩子编号为2i+1=9（即I）再分析：编号为i=5的结点E，因i1，所以其双亲结点是(int)(i/2)=2(即B)；又因2i=2*5≤10，所以该结点有左子树，左孩子编号为2i=10（即J）；再因2i+1=1110,所以该结点没有右子树。6.3二叉树的存储结构常用顺序存储结构和链式存储结构。6.3.1二叉树的顺序存储结构·对于完全二叉树进行结点编号后，编号可以反映结点的分支和从属关系，可以将这些结点存入一维数组，编号和数组下标可以对应起来。·对于一般的二叉树，不易直接采用顺序存储，可以补成完全二叉树后再用顺序存储的方法存储。以上两点是定义完全二叉树的原因之一。如：一棵普通二叉树由上图用虚结点（@）补成的完全二叉树再顺序存储位置[1][2][3][4][5][6][7][8][9][10][11][12][13]结点ABC@DE@@@F@@G定义：ABDFCEGA1B2@4@8@9D5F10@11C3E6@12G13@7#defineMAXSIZE100typedefcharDataType;typedefstruct{DataTypebt[MAXSIZE+1];intnum;}SeqBTree;·顺序存储结构比较适合于完全全二叉树，对于一般的二叉树需要引进虚结点，补成完全二叉树后再顺序存储。6.3.2二叉树的链式存储结构结点模式：root定义：typedefstructnodeA^BC^D^^E^F^^G^lchilddatarchild{DataTypedata;structnode*lchild,*rchild;}BTree;此种定义称为二叉树的二叉链表。在链式结构中，通过每个结点的左右指针域，可以找到其孩子结点，但要找双亲结点不方便，可以增加一个指针域保存双亲结点的地址，称为带双亲指针的二叉链表。结点模式：root定义：typedefstructnode{DataTypedata;A^^BC^D^^E^F^^G^lchilddataparentsrchildstructnode*lchild,*parents,*rchild;}ThTree;6.4二叉树的遍历·遍历首先从根结点进入，对每个结点都要遍历到且每个结点仅遍历一次。·可以采用递归方法（程序简单）和非递归方法（程序稍复杂）。遍历二叉树，可有6+1种方法（实际采用3+1种）：·第一种方法：先序遍历：根，左子树，右子树遍历的结果：A，B，C遍历的足迹：沿途经过各结点的“左部”·第二种方法：中序遍历：左子树，根，右子树遍历的结果：B，A，C遍历的足迹：沿途经过各结点的“下部”·第三种方法：ABC后序遍历：左子树，右子树，根遍历的结果：B，C，A遍历的足迹：沿途经过各结点的“右部”·第四种方法：逆先序遍历：根，右，左A，C，B·第五种方法：逆中序遍历：右，根，左C，A，B·第六种方法：逆后序遍历：右，左，根C，B，A·第七种方法：按层次遍历：从上（根）到下逐层进行，自左至右诸个结点进行。遍历的结果：A，B，C例如：对下列二叉树，分别用四种方法遍历○A○B○C○D○E○F○G1.先序遍历的结果：A，B，D，F，C，E，G观察：A（根）B，D，F（根的左子树）C，E，G（根的右子树）2.中序遍历的结果：B，F，D，A，E，G，C观察：B，F，D（根的左子树）A（根）E，G，C（根的右子树）3.后序遍历的结果：F，D，B，G，E，C，A观察：F，D，B（根的左子树）G