這篇文章主要介紹了使用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. }