二进制排序树的C ++完成

最近回顾了C ++语言，在回顾过程中，我顺便回顾了数据结构的某些内容，用一颗石头杀死了两只鸟！以下是用于实现二进制排序树的类模板.

首先定义节点类型和二叉树类型:

template<typename T>
class BinaryTree;
template<typename T>   //节点类的定义
class Node
{private:
	Node<T>*lchild, *rchild;
	T info;
 public:
	 Node()
	 {
		 lchild = NULL;
		 rchild = NULL;
	 }
	 Node(T data, Node<T>*left = NULL, Node<T>*right = NULL)
	 {
		 info = data;
		 lchild = left;
		 rchild = right;
	 }
	 friend class BinaryTree < T > ;
};
template<typename T>                 //二叉排序树类的定义     
class BinaryTree
{
	Node<T>*root;
	void Inorder(Node<T>*current);              
	void Insert(const T &data,Node<T>* &b);
	void Remove(const T &data, Node<T>* &a, Node<T>* &b);
	void Destory(Node<T>*current);                           //删除二叉排序树
public:
	BinaryTree(){ root = NULL; }
	~BinaryTree(){ Destory(root); }
	void Create(T*data, int n);                      //由数组创建二叉排序树，n是数组大小
	void InOrder(){ Inorder(root); }                  //中序遍历
	void Remove(const T&data){ Remove(data,root,root); }  //删除节点
};

上面定义的二进制排序树类中涉及一些简单的操作:

template<typename T>
void BinaryTree<T>::Insert(const T &data, Node<T>* &b)  //递归法在二叉排序树中插入一个节点
{
	if (b == NULL)          //递归终止条件
	{
		b = new Node<T>(data);
		if (!b)
		{
			cout << "out of space!" << endl;
		}
	}
	else if (data < b->info)
		Insert(data, b->lchild);
	else
		Insert(data, b->rchild);
}
template<typename T>
void BinaryTree<T>::Inorder(Node<T>*current)  //中序遍历
{
	if (current != NULL)
	{
		Inorder(current->lchild);
		cout << current->info<<" ";
		Inorder(current->rchild);
	}
}
template<typename T>
void BinaryTree<T>::Create(T*data, int n)         //由数组创建二叉排序树，n是数组大小
{
	for (int i = 0; i < n; i++)
	{
		Insert(data[i],root);
	}
}

对于二进制排序树的相关操作，我个人认为最技术上的内容是删除节点. 在这个问题上还有更多的案例需要考虑.

删除节点需要考虑相应节点的状态，特别是该节点是否为空，如果不为空，则其左右子树是否存在. 我们可以进行如下操作:

1. 要找到要删除的节点，您需要在搜索时记录要删除的节点的父节点c++二叉排序树，因为需要同时清理该节点（空白节点的父子节点或子节点）.

2. 根据待删除节点左右子树的状态，进行相应的处理，这些状态包括:

1. 如果要删除的节点的左右节点不存在，则将其直接删除，并清空其父节点（如果有父节点）的相应指针.

2. 如果要删除的节点的左子树存在，则右子树不存在，或者左子树不存在，并且右子树存在. 只需直接在其子树中添加一个候选边即可.

3. 如果存在要删除的节点的左右子树，则情况会稍微复杂一些. 必须根据二进制排序树的性质，从左侧的子树或子树中选择节点以填充要删除的节点的位置.

通常，在树的中间遍历中与要删除的节点相邻的节点（左和右节点都可以c++二叉排序树，这里是右节点值）来替换要删除的节点. 实际执行删除操作时，不会

真正删除要删除的节点，但是将要删除的节点的键值分配给替换节点的键值，然后删除替换节点.

（a）（b）

上图（a）至（b）是典型的删除过程，其中要删除的节点的左右子树都存在: 要删除15个节点，请首先将21个节点更改为20个左边的子树节点，然后更改18个节点. 请参阅将值复数值更改为要删除的15个节点，最后删除原始的18个节点.

template<typename T>
void BinaryTree<T>::Remove(const T &data, Node<T>* &a, Node<T>* &b)
{
	         Node<T>*temp1, *temp2;
		if (b == NULL) { cerr << "Invalid input"; return; }
		if (data < b->info) Remove(data, b, b->lchild);    //先找到节点位置，这里没有考虑找不到的情况
		else if (data >b->info) Remove(data, b, b->rchild);
               ?else if (b->lchild != NULL&&b->rchild != NULL)     //这个分支以及下面的分支表示已找到data所在节点
		{
			temp2 = b;
			temp1 = b->rchild;
			if (temp1->lchild != NULL)
			{
				while (temp1->lchild != NULL)
				{
					temp2 = temp1;
					temp1 = temp1->lchild;
				}
				temp2->lchild = temp1->rchild;
			}
			else temp2->rchild = temp1->rchild;
			b->info = temp1->info;
			delete temp1;
		}
	        else                                                //左右子树中至少有一个不存在的情况
		{
			temp1 = b;
			if (b->rchild != NULL)
			{
				temp1 = b->rchild;
				b->info = temp1->info;
				b->rchild = temp1->rchild;
				b->lchild = temp1->lchild;
			}
			else if (b->lchild != NULL)
			{
				temp1 = b->lchild;
				b->info = temp1->info;
				b->rchild = temp1->rchild;
				b->lchild = temp1->lchild;
			}
			else if (b == root) root = NULL;
			else if (a->rchild == temp1) a->rchild = NULL;
			else a->lchild = NULL;
			delete temp1;
		}
	
}

以上代码已经过测试并通过，欢迎交流.

本文来自本站，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-286414-1.html