@Author: 张海拔
@Update: 2014-01-28
@Link: http://www.cnblogs.com/zhanghaiba/p/3535769.html
二叉树这种数据结构非常经典。研究二叉树之前必须得创建二叉树，这里简单介绍三种常见的创建二叉树的方式——
89
____|____
| |
73 82
_|__ ___|___
| | | |
92 5
_|__ _|__
| | | |
69
_|__
| |
（1）随机创建一棵二叉树
比如我们要随机生成含n个节点的二叉树，默认指定节点值的范围是[0, 100)
那么生成一个节点后，设随机生成的左子树包括节点数是left_n = random[0, n-1]，则right_n = (n-1) - left_n
这样递归下去，当n<=0返回空，n==1返回一个根节点
该算法生成的二叉树是比较“平衡”的（期望情况下左子树和右子树数目差不多），原因是生成深度很浅时比深度很深时范围大，相对不容易取到边界值。
如上所示的二叉树，创建过程中，打印left_n和right_n结果会是：
left_n=1 right_n = 4
left_n=2 right_n = 1
left_n=1 right_n = 0
（2）根据二叉树的前序、中序或后序序列（同时包含空节点的序列）来创建
如上所示的二叉树，包括空节点的前序序列表示为：89 73 # # 82 92 69 # # # 5 # #（空节点标记为#）
中序、后序同理
（3）根据二叉树对应的“完全二叉树”序列来创建（设下标从0开始）
想象如上所示的二叉树嵌入到完全二叉树中，则从下标0~15，完全二叉树对应的序列是：
89 73 82 # # 92 5 # # # # 69 # # #
把序列存入数组order[]中，若设树的根节点值为order[idx]，则其左子树根节点的值为order[idx*2 +1]，右子树的为order[idx*2 +2]
（4）由遍历序列创建二叉树 link(public)，这个已经单独介绍过了，包括给定中序前序创建和给定中序后序创建两种情况。
不过这种创建方式创建出来的二叉树有局限性：要求每个节点的“值”是不同的。
假如有两个节点“值”相同，比如完全二叉树的{1，1}和{1, #, 1}，可以创建两棵不同的树，但它们的前序中序序列是完全一样的。
1 /*
2 *Author: ZhangHaiba
3 *Date: 2014-1-28
4 *File: binary_tree.c
5 *
6 *a demo shows three ways to create binary tree
7 */
8 #include <stdio.h>
9 #include <stdlib.h>
10 #include <time.h>
11 #define MOD 100
12 #define LEN 1024
13 #define CMD_LEN 128
14
15 typedef struct node* link;
16 typedef struct node {
17 int item;
18 link left;
19 link right;
20 }node;
21
22 //public
23 link NODE(int item, link left, link right);
24 link bt_create_by_random(int n);
25 link bt_create_by_preorder(void);
26 //idx begin with 0
27 link bt_create_by_complete_bt_order(int *order, int order_len, int idx);
28 link bt_preorder(link root);
29 void bt_show_by_tree(link root);
30
31 //private
32 link bt_create_by_random_core(int n);
33 void tree_print(link root, FILE *fd);
34
35
36 int main(void)
37 {
38 char cmd[CMD_LEN];
39 int n, i, order[LEN];
40
41 printf("there is three ways to create binary tree, including:\n");
42 printf("[r] create binary tree by random\n");
43 printf("[p] create binary tree by preorder(NULL node values -1)\n");
44 printf("[c] create binary tree by complete binary tree order(NULL node values -1)\n");
45 printf("[q] quit\n");
46 printf("please choice: enter charactor 'r' 'p' or 'c', or 'q' to quit\n");
47 while(1) {
48 scanf("%s", cmd);
49 switch(cmd[0]) {
50 case 'r':
51 printf("create binary tree with n nodes by randmon, please assgin n:\n");
52 scanf("%d", &n);
53 link bt_tree_a = bt_create_by_random(n);
54 bt_show_by_tree(bt_tree_a);
55 break;
56 case 'p':
57 printf("please input preorder(NULL node values -1)\n");
58 link bt_tree_b = bt_create_by_preorder();
59 bt_show_by_tree(bt_tree_b);
60 break;
61 case 'c':
62 printf("to create complete binary tree order, assgin its length as:\n");
63 scanf("%d", &n);
64 printf("please input complete binary tree order(NULL node values -1)\n");
65 for (i = 0; i < n; ++i)
66 scanf("%d", order+i);
67 link bt_tree_c = bt_create_by_complete_bt_order(order, n, 0);
68 bt_show_by_tree(bt_tree_c);
69 break;
70 case 'q':
71 return 0;
72 default:
73 break;
74 }
75 }
76 return 0;
77 }
78
79 link NODE(int item, link left, link right)
80 {
81 link born = malloc( sizeof (node) );
82 born->item = item;
83 born->left = left;
84 born->right = right;
85 return born;
86 }
87
88 link bt_create_by_random(int n)
89 {
90 srand( (unsigned)time(NULL) );
91 return bt_create_by_random_core(n);
92 }
93
94 link bt_create_by_random_core(int n)
95 {
96 if (n <= 0)
97 return NULL;
98 if (n == 1)
99 return NODE(rand()%MOD, NULL, NULL);
100
101 link root = NODE(rand()%MOD, NULL, NULL);
102 int left_n = rand()%(n-1) + 1, right_n = (n-1) - left_n;
103 root->left = bt_create_by_random_core(left_n);
104 root->right = bt_create_by_random_core(right_n);
105 return root;
106 }
107
108 link bt_create_by_preorder(void)
109 {
110 int item;
111
112 scanf("%d", &item);
113 if (item == -1) //current root is NULL
114 return NULL;
115 link root = NODE(item, NULL, NULL);
116 root->left = bt_create_by_preorder();
117 root->right = bt_create_by_preorder();
118 return root;
119 }
120
121
122 link bt_create_by_complete_bt_order(int *order, int n, int idx)
123 {
124 if (order[idx] == -1 || idx >= n)
125 return NULL;
126 link root = NODE(order[idx], NULL, NULL);
127 root->left = bt_create_by_complete_bt_order(order, n, idx*2+1);
128 root->right = bt_create_by_complete_bt_order(order, n, idx*2+2);
129 return root;
130 }
131
132 void bt_show_by_tree(link root)
133 {
134 char cmd[CMD_LEN];
135
136 sprintf(cmd, "rm -f ./tree_src.txt");
137 system(cmd);
138
139 FILE *fd = fopen("./tree_src.txt", "a+");
140 fprintf(fd, "\n\t\\tree");
141 tree_print(root, fd);
142 fprintf(fd, "\n\n");
143 fclose(fd);
144
145 sprintf(cmd, "cat ./tree_src.txt | ~/tree/tree");
146 system(cmd);
147 }
148
149 void tree_print(link root, FILE *fd)
150 {
151 fprintf(fd, "(");
152 if (root != NULL) {
153 fprintf(fd, "%d", root->item);
154 tree_print(root->left, fd);
155 tree_print(root->right, fd);
156 }
157 fprintf(fd, ")");
158 }
测试示范：
ZhangHaiba-MacBook-Pro:code apple$ ./a.out
there is 3 way to create binary tree, including:
[r] create binary tree by random
[p] create binary tree by preorder(NULL node values -1)
[c] create binary tree by complete binary tree order(NULL node values -1)
[q] quit
please choice: enter charactor 'r' 'p' or 'c', or 'q' to quit
r
create binary tree with n nodes by randmon, please assgin n:
4
19
___|___
| |
61 49
_|__ _|__
| | | |
67
_|__
| |
r
create binary tree with n nodes by randmon, please assgin n:
10
33
_|__
| |
60
____|_____
| |
80 6
_|__ ___|___
| | | |
43 93 54
___|___ _|__ _|__
| | | | | |
67 31 40
_|__ _|__ _|__
| | | | | |
r
create binary tree with n nodes by randmon, please assgin n:
10
61
____|_____
| |
11 89
_|__ ___|___
| | | |
34 58
_|__ _|__
| | | |
50
___|___
| |
79 58
_|__ _|__
| | | |
81
_|__
| |
22
_|__
| |
r
create binary tree with n nodes by randmon, please assgin n:
10
38
____|_____
| |
38 8
_|__ ____|____
| | | |
54 14 62
_|__ _|__ ___|___
| | | | | |
3 68 9
_|__ _|__ _|__
| | | | | |
42
_|__
| |
p
please input preorder(NULL node values -1)
89 73 -1 -1 82 92 69 -1 -1 -1 5 -1 -1
89
____|____
| |
73 82
_|__ ___|___
| | | |
92 5
_|__ _|__
| | | |
69
_|__
| |
c
to create complete binary tree order, assgin its length as:
15
please input complete binary tree order(NULL node values -1)
89 73 82 -1 -1 92 5 -1 -1 -1 -1 69 -1 -1 -1
89
____|____
| |
73 82
_|__ ___|___
| | | |
92 5
_|__ _|__
| | | |
69
_|__
| |
q