首页 > 编程语言 > 详细

二叉排序树的部分实现

时间:2020-04-19 18:37:46      阅读:38      评论:0      收藏:0      [点我收藏+]

Search(T,key)伪代码

Search(T, key)
{
	if (T为空 || 找到)
	{
		return T;
	}
	 if (key < T - key)
	{
		return Search(左子树查找);
}
	 else
	 {
		 return Search(右子树查找);
	 }

InsertBST(T,key)伪代码

void InsertBST(T, key) {
	if (T为空){
		新生成一个结点;
		}
	else if (T == key)
	{
		return 0;
	}
	else if (T > key)
		InsertBST(T->lchild, key);
	else
		InsertBST(T->rchild, key);
}

Create(T,key)伪代码

void CreateBST(BSTree& T)
{
	int n;
	输入插入个数
	int a[100];
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];//输入插入数据
		InsertBST(T, a[i]);
	}
}

BST的创建

数据类型定义

typedef struct BSTNode
{
	int data;
	struct BSTNode* lchild, * rchild;
}* BSTree;

main函数

int main()
{
	BSTree T = NULL;
	int key;
	CreateBST(T);
	cout << "中序遍历的结果为:" << endl;
	InOrder(T);
	cout << endl;
	return 0;

}

Search(T,key)函数

void InsertBST(BSTree& T, int key)
{
	if (T==NULL)
	{
		T = new BSTNode;
		T->data = key;
		T->lchild = T->rchild = NULL;
	}
	else if (T->data == key)
	{
		return;
	}
	else if (T->data > key)
	{
		InsertBST(T->lchild, key);
	}
	else
	{
		InsertBST(T->rchild, key);
	}
}

InsertBST(BSTree& T, int key)函数

void InsertBST(BSTree& T, int key)
{
	if (T==NULL)
	{
		T = new BSTNode;
		T->data = key;
		T->lchild = T->rchild = NULL;
	}
	else if (T->data == key)
	{
		return;
	}
	else if (T->data > key)
	{
		InsertBST(T->lchild, key);
	}
	else
	{
		InsertBST(T->rchild, key);
	}
}

中序遍历代码

void InOrder(BSTree T)
{

	if (T)
	{
		InOrder(T->lchild);
		cout << T->data << " ";
		InOrder(T->rchild);
	}
}

BST中删除关键字key所需注意的事项

(1)删除叶子节点

直接删除该节点

(2)只有左子树或右子树

用其左子树或者右子树代替它,用其父结点指向其子节点

(3)既有左子树也有右子树

用其前驱或后驱节点替代,并将其前驱节点或后驱节点删掉

Delete(T,key)伪代码

 Delete(T,key)
{
	 if (树空)
	 {
		 return 删除失败;
	}
	else if (找到)
		{
			Delete(T);
			return 1;
		}
		else if (key < T->data)
		{
			return Delete(T->lchild, key);
		}
		else
		{
			return Delete(T->rchild, key);
		}
	}

1、2部分全部代码实现

#include<iostream>
using namespace std;
typedef struct BSTNode
{
	int data;
	struct BSTNode* lchild, * rchild;
}* BSTree;
void InsertBST(BSTree& T, int key)
{
	if (T==NULL)
	{
		T = new BSTNode;
		T->data = key;
		T->lchild = T->rchild = NULL;
	}
	else if (T->data == key)
	{
		return;
	}
	else if (T->data > key)
	{
		InsertBST(T->lchild, key);
	}
	else
	{
		InsertBST(T->rchild, key);
	}
}

void CreateBST(BSTree& T)
{
	int n;
	cout << "请输入要插入的节点数: ";
	cin >> n;
	int a[100];
	cout << "请输入" << endl;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		InsertBST(T, a[i]);
	}
}

void InOrder(BSTree T)
{

	if (T)
	{
		InOrder(T->lchild);
		cout << T->data << " ";
		InOrder(T->rchild);
	}
}
int main()
{
	BSTree T = NULL;
	int key;
	CreateBST(T);
	cout << "中序遍历的结果为:" << endl;
	InOrder(T);
	cout << endl;
	return 0;

}

二叉排序树的部分实现

原文:https://www.cnblogs.com/254916-cn/p/12731063.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!