二叉搜索树:
二叉树的查找很简单,先序后序中序都可以,一开始要判断是否为空。
插入要判断一下是否存在,查找时同时记录其父节点,然后直到找到空节点,插入。
删除比较复杂一点:
逐一判断:
先判断是否为空,然后查找到要删除的节点p,并记录其父节点q,如果查不到,返回false;
当p节点有两个子树时,查到其中序遍历的后继节点,即排序后的位于p节点之后的节点,记为s。查找的同时记录s的父节点r,然后将s的值复制给p,然后以s为p,r为q,将问题转换为p节点只有最多一棵子树的情况,即之后的情况。这里是因为其为中序遍历的第一个节点,这此时的p点绝对没有左子树。
当p节点只有一颗子树或没有时,将其的子树或者null赋值个c,为p的子节点,然后让其代替p在q的位置。
当p节点为根节点时,则c节点为根节点。
释放p的内存。
代码如下:
#include "BSTree.h"
template<typename T>
bool BSTree<T>::Search(const T& x) const{
if(!root) return false;
return Search(root,x);
}
template<typename T>
bool BSTree<T>::Search(const BTNode<T> *p, const T& x)const{
if(!p)return false;
if(p->element == x)return true;
if(p->lchild)return Search(p->lchild,x);
if(p->rchild)return Search(p->rchild,x);
return false;
}
template<typename T>
bool BSTree<T>:: Insert(const T& x){
if(!root)
root = new BTNode<T>(x);
else{
BTNode<T>* p = root,q = 0;
while(p){
q = p;
if(p->element==x)return false;
else if(x < p->element)p = p->lchild;
else p = p->rchild;
}
p = new BTNode<T>(x);
q -> rchild = p;
}
return true;
}
template<typename T>
bool BSTree<T>::Remove(const T& x){
BTNode<T> *c,*s,*r,*p = root,*q = 0;
if(p)return false;
while(p &&p->element != x){
q = p;
if(x < p->element) p = p->lchild;
else p = p->rchild;
}
if(!p ) return false;
if(p->lchild && p->rchild){
s = p->rchild;r = p;
while(r->lchild){
r = s;
s = s->lchild;
}
p->element = s->element;
p = s;
q = r;
}
if(p ->lchild ) c = p->rchild;
else c = p->lchild;
if( p == root) root = c;
else if(p == q->lchild) q->lchild = c;
else q->rchild = c;
delete p;
return true;
}
头文件:
#ifndef BSTREE
#define BSTREE
template <typename T>
struct BTNode
{
BTNode(){lchild =rchild = 0;}
BTNode(const T& x){
element = x;
lchild =rchild = 0;
}
BTNode<T>* lchild,*rchild;
T element;
};
template <typename T>
class BSTree{
public:
BSTree(){root = 0;}
bool Search(const T& x) const;
bool Insert(const T& x);
bool Remove(const T& x);
private:
bool Search(const BTNode<T> *p, const T& x)const;
protected:
BTNode<T>* root;
};
#endif
分享到:
相关推荐
使用二叉链表和c++来实现二叉搜索树,提供插入、删除、遍历、求最小节点、最大最节点等操作。
函数Insert将X插入二叉搜索树BST并返回结果树的根结点指针; 函数Delete将X从二叉搜索树BST中删除,并返回结果树的根结点指针;如果X不在树中,则打印一行Not Found并返回原树的根结点指针; 函数Find在二叉搜索树...
给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树,都得到一样的结果。于是对于输入的...
1.在二叉搜索树中插入节点 2.前序、中序、后序遍历该二叉搜索树,写出遍历序列 3.输出二叉搜索树的深度、节点数目、叶子节点数目 4.退出
1.二叉搜索树的建立 2.二叉搜索树节点的查找 3.二叉搜索树节点的删除 4.二叉搜索树的中序、后序递归遍历 5.二叉搜索树的中序、后序非递归遍历 6.二叉搜索树查找某个节点的前驱(下一个值比当前节点x大的节点)
1.实现二叉搜索树的基本操作 2.包括建立,查找,删除,显示 3.得到最长路径和最短路径,并能分别计算长度
该程序是在VC2005下基于二叉搜索树实现的,主要功能包括查找、删除、添加、修改等基本操作,另外还有关于MFC位图显示,文件读写的操作
增强二叉搜索树
最优二叉搜索树详细的分析了最优二叉树的伪代码以及给出了算法设计,还包含一个例子用来更好的理解最优二叉搜索树的流程
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 包含二叉树的建立,测试输出。。可直接运行。。
二叉搜索树的详细算法的过程,是算法分析里较为重要的一个算法
二叉搜索树判断的ppt有动画,有递归讲解,二叉搜索树判断的ppt有动画,有递归讲解,十分详细,适合要做演示的老师和同学 二叉搜索树判断的ppt有动画,有递归讲解,二叉搜索树判断的ppt有动画,有递归讲解,十分详细,...
acm题目二叉搜索树的参考源代码,内含测试数据和源代码。
是我自己所写的二叉搜索树的源码,里面有自己的一些注释和理解
摘要视图订阅登录 | 注册195897次第4587名57篇33篇0篇117条0020算法笔记——【动态规划】最优二叉搜索树问题 liufeng_king的专
本代码实现了二叉搜索树的插入功能,是基于c/c++的类型实现的,在vs下可以运行
数据结构课程实验C++实现霍夫曼树和二叉搜索树
很简单的一个例子!非常适合新手观看!!!!!!!!!!!!!!!!!!!!!