【附C源码】二叉搜索树的C语言实现-洪萨配资

【附C源码】二叉搜索树的C语言实现

前言

二叉搜索树（Binary Search Tree，BST）作为一种基础且重要的数据结构，在计算机科学领域有着广泛的应用。本文将介绍一种基于C语言的二叉搜索树实现方案，涵盖其核心原理、代码实现细节以及使用方式。

核心原理

二叉搜索树的核心性质在于：对于树中的任意节点，其左子树中所有节点的值均小于该节点的值，右子树中所有节点的值均大于该节点的值。这一性质保证了中序遍历二叉搜索树时，输出结果必然是有序的。

基于这一性质，二叉搜索树在平均情况下能够以 O(log n) 的时间复杂度完成插入、删除和查找操作。当然，在最坏情况下（如树退化为链表），时间复杂度会退化为 O(n)，这也是后续需要引入平衡机制的原因。

数据结构定义

首先定义树节点和树结构体：

typedefintData;typedefstructTreeNode{Data data;structTreeNode*left;structTreeNode*right;}TreeNode;typedefstruct{TreeNode*root;intsize;}Tree;

此处采用typedef int Data的方式对数据类型进行抽象，便于后续扩展为其他类型。树结构体中维护size字段，使得获取节点数量的操作能够在 O(1) 时间内完成。

关键操作实现

节点插入

插入操作的核心逻辑是从根节点出发，根据待插入值与当前节点值的大小关系，决定向左子树或右子树递归查找，直至找到合适的空位置：

booltreeInsert(Tree*t,Data val){TreeNode*newNode=(TreeNode*)malloc(sizeof(TreeNode));newNode->data=val;newNode->left=NULL;newNode->right=NULL;if(!t->root){t->root=newNode;t->size++;returntrue;}TreeNode*current=t->root;TreeNode*parent=NULL;while(current){parent=current;if(val<current->data){current=current->left;}elseif(val>current->data){current=current->right;}else{free(newNode);// 重复值不插入returnfalse;}}if(val<parent->data){parent->left=newNode;}else{parent->right=newNode;}t->size++;returntrue;}

该实现采用迭代方式而非递归，避免了函数调用栈的开销。同时，代码中明确处理了重复值的情况，保证树中不存在重复节点。

节点删除

删除操作是二叉搜索树中最复杂的操作，需要根据待删除节点的子节点数量分三种情况处理：

叶子节点：直接删除，无需额外操作
单子节点：用子节点替代被删除节点
双子节点：用右子树的最小值（或左子树的最大值）替代被删除节点，然后递归删除该最小值节点

TreeNode*treeRemoveNode(TreeNode*node,Data val){if(!node)returnNULL;if(val<node->data){node->left=treeRemoveNode(node->left,val);}elseif(val>node->data){node->right=treeRemoveNode(node->right,val);}else{if(!node->left){TreeNode*temp=node->right;free(node);returntemp;}elseif(!node->right){TreeNode*temp=node->left;free(node);returntemp;}TreeNode*temp=treeFindMin(node->right);node->data=temp->data;node->right=treeRemoveNode(node->right,temp->data);}returnnode;}

此处选择右子树的最小值作为替代节点，是因为该值必然大于左子树所有节点且小于右子树其余节点，满足二叉搜索树的性质。

树的遍历

三种基本遍历方式的递归实现：

voidtreeInOrderNode(TreeNode*node){if(!node)return;treeInOrderNode(node->left);printf("%d ",node->data);treeInOrderNode(node->right);}

中序遍历的输出结果即为升序序列，这一特性在实际应用中经常被利用。前序遍历和后序遍历的实现结构类似，仅调整访问顺序即可。

可视化输出

为了便于调试和验证，实现了一个简单的树形打印函数：

voidtreePrintNode(TreeNode*node,intdepth){if(!node)return;treePrintNode(node->right,depth+1);for(inti=0;i<depth;i++){printf(" ");}printf("%d\n",node->data);treePrintNode(node->left,depth+1);}

该函数采用右-根-左的遍历顺序，配合缩进输出，使得树的结构能够直观地呈现在终端上。

内存管理

C语言不像高级语言具备自动垃圾回收机制，因此内存管理需要格外谨慎。本实现中，销毁树的操作采用后序遍历的顺序递归释放节点：

voidtreeNodeDestroy(TreeNode*node){if(!node)return;treeNodeDestroy(node->left);treeNodeDestroy(node->right);free(node);}

必须确保子节点先于父节点释放，否则会导致内存泄漏或访问非法内存。

使用示例

以下是一个完整的使用示例：

intmain(){Tree*t=treeCreate();treeInsert(t,50);treeInsert(t,30);treeInsert(t,70);treeInsert(t,20);treeInsert(t,40);treePrint(t);treeInOrder(t);printf("树高度: %d\n",treeHeight(t));printf("叶子节点数: %d\n",treeCountLeaves(t));treeRemove(t,30);treePrint(t);treeDestroy(t);return0;}