使用C语言构建基本的二叉树数据结构

这篇文章主要介绍了使用C语言使用C语言构建基本的二叉树数据结构,包括根据前序序列和中序序列构建二叉树的方法,需要的朋友可以参考下

二叉树结构常用的一些初始化代码

1. #include 
2. #include 
3.  
4. typedef struct Node{ 
5. int data; 
6. Node *leftchild; 
7. Node *rightchild; 
8. }Node; 
9.  
10.  
11. /* 
12. 初始化一棵二叉树排序树。 
13. */ 
14. void InitBinaryTree(Node**root,int elem) 
15. { 
16. *root=(Node*)malloc(sizeof(Node)); 
17. if(!(*root)) 
18. { 
19. printf("Memory allocation for root failed./n"); 
20. return; 
21. } 
22. (*root)->data=elem; 
23. (*root)->leftchild=NULL; 
24. (*root)->rightchild=NULL; 
25. } 
26.  
27. /* 
28. 向二叉树排序树中插入节点。 
29. */ 
30. void InsertNode(Node *root,int elem) 
31. { 
32. Node *newnode=NULL; 
33. Node *p=root,*last_p=NULL; 
34.  
35. newnode=(Node*)malloc(sizeof(Node)); 
36. if(!newnode) 
37. { 
38. printf("Memory allocation for newnode failed./n"); 
39. return; 
40. } 
41. newnode->data=elem; 
42. newnode->leftchild=NULL; 
43. newnode->rightchild=NULL; 
44.  
45. while(NULL!=p) 
46. { 
47. last_p=p; 
48. if(newnode->datadata) 
49. { 
50. p=p->leftchild; 
51. } 
52. else if(newnode->data>p->data) 
53. { 
54. p=p->rightchild; 
55. } 
56. else 
57. { 
58. printf("Node to be inserted has existed./n"); 
59. free(newnode); 
60. return; 
61. } 
62. } 
63. p=last_p; 
64. if(newnode->datadata) 
65. { 
66. p->leftchild=newnode; 
67. } 
68. else 
69. { 
70. p->rightchild=newnode; 
71. } 
72. } 
73.  
74. /* 
75. 创建一棵二叉树排序树。 
76. */ 
77. void CreatBinarySearchTree(Node **root,int data[],int num) 
78. { 
79. int i; 
80.  
81. for(i=0;i 
82. { 
83. if(NULL==*root) 
84. { 
85. InitBinaryTree(root,data[i]); 
86. } 
87. else 
88. { 
89. InsertNode(*root,data[i]); 
90. } 
91. } 
92. } 

根据前序序列、中序序列构建二叉树

函数定义

1. bt rebuildTree(char *pre, char *in, int len);  

参数：

* pre：前序遍历结果的字符串数组

* in：中序遍历结果的字符串数组

len : 树的长度

例如：

前序遍历结果: a b c d e f g h

中序遍历结果: c b e d f a g h

算法思想

递归思想，递归的终止条件是树的长度len == 0

在中序遍历的数组中找到前序数组的第一个字符，记录在中序数组中的位置index.如果找不到，说明前序遍历数组和中序遍历数组有问题，提示错误信息，退出程序即可;找到index后，新建一个二叉树节点t，t->item = *pre,然后递归的求t的左孩子和有孩子

递归的左孩子：void rebuildTree(pre + 1, in, index)

递归的右孩子：void rebuildTree(pre + (index + 1), in + (index + 1), len - (index + 1))

实现代码(c语言版)

1. /**  
2. * Description:根据前序和中序构建二叉树  
3. */ 
4. bt rebuildTree(char *pre, char *in, int len)  
5. {  
6. bt t;  
7. if(len <= 0)  
8. {  
9. //递归终止  
10. t = NULL;  
11. }else 
12. {  
13. //递归主体  
14. int index = 0;  
15.  
16. while(index < len && *(pre) != *(in + index))  
17. {  
18. index ++;  
19. }  
20.  
21. if(index >= len)  
22. {  
23. printf("前序遍历或者中序遍历数组有问题!/n");  
24. exit(-1);  
25. }  
26.  
27. t = (struct bintree *)malloc(sizeof(struct bintree));  
28. t->item = *pre;  
29. t->lchild = rebuildTree(pre + 1, in, index);  
30. t->rchild = rebuildTree(pre + (index + 1), in + (index + 1), len - (index + 1));  
31. }  
32. return t;  
33. }  

根据中序序列、后序序列构建二叉树

函数定义

1. /**  
2. * 中序、后序序列构建二叉树  
3. */ 
4. btree* rebuildTree(char *order, char *post, int len);  

算法思想

中序序列：C、B、E、D、F、A、H、G、J、I

后序序列：C、E、F、D、B、H、J、I、G、A

递归思路：

根据后序遍历的特点，知道后序遍历最后一个节点为根节点，即为A

观察中序遍历，A左侧CBEDF为A左子树节点，A后侧HGJI为A右子树节点

然后递归的构建A的左子树和后子树

实现代码(c代码)

1. /**  
2. * 根据中序和后序序列构建二叉树  
3. * (ps:昨晚参加阿里笔试，等到最后说可以免笔试直接面试，今天估计还是要根据学校筛选，哈哈，为了这点  
4. * 也得参加阿里笔试，不能让自己的学校受到鄙视)  
5. */ 
6.  
7. #include <stdio.h>  
8. #include <stdlib.h>  
9. #include <string.h>  
10.  
11. int n;  
12.  
13. typedef struct btree {  
14. struct btree *lchild;  
15. struct btree *rchild;  
16. char data;  
17. } btree;  
18.  
19. /**  
20. * 中序、后序序列构建二叉树  
21. */ 
22. btree* rebuildTree(char *order, char *post, int len)  
23. {  
24. btree *t;  
25.  
26. if (len <= 0) {  
27. return NULL;  
28. } else {  
29. int index = 0;  
30.  
31. while (index < len && *(post + len - 1) != *(order + index)) {  
32. index ++;  
33. }  
34.  
35. t = (btree *)malloc(sizeof(btree));  
36. t->data = *(order + index);  
37. t->lchild = rebuildTree(order, post, index);  
38. t->rchild = rebuildTree(order + index + 1, post + index, len - (index + 1));  
39. }  
40.  
41. return t;  
42. }  
43.  
44. /**  
45. * 前序遍历二叉树  
46. */ 
47. void preTraverse(btree *t)  
48. {  
49. if (t) {  
50. printf("%c ", t->data);  
51. preTraverse(t->lchild);  
52. preTraverse(t->rchild);  
53. }  
54. }  
55.  
56. int main(void)  
57. {  
58. int i;  
59. char *post, *order;  
60. btree *t;  
61.  
62. while (scanf("%d", &n) != EOF) {  
63. post = (char *)malloc(n);  
64. order = (char *)malloc(n);  
65.  
66. getchar();  
67. for (i = 0; i < n; i ++)  
68. scanf("%c", order + i);  
69.  
70. getchar();  
71. for (i = 0; i < n; i ++)  
72. scanf("%c", post + i);  
73.  
74. t = rebuildTree(order, post, n);  
75.  
76. preTraverse(t);  
77. printf("/n");  
78.  
79. free(post);  
80. free(order);  
81.  
82. }  
83.  
84. return 0;  
85. }