最近回顾了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
……