二叉查找树C语言实现
1. 二叉查找树的定义:
左子树不为空的时候,左子树的结点值小于根节点,右子树不为空时,右子树的结点值大于根节点,左右子树分别为二叉查找树
2. 二叉查找树的最左边的结点即为最小值,要查找最小值,只需遍历左子树的结点直到为空为止,同理,最右边的结点结尾最大值,要查找最大值,只需遍历右子树的结点直到为空为止。二叉查找树的插入查找和删除都是通过递归的方式来实现的,删除一个结点的时候,先找到这个结点S,然后并不是真正的删除这个结点S,而是在其右子树找到后继结点,将后继结点的值付给S,然后删除这个后继结点即可。
3. 二叉查找树的C实现:
# include <iostream> # include <cstdlib> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x):val(x),left(NULL),right(NULL){} }; TreeNode *insert(TreeNode *root,int val) //插入元素 { if(root==NULL) { root=new TreeNode(val); return root; } if(val<root->val) root->left=insert(root->left,val); if(val>root->val) root->right=insert(root->right,val); return root; } TreeNode *findmin(TreeNode *root) { if(root==NULL) return NULL; if(root->left==NULL&&root->right==NULL) return root; if(root->left) return findmin(root->left); } bool find(TreeNode *root,int val) //查找元素,若存在返回1,不存在返回0 { if(root==NULL) return false; if(root->val==val) return true; if(val<root->val) return find(root->left,val); else return find(root->right,val); return false; } TreeNode *delnum(TreeNode *root,int val) { if(root==NULL) return NULL; if(val>root->val) root->right=delnum(root->right,val); else if(val<root->val) root->left=delnum(root->left,val); else { if(root->left&&root->right) //待删除结点有两个孩子的情形 { TreeNode *tmp=findmin(root->right); root->val=tmp->val; root->right=delnum(root->right,tmp->val); } else //待删除结点只有一个或者没有孩子 { if(root->left==NULL) root=root->right; else if(root->right==NULL) root=root->left; } } return root; } int main() //测试代码 { TreeNode *root=NULL; root=insert(root,3); root=insert(root,2); root=insert(root,4); root=insert(root,1); cout<<find(root,2)<<endl; root=delnum(root,2); cout<<find(root,2)<<endl; system("pause"); return 0; }