二叉树查找树的基本操作

一、什么是二叉查找树:

顾名思义,一棵二叉查找树是以一棵树的形式组织起来的。如图一所看到的。

其能够使用一个链表数据结构来表示,

中每一个节点就是就是一个对象。除了包括数据域之外还包括属性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);//树中不能有相等的值
/*查找一个keyword是否在二叉树中,存在的话返回指向该节点的指针。否则返回NULL*/
STree tree_find(STree root, ElemType e);
/*删除keyword为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 << "
删除后中序输出例如以下:" << 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;
}
输出结果为:



原文地址:https://www.cnblogs.com/lytwajue/p/7216383.html