实现二叉排序树的前中后序遍历

二叉排序树定义

二叉排序树（Binary Sort Tree），也称为二叉查找树（Binary Search Tree, BST）或有序二叉树，是一种特殊的二叉树数据结构。以下是二叉排序树的一些核心概念：
一个二叉排序树或者是一棵空树，或者是具有以下性质的二叉树：

• 右子树上所有结点的值均大于它的根结点的值
  
• 左子树上所有结点的值均小于它的根结点的值
  
• 左右子树也分别为二叉排序树
  
• 不存在键值相等的节点
  

代码实现

1. #include <stdio.h>
2. #include <stdbool.h>
3. #include <stdlib.h>
5. typedef int DataType_t;
6. typedef struct BSTreeNode
7. {
8.         DataType_t                         Keyval;
9.         struct BSTreeNode *lchild;
10.         struct BSTreeNode *rchild;
12. }BSTNode_t;
15. BSTNode_t* BSTree_Create(DataType_t KeyVal)
16. {
17.         BSTNode_t *root = (BSTNode_t *)calloc(1,sizeof(BSTNode_t));
18.         if(root == NULL){
19.                 perror("Calloc memory for the root is failed!\n");
20.                 exit(-1);
21.         }
22.         root->lchild = NULL;
23.         root->rchild = NULL;
24.         root->Keyval = KeyVal;
25.         return root;
26. }
29. BSTNode_t* BSTree_NewNode(DataType_t KeyVal)
30. {
31.         BSTNode_t *New = (BSTNode_t *)calloc(1,sizeof(BSTNode_t));
32.         if(New == NULL){
33.                 perror("Calloc memory for the New is failed!\n");
34.                 return NULL;
35.         }
36.         New->lchild = NULL;
37.         New->rchild = NULL;
38.         New->Keyval   = KeyVal;
39.         return New;
40. }
43. bool BSTree_InsertNode(BSTNode_t* root, DataType_t KeyVal)
44. {
45.     if (root == NULL) {
46.         printf("Error: root is NULL, cannot insert %d\n", KeyVal);
47.         return false;
48.     }
50.     BSTNode_t *New = BSTree_NewNode(KeyVal);
51.     if (New == NULL) {
52.         printf("Create NewNode Error\n");
53.         return false;
54.     }
56.     BSTNode_t *Proot = root;
57.     while (Proot != NULL) {
58.         if (KeyVal == Proot->Keyval) {
59.             printf("Can not Insert, duplicate value: %d\n", KeyVal);
60.             free(New); // 避免内存泄漏
61.             return false;
62.         }
63.         else if (KeyVal < Proot->Keyval) {
64.             if (Proot->lchild == NULL) {
65.                 Proot->lchild = New;
66.                 return true;
67.             }
68.             Proot = Proot->lchild;
69.         }
70.         else {
71.             if (Proot->rchild == NULL) {
72.                 Proot->rchild = New;
73.                 return true;
74.             }
75.             Proot = Proot->rchild; //
76.         }
77.     }
79.     return true; //
80. }
82. //前序遍历
83. bool BSTree_PreOrder(BSTNode_t* root)
84. {
85.         if(root == NULL)
86.         {
87.                 return false;
88.         }
90.         printf("KeyVal = %d\n",root->Keyval);
91.         BSTree_PreOrder(root->lchild);
92.         BSTree_PreOrder(root->rchild);
94.         return true;
95. }
96. //中序遍历
97. bool BSTree_InOrder(BSTNode_t* root)
98. {
99.         if(root == NULL)
100.         {
101.                 return false;
102.         }
103.         BSTree_InOrder(root->lchild);
104.         printf("KeyVal = %d\n",root->Keyval);
105.         BSTree_InOrder(root->rchild);
106.         return true;
107. }
108. //后序遍历
109. bool BSTree_PostOrder(BSTNode_t* root)
110. {
111.         if(root == NULL)
112.         {
113.                 return false;
114.         }
115.         BSTree_PostOrder(root->lchild);
116.         BSTree_PostOrder(root->rchild);
117.         printf("KeyVal = %d\n",root->Keyval);
118.         return true;
119. }
121. int main()
122. {
123.     // --- 1. 测试：创建根节点 ---
124.     printf("1. 创建根节点...\n");
125.     BSTNode_t* root = BSTree_Create(50);
126.     if (root) {
127.         printf("成功创建根节点，值为: %d\n", root->Keyval);
128.     }
130.     // --- 2. 测试：插入多个节点 ---
131.     printf("\n2. 插入其他节点...\n");
132.     int values[] = {30, 70, 20, 40, 60, 80, 35, 45};
133.     int n = sizeof(values) / sizeof(values[0]);
135.     for (int i = 0; i < n; i++) {
136.         if (BSTree_InsertNode(root, values[i])) {
137.             printf("成功插入: %d\n", values[i]);
138.         }
139.     }
140.     // --- 3. 测试：重复插入（应失败）---
141.     printf("\n3. 测试重复插入...\n");
142.     BSTree_InsertNode(root, 40);  // 已存在
143.     BSTree_InsertNode(root, 50);  // 根节点已存在
145.     // --- 4. 测试：遍历操作 ---
146.     printf("\n4. 遍历测试...\n");
148.     printf("\n=== 前序遍历 (Pre-order) ===\n");
149.     BSTree_PreOrder(root);
151.     printf("\n=== 中序遍历 (In-order) - 应升序输出 ===\n");
152.     BSTree_InOrder(root);
154.     printf("\n=== 后序遍历 (Post-order) ===\n");
155.     BSTree_PostOrder(root);
157.         printf("\n7. 测试插入到 NULL 树（应失败）...\n");
158.     BSTNode_t* emptyTree = NULL;
159.     bool result = BSTree_InsertNode(emptyTree, 100);
160.     if (!result) {
161.         printf("正确：无法向 NULL 树插入节点。\n");
162.     }
163.     printf("\n所有测试完成\n");
164.     return 0;
165. }

复制代码

根节点的值是50，主函数中依次插入节点：30, 70, 20, 40, 60, 80, 35, 45，所以这棵树的图像长这个样子

运行结果

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！