一、结点类型
typedef struct TreeNode
{
int data;
struct TreeNode* lchild, * rchild;
}TreeNode,*TreeNodeP;
二、二叉排序树的查找
1、伪代码
SearchBST(T, key)
{
if (T为空 || T->data==key)
{
返回T;
}
if (key > T->data)
{
SearchBST(T的右孩子指针, key)
}
else
{
SearchBST(T的左孩子指针, key)
}
}
2、代码实现
TreeNodeP SearchBST(TreeNodeP T, int key)
{
if (T == NULL || T->data == key)
{
return T;
}
if (key > T->data)
{
SearchBST(T->rchild, key);
}
else
{
SearchBST(T->lchild, key);
}
}
二、二叉排序树的插入
1、伪代码
InsertBST(T, key)
{
if (T为空)
{
T = new TreeNode;
T->data = key;
T->lchild = T->rchild = NULL;
}
else if (key == T->data)
{
直接return;
}
else if (key > T->data)
{
InsertBST(T右孩子指针, key);
}
else
{
InsertBST(T左孩子指针, key);
}
}
2、代码实现
void InsertBST(TreeNodeP &T, int key)
{
if (!T)
{
T = new TreeNode;
T->data = key;
T->lchild = T->rchild = NULL;
}
else if (key == T->data)
{
return;
}
else if (key > T->data)
{
InsertBST(T->rchild, key);
}
else
{
InsertBST(T->lchild, key);
}
}
三、二叉排序树的创建
1、伪代码
CreateBST(T)
{
while (控制输入个数)
{
cin >> data;
InsertBST(T, data);
}
}
2、代码实现
TreeNodeP CreateBST()
{
int i = 0, N, data;
cin >> N;//创建树的元素个数
TreeNodeP T=NULL;
while (i<N)
{
cin >> data;
InsertBST(T, data);
i++;
}
return T;
}
3、效果展示
四、二叉排序树的删除
1、伪代码
DeleteBST(T, key)
{
if (T为空)
{
直接return;
}
else
{
if (key > T->data)
{
DeleteBST(T右孩子指针, key);
}
else if (key < T->data)
{
DeleteBST(T左孩子指针, key);
}
else
{
声明结构指针 q = T;
if (T->lchild为空)
{
q = T;
T = T->rchild;
free(q);
}
else if (T->rchild为空)
{
q = T;
T = T->lchild;
free(q);
}
else
{
Deletel(T, T->lchild);
}
return;
}
}
}
Deletel(T, p)
{
声明结构指针 q = T;
if (p->rchild不为空)
{
Deletel(T, p右孩子指针);
}
else
{
T->data = p->data;
q = p;
p = p->lchild;
free(q);
}
}
2、代码实现
void DeleteBST(TreeNodeP &T, int key)
{
if (T == NULL)
{
return;
}
else
{
if (key > T->data)
{
DeleteBST(T->rchild, key);
}
else if (key < T->data)
{
DeleteBST(T->lchild, key);
}
else
{
Delete(T);
return;
}
}
}
void Delete(TreeNodeP &T)
{
TreeNodeP q = T;
if (T->lchild == NULL)
{
q = T;
T = T->rchild;
free(q);
}
else if (T->rchild == NULL)
{
q = T;
T = T->lchild;
free(q);
}
else
{
Deletel(T, T->lchild);
}
}
void Deletel(TreeNodeP& T, TreeNodeP& p)
{
TreeNodeP q;
if (p->rchild != NULL)
{
Deletel(T, p->rchild);
}
else
{
T->data = p->data;
q = p;
p = p->lchild;
free(q);
}
}
3、效果展示(删除data==80的结点)