二叉树查找树的基本操作

一、什么是二叉查找树：

顾名思义，一棵二叉查找树是以一棵树的形式组织起来的，如图一所示。其可以使用一个链表数据结构来表示，

其 中每个节点就是就是一个对象。除了包含数据域之外还包含属性lchild、rchild、parent，分别指向左孩子、右孩子、父节点。如果某个孩子节点和双亲节点不存在，则相应属性的值NULL。二叉查找树的性质为：设x为树中的任意一节点。如果y是左子树中的节点那么x.data>y.data， 如果y是右子树中的节点那么x.data<y.data。

二、二叉查找树的基本操作

二叉查找树的节点结构定义如下：

typedef struct node
{
ElemType data;
struct node *lchild, *rchild,*parent;
}SNode, *STree;

二叉树的基本操作主要包括插入、查询、删除等。1）插入操作：当向一棵二叉树插入一个节点时，要判断此节

点的数据域和根节点的大小，如果比根节点数据域大就插入左子树中，比根节点小就插入右子树中，等于根节点插入失败。插入操作的函数声明为：int tree_insert(STree *root, ElemType e)。2）查找操作：当从一棵二叉树查找一个节点时，要判断此节点的数据域和根节点的大小，如果比根节点数据域大就在左子树中查找，比根节点小就在右子树中查找，等于根节点就返回指向此根节点的指针，否则返回NULL。查找操作的函数声明为：STree tree_find(STree root, ElemType e)。3）删除操作：删除操作分三种情况：①要删除的节点没有孩子节点，直接删除，并修改其父节点。如图二所示。②该节点只有一个孩子：将该节点的孩子直接提升到该节点处，并修改该相应的指针。如图三所示。③若该z节点有两个孩子：此情况比较复杂，找到该节点的后继y，并用y的右孩子替换y节点，再用y节点替换z，z的左孩子置为y的左孩子。如图四所示。

三、具体代码如下：(构造图一的二叉查询树)

#include <iostream>
typedef int ElemType;
using namespace std;

typedef struct node
{
ElemType data;
struct node *lchild, *rchild,*parent;
}SNode, *STree;

/*向二叉树中插入一个节点*/
int tree_insert(STree *root, ElemType e);//树中不能有相等的值
/*查找一个关键字是否在二叉树中，存在的话返回指向该节点的指针，否则返回NULL*/
STree tree_find(STree root, ElemType e);
/*删除关键字为e的节点，删除成功返回1，否则返回0（不存在该节点）*/
int tree_delete(STree *root, ElemType e);//删除节点之后任然是一棵二叉查找树
void replace_node(STree *root, STree u, STree v);//用v节点替换u节点
/*二叉查找树的中序遍历是按序输出的*/
void mid_travesal(STree root);
int main()
{
STree root = NULL;
int data;
cout << "输入要插入的十个整形，中间用空格分开" << endl;
for (int i = 0; i < 10;i++)
{
cin >> data;
tree_insert(&root, data);
}

STree temp = tree_find(root, 13);
if (temp != NULL)
{
cout << "找到了该节点：" << temp->data << endl;
}

cout << "删除前中序输出如下：" << endl;
mid_travesal(root);
if (tree_delete(&root,30))
{
cout << "\n删除后中序输出如下：" << endl;
mid_travesal(root);
}
cout << endl;
}

int tree_insert(STree *root, ElemType e)
{
/*先构造树节点*/
STree temp = (STree)malloc(sizeof(SNode));
temp->data = e;
temp->lchild = NULL;
temp->rchild = NULL;
temp->parent = NULL;

if (*root == NULL)//如果是棵空树
{
*root = temp;
return 1;
}

STree x = *root;
STree y = x;//y用来记录x的值
while (x != NULL)//找到叶子节点
{
y = x;
if (x->data == e)
return 0;
else if (x->data < e)
x = x->rchild;
else
x = x->lchild;
}

if (y->data > e)
y->lchild = temp;
else
y->rchild = temp;
temp->parent = y;
return 1;

}
void mid_travesal(STree root)
{
if (root != NULL)
{
mid_travesal(root->lchild);
cout << root->data << "  ";
mid_travesal(root->rchild);
}
}
STree tree_find(STree root, ElemType e)
{
while (root != NULL && root->data != e)
{
if (root->data > e)
root = root->lchild;
else
root = root->rchild;
}

return root;
}
/*二叉查找树的删除有3中情况：
1、该节点没有孩子：直接删除，并修改其父节点。
2、该节点只有一个孩子：将该节点的孩子直接提升到该节点处，并修改该相应的指针
3、若该z节点有两个孩子：此情况比较复杂，找到该节点的后继y，并用y的右孩子替换y节点，再用y节点替换z，z的左孩子置为y的左孩子*/
int tree_delete(STree *root, ElemType e)
{
STree temp = tree_find(*root, e);
if (temp == NULL)//树中没有该节点
return 0;
if (temp->lchild != NULL && temp->rchild != NULL)//该节点有左孩子和右孩子
{
STree y = temp->rchild;
while (y->lchild != NULL)
y = y->lchild;
if (y != temp->rchild)//说明y是孙子节点
{
replace_node(root, y, y->rchild);//用y的右孩子替换y
replace_node(root, temp, y);
y->lchild = temp->lchild;
y->rchild = temp->rchild;
temp->lchild->parent = y;
temp->rchild->parent = y;
}
else
{
replace_node(root, temp, y);
y->lchild = temp->lchild;
temp->lchild->parent = y;
}
}
else if (temp->lchild != NULL || temp->rchild != NULL)//该节点只有左孩子或者只有右孩子
{
if (temp->lchild != NULL)//只有左孩子
replace_node(root, temp, temp->lchild);
else
replace_node(root, temp, temp->rchild);
}
else//该节点没有孩子
replace_node(root, temp, NULL);

free(temp);
return 1;
}
void replace_node(STree *root, STree u, STree v)
{
if (u->parent == NULL)
*root = v;
else if (u == u->parent->rchild)
u->parent->rchild = v;
else
u->parent->lchild = v;
if (v != NULL)
v->parent = u->parent;
}

输出结果为：