第6章树和二叉树6.1知识点概述树(Tree)形结构是一种很重要的非线性结构，它反映了数据元素之间的层次关系和分支关系。在计算机科学中具有广泛的应用。1、树的定义树(Tree)是n(n±0)个数据元素的有限集合。当n=0时，称这棵树为空树。在一棵非空树T中：(1)有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。(2)若n〉l，除根结点之外的其余数据元素被分成m(m>0)个互不相交的集合T1,T2,…，Tm，其中每一个集合Ti(lWiWm)本身又是一棵树。树T1,T2,…，Tm称为这个根结点的子树。2、树的基本存储结构(1)双亲表示法由于树中的每一个结点都有一个唯一确定的双亲结点，所以我们可用一组连续的存储空间(即一维数组)存储树中的结点。每个结点有两个域：一个是data域，存放结点信息，另一个是parent域，用来存放双亲的位置(指针)。(2)孩子表示法将一个结点所有孩子链接成一个单链表形，而树中有若干个结点，故有若干个单链表，每个单链表有一个表头结点，所有表头结点用一个数组来描述这种方法通常是把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。(3)双亲孩子表示法双亲表示法是将双亲表示法和孩子表示法相结合的结果。其仍将各结点的孩子结点分别组成单链表，同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子结点链表的头指针之外，还增设一个域，存储该结点双亲结点在数组中的序号。(4)孩子兄弟表示法这种表示法又称为树的二叉表示法，或者二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟(右兄弟)结点。3、二叉树的定义二叉树(BinaryTree)是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。4、满二叉树定义：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。5、完全二叉树定义：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i(lWiWn)的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。6、二叉树的性质性质1一棵非空二叉树的第i层上最多有2i-l个结点（i±l）。性质2—棵深度为k的二叉树中，最多具有2k—1个结点。性质3对于一棵非空的二叉树，如果叶子结点数为nO，度数为2的结点数为n2,则有：n0=n2+1性质4具有n个结点的完全二叉树的深度k为[log2n]+1。性质5对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有：1）如果i〉1,则序号为i的结点的双亲结点的序号为i/2（“/”表示整除）；如果i=1,则序号为i的结点是根结点，无双亲结点。2）如果2iWn,则序号为i的结点的左孩子结点的序号为2i；如果2i>n，则序号为i的结点无左孩子。3）如果2i+1Wn,则序号为i的结点的右孩子结点的序号为2i+1；如果2i+1〉n,则序号为i的结点无右孩子。7、二叉树的存储结构顺序存储结构和链式存储结构。（1）顺序存储结构所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。（2）链式存储结构所谓二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链来指示着元素的逻辑关系。二叉树的链式存储结构通常有下面两种形式。1）二叉链表存储链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。2）三叉链表存储每个结点由四个域组成，data、lchild、rchild和parent其中，data、lchild以及rchild三个域的意义同二叉链表结构；parent域为指向该结点双亲结点的指针。这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是，相对于二叉链表存储结构而言，...
