二叉查找樹C語言實現

二叉查找樹C語言實現

1. 二叉查找樹的定義：

左子樹不為空的時候，左子樹的結點值小於根節點，右子樹不為空時，右子樹的結點值大於根節點，左右子樹分別為二叉查找樹

2. 二叉查找樹的最左邊的結點即為最小值，要查找最小值，只需遍歷左子樹的結點直到為空為止，同理，最右邊的結點結尾最大值，要查找最大值，只需遍歷右子樹的結點直到為空為止。二叉查找樹的插入查找和刪除都是通過遞歸的方式來實現的，刪除一個結點的時候，先找到這個結點S，然後並不是真正的刪除這個結點S，而是在其右子樹找到後繼結點，將後繼結點的值付給S，然後刪除這個後繼結點即可。

3. 二叉查找樹的C實現：

# include 
# include 
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(valval)
	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(valval)
	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(valval)
	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<