@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 -1 -1 82 92 69 -1 -1 -1 5 -1 -1
中序、后序同理
（3）根据二叉树对应的“完全二叉树”序列来创建（设下标从0开始）
想象如上所示的二叉树嵌入到完全二叉树中（不存在的节点标记为-1），则从下标0~15，完全二叉树对应的序列是：
89 73 82 -1 -1 92 5 -1 -1 -1 -1 69 -1 -1 -1
把序列存入数组order[]中，若设树的根节点值为order[idx]，则其左子树根节点的值为order[idx*2 +1]，右子树的为order[idx*2 +2]
当然还有第四种也很常见，就是“由遍历序列创建二叉树 link(public)”，这个已经单独介绍过了，包括给定中序前序创建和给定中序后序创建两种情况。
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 void tree_print(link root, FILE *fd); 33 34 35 int main(void) 36 { 37 char cmd[CMD_LEN]; 38 int n, i, order[LEN]; 39 40 printf("there is three ways to create binary tree, including:\n"); 41 printf("[r] create binary tree by random\n"); 42 printf("[p] create binary tree by preorder(NULL node values -1)\n"); 43 printf("[c] create binary tree by complete binary tree order(NULL node values -1)\n"); 44 printf("[q] quit\n"); 45 printf("please choice: enter charactor ‘r‘ ‘p‘ or ‘c‘, or ‘q‘ to quit\n"); 46 while(1) { 47 scanf("%s", cmd); 48 switch(cmd[0]) { 49 case ‘r‘: 50 printf("create binary tree with n nodes by randmon, please assgin n:\n"); 51 scanf("%d", &n); 52 srand( (unsigned)time(NULL) ); 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 if (n <= 0) 91 return NULL; 92 if (n == 1) 93 return NODE(rand()%MOD, NULL, NULL); 94 95 link root = NODE(rand()%MOD, NULL, NULL); 96 int left_n = rand()%(n-1) + 1, right_n = (n-1) - left_n; 97 root->left = bt_create_by_random(left_n); 98 root->right = bt_create_by_random(right_n); 99 return root; 100 } 101 102 link bt_create_by_preorder(void) 103 { 104 int item; 105 106 scanf("%d", &item); 107 if (item == -1) //current root is NULL 108 return NULL; 109 link root = NODE(item, NULL, NULL); 110 root->left = bt_create_by_preorder(); 111 root->right = bt_create_by_preorder(); 112 return root; 113 } 114 115 116 link bt_create_by_complete_bt_order(int *order, int n, int idx) 117 { 118 if (order[idx] == -1 || idx >= n) 119 return NULL; 120 link root = NODE(order[idx], NULL, NULL); 121 root->left = bt_create_by_complete_bt_order(order, n, idx*2+1); 122 root->right = bt_create_by_complete_bt_order(order, n, idx*2+2); 123 return root; 124 } 125 126 void bt_show_by_tree(link root) 127 { 128 char cmd[CMD_LEN]; 129 130 sprintf(cmd, "rm -f ./tree_src.txt"); 131 system(cmd); 132 133 FILE *fd = fopen("./tree_src.txt", "a+"); 134 fprintf(fd, "\n\t\\tree"); 135 tree_print(root, fd); 136 fprintf(fd, "\n\n"); 137 fclose(fd); 138 139 sprintf(cmd, "cat ./tree_src.txt | ~/tree/tree"); 140 system(cmd); 141 } 142 143 void tree_print(link root, FILE *fd) 144 { 145 fprintf(fd, "("); 146 if (root != NULL) { 147 fprintf(fd, "%d", root->item); 148 tree_print(root->left, fd); 149 tree_print(root->right, fd); 150 } 151 fprintf(fd, ")"); 152 }
测试示范：
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