实现二叉排序树的前中后序遍历
<h1 id="二叉排序树定义">二叉排序树定义</h1><p>二叉排序树（Binary Sort Tree），也称为二叉查找树（Binary Search Tree, BST）或有序二叉树，是一种特殊的二叉树数据结构。以下是二叉排序树的一些核心概念：</p>
<p>一个二叉排序树或者是一棵空树，或者是具有以下性质的二叉树：</p>
<ul>
<li>右子树上所有结点的值均大于它的根结点的值</li>
<li>左子树上所有结点的值均小于它的根结点的值</li>
<li>左右子树也分别为二叉排序树</li>
<li>不存在键值相等的节点</li>
</ul>
<h2 id="代码实现">代码实现</h2>
<pre><code class="language-c">#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int DataType_t;
typedef struct BSTreeNode
{
DataType_t Keyval;
struct BSTreeNode *lchild;
struct BSTreeNode *rchild;
}BSTNode_t;
BSTNode_t* BSTree_Create(DataType_t KeyVal)
{
BSTNode_t *root = (BSTNode_t *)calloc(1,sizeof(BSTNode_t));
if(root == NULL){
perror("Calloc memory for the root is failed!\n");
exit(-1);
}
root->lchild = NULL;
root->rchild = NULL;
root->Keyval = KeyVal;
return root;
}
BSTNode_t* BSTree_NewNode(DataType_t KeyVal)
{
BSTNode_t *New = (BSTNode_t *)calloc(1,sizeof(BSTNode_t));
if(New == NULL){
perror("Calloc memory for the New is failed!\n");
return NULL;
}
New->lchild = NULL;
New->rchild = NULL;
New->Keyval = KeyVal;
return New;
}
bool BSTree_InsertNode(BSTNode_t* root, DataType_t KeyVal)
{
if (root == NULL) {
printf("Error: root is NULL, cannot insert %d\n", KeyVal);
return false;
}
BSTNode_t *New = BSTree_NewNode(KeyVal);
if (New == NULL) {
printf("Create NewNode Error\n");
return false;
}
BSTNode_t *Proot = root;
while (Proot != NULL) {
if (KeyVal == Proot->Keyval) {
printf("Can not Insert, duplicate value: %d\n", KeyVal);
free(New); // 避免内存泄漏
return false;
}
else if (KeyVal < Proot->Keyval) {
if (Proot->lchild == NULL) {
Proot->lchild = New;
return true;
}
Proot = Proot->lchild;
}
else {
if (Proot->rchild == NULL) {
Proot->rchild = New;
return true;
}
Proot = Proot->rchild; //
}
}
return true; //
}
//前序遍历
bool BSTree_PreOrder(BSTNode_t* root)
{
if(root == NULL)
{
return false;
}
printf("KeyVal = %d\n",root->Keyval);
BSTree_PreOrder(root->lchild);
BSTree_PreOrder(root->rchild);
return true;
}
//中序遍历
bool BSTree_InOrder(BSTNode_t* root)
{
if(root == NULL)
{
return false;
}
BSTree_InOrder(root->lchild);
printf("KeyVal = %d\n",root->Keyval);
BSTree_InOrder(root->rchild);
return true;
}
//后序遍历
bool BSTree_PostOrder(BSTNode_t* root)
{
if(root == NULL)
{
return false;
}
BSTree_PostOrder(root->lchild);
BSTree_PostOrder(root->rchild);
printf("KeyVal = %d\n",root->Keyval);
return true;
}
int main()
{
// --- 1. 测试：创建根节点 ---
printf("1. 创建根节点...\n");
BSTNode_t* root = BSTree_Create(50);
if (root) {
printf("成功创建根节点，值为: %d\n", root->Keyval);
}
// --- 2. 测试：插入多个节点 ---
printf("\n2. 插入其他节点...\n");
int values[] = {30, 70, 20, 40, 60, 80, 35, 45};
int n = sizeof(values) / sizeof(values);
for (int i = 0; i < n; i++) {
if (BSTree_InsertNode(root, values)) {
printf("成功插入: %d\n", values);
}
}
// --- 3. 测试：重复插入（应失败）---
printf("\n3. 测试重复插入...\n");
BSTree_InsertNode(root, 40);// 已存在
BSTree_InsertNode(root, 50);// 根节点已存在
// --- 4. 测试：遍历操作 ---
printf("\n4. 遍历测试...\n");
printf("\n=== 前序遍历 (Pre-order) ===\n");
BSTree_PreOrder(root);
printf("\n=== 中序遍历 (In-order) - 应升序输出 ===\n");
BSTree_InOrder(root);
printf("\n=== 后序遍历 (Post-order) ===\n");
BSTree_PostOrder(root);
printf("\n7. 测试插入到 NULL 树（应失败）...\n");
BSTNode_t* emptyTree = NULL;
bool result = BSTree_InsertNode(emptyTree, 100);
if (!result) {
printf("正确：无法向 NULL 树插入节点。\n");
}
printf("\n所有测试完成\n");
return 0;
}
</code></pre>
<blockquote>
<p>根节点的值是50，主函数中依次插入节点：30, 70, 20, 40, 60, 80, 35, 45，所以这棵树的图像长这个样子<br>
<img src="https://img2024.cnblogs.com/blog/3677701/202508/3677701-20250804210437255-1892716154.png" alt="msedge_FFfY1DDJMl" loading="lazy"></p>
</blockquote>
<h2 id="运行结果">运行结果</h2>
<p><img src="https://img2024.cnblogs.com/blog/3677701/202508/3677701-20250804210737446-2047069018.png" alt="vmware_T22DOzRczs" loading="lazy"></p>
<p><img src="https://img2024.cnblogs.com/blog/3677701/202508/3677701-20250804210635853-597176566.png" alt="vmware_kjOd3npI9Z" loading="lazy"></p><br><br>
来源：https://www.cnblogs.com/YueZone/p/19022187
頁:
[1]