树的基础知识

1树1.1树1.2二叉树1.3二叉树的遍历1.4线索二叉树1.5树和森林1.1树树的定义：树：T是n个结点构成的有限集合(n0)，其中有一个结点叫根，其余结点可划分为m个互不相交的子集T1，T2，……，Tm(m≥0)，并且这m个子集本身又构成树，称为T的子树。注意：这里没给出空树的概念。从树的定义可以看出，树的逻辑结构：（1）树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。（2）树中所有结点可以有零个或多个后继结点。1.1树树的表示形式：图形表示法ABDEFGIHC嵌套集合表示法HIEDFBGCA凹入表表示法ABCDEFGHI广义表表示法(A(B(D,E(H,I),F),C(G)))1.1树树的有关概念：1、孩子结点、双亲结点(父结点)：某结点的子树的根为该结点的孩子结点，而该结点为其孩子结点的双亲结点。兄弟结点：同一结点的孩子为兄弟结点。可延伸到祖先结点和后代结点。2、一个结点的度：该结点的直接后继结点(孩子)的个数。树的度：树中最大的结点度。3、叶子结点(终结点)：结点度为0。分支结点：结点度不为0。根结点：无直接前驱结点。1.1树树的有关概念：5、森林：多棵树。4、一个结点的层次：根为1，其余为父结点的层次数加1。树的深度：最大的结点层次数。6、有序树：树中各兄弟结点之间的排列次序是有关的。无序树：树中各兄弟结点之间的排列次序是无关的。1.1树树的基本运算：1、初始化树initial_tree(T)：建立树的初始结构。2、插入子树insert_tree(T,S)：将以S为根的子树作为T的第一个子树插入到树中。3、插入兄弟结点insert_sigling(T,S)：将以S为根的树作为T的兄弟子树插入到树中。4、查询根结点rootof(T)：查询结点T所在树的根结点。5、查询父结点fatherof(T)：查询结点T的父结点。6、查询孩子结点childof(T)：查询结点T的所有或某个孩子结点。7、查询兄弟结点siblingof(T)：查询结点T的所有或某个兄弟结点。1.2二叉树1.2.1二叉树的基本概念二叉树T是n个结点的有限集合，其中n≥0,当n=0时，为空树，否则，其中有一个结点为根结点，其余结点划分为两个互不相交的子集TL、TR，并且TL、TR分别构成叫作左、右子树的二叉树。（即树中结点的最大度为2，每个结点的孩子有左、右之分）。ABDEFGIHC结点A的左子树结点A的右子树1.2二叉树1.2.1二叉树的基本概念二叉树的五种不同形态：空树Ø单结点树右子树为空左子树为空左、右子树均不空1.2二叉树1.2.1二叉树的基本概念：满二叉树：每层都有最大数目结点的二叉树。满二叉树：每层都有最大数目结点的二叉树。完全二叉树：在满二叉树的最下层从右向左连续地删除若干个结点所得到的二叉树。（满二叉树是完全二叉树的一个特例）ADHIEBJKCLFMGON满二叉树ADHIEBJKCLFMG完全二叉树1.2二叉树1.2.2二叉树的性质性质1：在二叉树的第i层上的结点个数≤2i-1（i0）。性质2：深度为k的二叉树的结点个数≤2k-1（k0）。性质3：对任一棵非空的二叉树T，如果其叶子数为n0，度为2的结点数为n2，则有：n0=n2+1。性质4：有n个结点的完全二叉树(n0)的深度为log2n+1。性质5：在编号的完全二叉树(根结点编号为1，顺序按从上到下、从左到右进行编号)中，各结点编号之间的关系为：i结点若有左孩子则其编号为2i，若有右孩子则其编号为2i+1，若有父结点则其编号为i/2。证明1.2二叉树性质1证明：用数学归纳法证明。性质2证明：结点个数n≤20+21+22+┅+2k-1=2k-1。性质3证明：设T的总结点数为n，度为1的结点数为n1，则T的结点数满足关系式：n=n0+n1+n2(a)从T的分支数来看：在这n个结点中，除根以外，每个结点有一个分支进入，因此其总分支数为n-1。而这些分支仅从度为1和2的结点发出，则有：n-1=n1+2n2(b)由(a)和(b)得：n0=n2+1性质4证明：设树深为k，则结点数满足：2k-1-1n≤2k-1；2k-1≤n2k；k-1≤log2nk；k=log2n+1。返回1.2二叉树1.2.3二叉树的存储结构1、顺序存储结构要能存储结点值并能体现结点间的关系，而结点间的关系可用完全二叉树的编号来表示，即要先向二叉树添加一些虚结点形成完全二叉树，如此可用数组存放结点的值，而其关系用下标来体现。ABCD存储状态如下：ABC∧∧Ddata：下标：0123456例如：1.2二叉树1.2.3二叉树的存储结构2、二叉链表存储结构链表的每个结点应包含存储结点的值(data)及指向左、右孩子的指针(lchild、rchild)，结构如下：lchildrchilddata左孩子右孩子1.2二叉树1.2.3二叉树的存储结构2、二叉链表存储结构例如：二叉链表ABCD二叉树Bnode*T;A∧∧B∧C∧∧DT1.3二叉树的遍历遍历二叉树是指按某种次序访问二叉树中每个结点一次且仅一次。链表的遍历的次序有如下几种：(L左子树，R右子树)先左后右先右后左先根序：TLRTRL中根序：LTRRTL后根序：LRTRLT1.3二叉树的遍历1.3.1遍历算法的实现1、先根序遍历（TLR）若二叉树T不空，则(1)访问T的根结点；(2)先序遍历T的左子树；(3)先序遍历T的右子树。2、中根序遍历（LTR）若二叉树T不空，则(1)中序遍历T的左子树；(2)访问T的根结点；(3)中序遍历T的右子树。3、后根序遍历（LRT）若二叉树T不空，则(1)后序遍历T的左子树；(2)后序遍历T的右子树；(3)访问T的根结点。1.3二叉树的遍历1.3.1遍历算法的实现例1.1已知二叉树的先序和中序序列如下，试构造出相应的二叉树。先序：ABCDEFGHIJ中序：CDBFEAIHGJ分析：先序序列的第一个节点是根节点，中序序列根结点处于左右子树的中序序列之间。（注意：二叉树的先序和后序序列不能唯一确定一棵二叉树，但由先序和中序或后序和中序序列能唯一确定一棵二叉树）1.3二叉树的遍历1.3.2二叉树遍历算法的应用例1.2设计算法按中序次序输出二叉树Ｔ中度为2的结点的值。分析：可按中序遍历的算法，但是仅输出度为2的结点(即结点的左、右孩子均不为空)，所以只要将中序遍历算法中的访问结点操作改为有条件的输出结点得知即可。1.3二叉树的遍历1.3.2二叉树遍历算法的应用例1.3设计算法求二叉树Ｔ的结点数。分析：由于二叉树的遍历算法对树T中每个结点都会执行一次且仅执行一次访问结点的操作，为此，可将某一遍历算法中的访问结点的操作改为计数操作，即将该结点的数目１累加到一个全局变量ｎ中。1.3二叉树的遍历1.3.2二叉树遍历算法的应用例1.4设计算法求解给定二叉树Ｔ的高度。分析：（1）若T为空时，则其高度为0，求解结束。（2）否则，若T不为空，其高度应是其左、右子树高度的最大值再加1，假设其左、右子树的高度能求解出来，则算法实现。而其左、右子树高度的求解又可通过递归调用本算法来完成。例1.3设计算法求二叉树Ｔ的结点数。1.3二叉树的遍历1.3.2二叉树遍历算法的应用在算法较复杂时，算法设计的步骤：1、要明确所要编写的算法的功能描述（包括所涉及的各参数或变量的含义）——这在递归算法中尤其要注意。2、在此基础上按如下步骤讨论算法的实现：①如果T为空，则按预定功能实现对空树的操作，以满足功能要求（包括对相应参数，变量的操作）。②否则，假设算法对T的左右子树都能分别实现预定功能，在此基础上，通过按预定要求适当调用对左右子树的算法的功能，及对当前结点的操作实现对整个二叉树的功能（包括对各变量、参数的操作）。1.4线索二叉树1.4.1线索二叉树结构把二叉链表中的n+1个空指针域改为指向其在某一遍历下的前驱和后继（空的左指针域指向其前驱，空的右指针域指向其后继），则这种指针称为线索，所得的二叉树则为线索二叉树，将二叉树转变成线索二叉树的过程被称为线索化。为了保留结点在某种遍历序列中直接前驱和直接后继的位置信息，可以利用二叉树的二叉链表存储结构中的那些空指针域来指示。1.4线索二叉树1.4.1线索二叉树结构即：ltag=0：lchild指示该结点的左孩子。ltag=1：lchild指示该结点的前驱。rtag=0：rchild指示该结点的右孩子。rtag=1：rchild指示该结点的后继。为了便于区分二叉链表中各结点的指针域是孩子指针还是线索，可在每个结点中增加两个区分标志ltag和rtag，约定其值为1时是线索，值为0时是孩子指针。ltaglchilddatarchildrtag左孩子或前驱结点右孩子或后继结点1.4线索二叉树1.4.1线索二叉树结构ABCDEFGHIJ(a)先序线索二叉树先序序列：ABCDEFGHIJABCDEFGHIJ(b)中序线索二叉树中序序列：CBEDFAHJIGABCDEFGHIJ(c)后序线索二叉树后序序列：CEFDBJIHGA线索二叉树示例：1.4线索二叉树1.4.1线索二叉树结构先序线索二叉树链表结构示例：A00B00G00D00C11E11F11H10I01J11NULLT1.4线索二叉树1.4.2线索二叉树中前驱、后继的求解（1）若*P有左孩子(即P-ltag为0)，则其左子树PL中的第一个元素就是*P的后继，而PL中的先序序列的第一个结点即是其根结点，即P的左孩子(指针为P-lchild)。1、先序线索二叉树中求解后继（2）否则，若*P有右孩子，则其右孩子就是其后继，其指针为P-rchild。按先序遍历，以*P为根的子树的遍历次序是*P、PL、PR，由此顺序可得：（3）否则，P-rchild即是后继线索。1.4线索二叉树1.4.2线索二叉树中前驱、后继的求解（1）若*P有右孩子(即P-rtag为0)，则其右子树PR中的第一个元素就是*P的后继，而PR中的第一个结点即是在以PR为根的子树中的最左下的第一个没有左孩子的结点。2、中序线索二叉树中求解后继（2）否则，若*P无右孩子，则P-rchild即是后继线索。按中序遍历，以*P为根的子树的遍历次序是PL、*P、PR，由此顺序可得：t1t2t3t4*PPR1.5树和森林1.5.1树的存储结构1、双亲表示法树中的每个结点都有唯一的一个双亲结点，根据这一特性，可用一组连续的存储空间（一维数组）存储树中的各个结点，数组中的一个元素表示树中的一个结点，数组元素为结构体类型，其中包括结点本身的信息data以及结点的双亲结点在数组中的序号parent。类型定义：structtnode{datatypedata;intparent;};structtnodetreelist[MAXNUM];1.5树和森林1.5.1树的存储结构示例：ABFEDCGIHJKA-10B01C02D03E14F15G16H27I28J39K310下标dataparent1.5树和森林1.5.1树的存储结构2、孩子链表表示法其主体是一个与结点个数一样大小的一维数组，数组元素由两个域组成，一个用来存放结点信息info，另一个是指针firstchild，指向由该结点孩子组成的单链表的首位置。单链表的结点也由两个域组成，一个存放孩子结点在一维数组中的序号data，另一个是指针域next，指向下一个孩子。链表结点类型定义：typedefstructnode{intdata;structnode*next;}listnode;1.5树和森林1.5.1树的存储结构2、孩子链表表示法数组元素类型定义：typedefstruct{datatypeinfo;structnode*firstchild;}arrelemnt;定义数组：arrelemnttree[MAXNUM];1.5树和森林1.5.1树的存储结构示例：A0B1C2D3E4F^5G^6H^7I^8J^9K^10下标infofirstchild123^4576^8^9^10^ABFEDCGIHJK1.5树和森林1.5.1树的存储结构3