大话数据结构-6.5 二叉树的定义 163- 高飞网

6.5 二叉树的定义 163

2016-12-23 22:02:51.0

6.5 二叉树的定义

二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两根互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

6.5.1 二叉树的特点

    二叉树的特点:

  1. 每个结点最多有两棵子树,所以二叉树不存在度大于2的结点。
  2. 左子树和右子树是有顺序的,次序不能任意颠倒。
  3. 即使树中某结点只有一棵子树,也要区分它是左子树还是右子树。

    二叉树的五团体客户基本形态:

  1. 空二叉树
  2. 只有一个根结点
  3. 根结点只有左子树
  4. 根结点只有右子树
  5. 根结点既有左子树又有右子树

6.5.2 特殊二叉树

    1. 斜树

    所有的结点都只有左子树的叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

    2. 满二叉树

    在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。

    满二叉树的特点:

  1. 叶子只能出现在最下一层。
  2. 非叶子结点的度一定是2.
  3. 在同样深度的二叉树中,满二叉树的结点个数最多。
    3. 完全二叉树

    对一棵具有n个结点的二叉树按层序编号,如果编号为i(1<=i<=n)的结点与同样深度的满二叉树编号为i的结点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树。如下图:

    完全二叉树的特点:

  1. 叶子结点只能出现在最下两层。
  2. 最下层的叶子一定集中在左部连续的位置。
  3. 倒数二层,若有叶子结点,一定都在右部连续位置。
  4. 如果结点度为1,该结点只有左孩子,即不存在只有右子树的情况。
  5. 同样结点数的二叉树,完全二叉树的深度最小。

6.6 二叉树的性质

6.6.1 二叉树性质1

    性质1:在二叉树的第i层上至多有2i-1个结点(i>=1)。

6.6.2 二叉树性质2

    性质2:深度为k的二叉树,至多有2k-1个结点(k>=1)。

6.6.3 二叉树性质3

    性质3:对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1.

    推导:设度为1的结点数为n1,结点总数为n,则n=n0+n1+n2。换一个角度,再数一数它的连接线数。由于根结点只有分支出去,没有分支进入,其他所有结点都有一个分支线进入,所以分支总数=n-1,另外,分支总数=2n2+n1。从而得出:

    n-1=n1+2n2  ==> n0+n1+n2 -1 = n1+2n2 ==>n0=n2+1

6.6.4 二叉树性质4

    性质4:具有n个结点的完全二叉树的深度为 [log2n]+1 ([x]表示不大于x的最大整数)。

6.6.5 二叉树性质5

    性质5:如果对一棵n个结点的完全二叉树,(其深度为[log2n]+1)的结点按层序编号,对任一结点i,有:

  1. 如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则其双亲结点是[i/2]。
  2. 如果2i>n,则结点i无左孩子;否则其左孩子是结点2i
  3. 如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1.

6.7 二叉树的存储结构

6.7.1 二叉树的顺序存储结构

    二叉树的顺序存储结构用一给数组存储二叉树中的结点,并且结点的存储位置,也就是数组的下标要能体现结点之间的逻辑关系,比如双亲与孩子的关系,左右兄弟的关系。

    对于完全二叉树,由于其位置与满二叉树完全相同,因此可以用一给数组方便地表示出来


    当然如果层序编号不能反映逻辑关系,但是可以将其按完全二叉树编号,只不过,把不存在的结点设置为“^”而已。

6.7.2 二叉链表

    二叉树的每个结点最多有两个孩子,所以为它设计一个数据域和两个指针域。

/* 二叉树的二叉链表结点结构定义 */
typedef struct BiiNode/* 结点结构 */
{
	TElemType data;	/* 结点数据 */
	struct BiTNode *lchild,*rchild;/*左右孩子指针*/
}BiTNode,*BiTree;


上一篇:第6章 树 149
下一篇:6.8 遍历二叉树 174