二叉树基本概念及表示法

beyes

二叉树是一种树状结构，一颗二叉树的 “结点” (Node)，最多只能拥有 2个子结点，也就是度小于或等于 2 。

二叉树的基本定义：

二叉树结点个数有限，而且可以没有结点。
一颗二叉树的树根下可以分为两个子树，分别称为 “左子树” (Left Subtree) 和 "右子树"(Right Subtree)。

形状如下图所示：

上图，是以 A 为根结点的二叉树，包含 B 根结点的左子树和 C 为根结点的右子树，如下图所示：


二叉树可以分为左子树和右子树，下图中有两棵树，虽然它们有着相同的树状结构，但是这两棵是不同的二叉树：

上图中，左边树没有右子树，右边树没有左子树。如果二叉树的高度是 h ，而且二叉树的结点数是 2[sup]h[/sup] - 1 ，如果符号此条件的树，则称为 满二叉树 (Full Binary Tree)，如下图所示：

上图中，二叉树的高度是 3 ，结点数是 7 ，即 2[sup]3[/sup] - 1 。这是一颗满二叉树。另外还有一种二叉树，如果它的结点不是叶结点，就一定拥有两个子结点，而且结点数的个数不足 2[sup]h[/sup] - 1 ，其中 h 表示高度。这样的树称为 "完全二叉树“ (Complete Binary Tree)，如下图所示：

定义：若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。

beyes

二叉树的结点数据表示法共有 3 种方法，如下：

二叉树数组表示法
二叉树结构数组表示法
二叉树链表结构表示法

前两种方法是内存静态分配的表示法，第 3 种方法是使用基于链表结构的动态内存分配。

beyes

创建二叉树结点数据的策略有三个：

将第一个要创建的元素插入称为根结点。
将元素值与结点值比较，如果元素值大于结点值，将此元素送往结点的右结点，如果右子结点并不是空，需要重复比较，否则创建结点将元素值插入。
如果元素值小于结点值，将此元素送往结点的左子结点，如果左子结点不是空的，需要重复比较，否则创建结点将元素插入。

如按照此策略，给二叉树输入数据的顺序是 5， 6， 4， 8， 2， 3， 7， 1， 9 ，树状如下图所示：


代码：

#include <stdio.h>

void createbtree (int *btree, int *data, int len)
{
     int level;    /*树的层数*/
     int i;

     btree [1] = data [1];    /*创建根结点*/
     for (i = 2; i <= len; i++) {    /*循环创建其它结点*/
         
         level = 1;   
                 
         while ( btree [level] != 0) {            /*是否有子树*/
             if (data [i] > btree [level])       /*是左或右子树*/
                 level = level * 2 + 1;        /*右子树*/
             else
                 level = level * 2;        /*左子树*/
         }
         btree [level] = data [i];
     }
}


int main()
{
     int btree [16];        /*二叉树数组*/
     /*二叉树结点数据*/
     int data [10] = {0, 5, 6, 4, 8, 2, 3, 7, 1, 9};
     int i;

     for (i = 1; i < 16; i++)
         btree [i] = 0;        /*清除二叉树数组*/
     createbtree (btree, data, 9);
     
     for (i = 1; i < 16; i++)
         printf ("%2d: [%d] \\n", i, btree[i]);
     
     return (0);
}

运行与输出：

beyes@linux-beyes:~/C/structer/BinaryTree> ./array_tree.exe
1: [5]
2: [4]
3: [6]
4: [2]
5: [0]
6: [0]
7: [8]
8: [1]
9: [3]
10: [0]
11: [0]
12: [0]
13: [0]
14: [7]
15: [9]

beyes

二叉树的特性是每个结点至多拥有两个子结点，所以可以声明结构存储树的结点，这个结点至少拥有 3 个数据项，数据项存放结点的数据，另外两个项存放指向左子树和右子树的数据索引：

left

data

right

二叉树使用的结构声明如下：

struct tree {
     int data;
     int left;
     int right;
};

上面的声明，left 表示左结点，如果 left = -1 ，那么表示此结点没有左子结点，如果不是 -1，则表示有左子结点，其值表示在这个子结点上的数据所在原数组中的索引。比如 left = 3，data = 5，这个 data 值是取自一个数组，而 left = 3 表示这个 data 值在它原来所在的数组中的索引为 3 。right 值同理。

下面是测试程序：

#include <stdio.h>

struct tree {        /*树的结构声明*/
     int data;    /*结点数据*/
     int left;    /*指向左子树的位置*/
     int right;    /*指向右子树的位置*/
};

typedef struct tree treenode;        /*树的结构新类型*/
treenode btree[15];            /*声明树的结构数组*/

/*---------------------*/
/*创建二叉树           */
/*---------------------*/
void createbtree (int *data, int len)
{
     int level;            /*树的层数*/
     int pos;            /*-1是左树,1是右树*/
     int i;               

     btree[0].data = data[0];    /*创建树的根结点*/
     
     for (i = 1; i < len; i++) {    /*循环创建其它结点*/
         btree[i].data = data[i];
         level = 0;
         pos = 0;

         while (pos == 0) {
                     /*比较是左或右子树*/
             if (data[i] > btree[level].data)
                     /*右树是否有下一层树*/
                 if (btree[level].right != -1)
                     level = btree[level].right;
                 else
                     pos = -1;    /*是右树*/
            
             else
                 if (btree[level].left != -1)
                     level = btree[level].left;
                      else
                     pos = 1;        /*是左树*/
         }
         if (pos == 1)        /*创建结点左右位置*/
            btree[level].left = i;        /*连接左子树*/
         else
            btree[level].right = i;        /*连接右子数*/
     }
}

/*-------------------------------*/
/*主程序:创建结构数组的二叉树结构*/
/*-------------------------------*/
int main()
{
     /*二叉树结点数据*/
     int data[10] = {5, 6, 4, 8, 2, 3, 7, 1, 9};
     int i;

     for (i = 0; i < 15; i ++) {

         btree[i].data = 0;
         btree[i].left = -1;
         btree[i].right = -1;
         
     }

     createbtree(data, 9);
     printf (" 左       数据     右\\n");
     for (i = 0; i < 15; i++)
         if (btree[i].data != 0)
             printf ("%2d:[%2d]   [%2d]   [%2d]\\n", i, btree[i].left,
                 btree[i].data, btree[i].right);
     return (0);
}

运行与输出：
beyes@linux-beyes:~/C/structer/BinaryTree> ./struct_tree.exe
左       数据     右
0:[ 2]   [ 5]   [ 1]
1:[-1]   [ 6]   [ 3]
2:[ 4]   [ 4]   [-1]
3:[ 6]   [ 8]   [ 8]
4:[ 7]   [ 2]   [ 5]
5:[-1]   [ 3]   [-1]
6:[-1]   [ 7]   [-1]
7:[-1]   [ 1]   [-1]
8:[-1]   [ 9]   [-1]

说明，从 data[10] 这个数组中取出元素建立二叉树。建立二叉树的流程及规律是：
data[0] = 5，这个数据作为二叉树根结点的数据值。接着，取出 data[1] ，因为 data[1] = 6 ，它的值比 5 大，那么此值应放在根结点的右子树上。下一步还需检测右子树是否已经被其他数据占据，如果还没有，那么 pos = -1 ，说明并未有数据占据，那么就讲这个数据的索引号填入到 btree[0].right 中。如果取出的是 data[3] = 8，同样从根结点开始检测，8 比 5 大，那么继续检测 5 的右子树是否被占用(right != -1 表示已经被占用)，如果已被(6)占用，那么继续往下检测，发现 8 比 6 大且6的右子树没被占用，于是把 8 插到 6 的右子树上，同时把 8 所在 data 数组中的索引值赋予btree[1].rihgt。
左子树的情况同理可推。
建立完后的二叉树如下图所示：

这种表示法可以解决二叉树插入结点或删除结点时的大量数据移动的问题。因此二叉树的创建是靠字段 left 和 right 连接，上述操作只需改变这两个字段值即可。不过需要估计二叉树的结点个数却是这种表示法的一大问题，否则结点数一旦超过声明的结构数组长度，将会产生未知结果的错误。