自己实现的 二叉查找树,受益于人,回馈于人
#include <stdio.h>
#include <stdlib.h>
typedef struct node* pNode;
struct node {
int data;
pNode left;
pNode right;
pNode parent;
};
pNode root;
void traverse(pNode);
pNode search(pNode, int);
pNode getMin(pNode);
pNode getMax(pNode);
pNode getSuccessor(pNode, int);
void insert(pNode* root, pNode element); //////// insert new element
pNode delete(pNode* root, int);
#include "BSTree.h"
/*************************
* Binary search tree
*
* By Jia Pengcheng
*************************/
void traverse(pNode root){
pNode st = root;
if(st){
traverse(st->left);
printf("%d, ", st->data);
traverse(st->right);
}
}
void insert(pNode* root, pNode element){
//<1> first, need to know whether this element has been in the tree
pNode start = *root;
// if the tree is empty
if(!start){
*root = element;
return;
}
pNode backup_start = NULL;
while(start){
backup_start = start; // save the position for insertion
if(element->data > start->data){
start = start->right;
}else if(element->data <= start->data){
start = start->left;
}
}
// if not existed
element->parent = backup_start;
if(element->data > backup_start->data){
backup_start->right = element;
}else{
backup_start->left = element;
}
}
pNode search(pNode root, int val){
pNode st = root;
while(st && (st->data != val)){
if(st->data > val){
st = st->left;
}else if(st->data < val){
st = st->right;
}
}
return st;
}
pNode getMax(pNode root){
pNode st = root;
while(st->right){
st = st->right;
}
return st;
}
pNode getMin(pNode root){
pNode st = root;
while(st->left){
st = st->left;
}
return st;
}
pNode getSuccessor(pNode root, int val){
pNode elem = NULL;
if(!(elem = search(root, val))) return NULL;
// if elem has right child, successor is the minimum element
if(elem->right){
return getMin(elem->right);
}else{ //////////// if has no right child, find the node which is its parent's left child, ruturn the parent
pNode tmp = elem->parent;
while(tmp && elem == tmp->right){
elem = tmp;
tmp = tmp->parent;
}
return tmp;
//pNode tmp = NULL;
//do{
//tmp = elem;
//elem = elem->parent;
//}while(elem && (tmp == elem->right));
//return tmp;
}
}
/// one child, two childs, 0 child
pNode delete(pNode* root, int val){
/// empty tree
if(!*root) return;
// this elem is not in the tree
pNode elem = search(*root, val);
if(!elem){
printf("%d is not in the tree\n", val);
return NULL;
}
pNode tmp = NULL;
if(!elem->left || !elem->right){
tmp = elem; /// if elem has one child or zero child
}else{
tmp = getSuccessor(*root,val); /// id elem has two childs, delete successor of elem, and then replace elem with successor
/// we need to know that successor of elem has one right child at most, it does not have left child
///printf("Successor is %d\n", tmp->data);
}
///========================= has at most one child ============================
pNode child = NULL;
if(tmp->left) /// why left first? cos successor of elem has no left child
child = tmp->left;
else
child = tmp->right;
if(child)
child->parent = tmp->parent; /// set parent pointer of elem's child, when tmp has one child
/// if tmp has parent, it means that it is not the root node
if(tmp->parent){
if(tmp == tmp->parent->left){
tmp->parent->left = child;
}else{
tmp->parent->right = child;
}
}else{
*root = child; /// tmp has no parent, it is root, when tmp is deleted, child should become the root
}
/// ===========================================================
///if tmp has two childs, tmp is the successor of tmp, so tmp != elem
if(tmp != elem){
elem->data = tmp->data; /// replace date of elem with data of tmp which is the successor of elem
}
return tmp;
}
分享到:
相关推荐
二叉查找树的源代码,包含查找,插入,删除等等
资源内容:完整的二叉查找树C++头文件,包括运算符重载,bst类构造器、bst类析构器、destroy()、size()、insert(),迭代器类的声明与实现,++运算符重载(前置、后置)、--运算符重载、*运算符重载、!=运算符重载、...
动态规划ppt(最优BST,矩阵连乘) 动态规划问题求解的步骤及分析 最优二叉查找树、矩阵连乘的问题分析、建模、伪代码
数据结构——二叉查找树(BST)静态查找表,使用数据结构实现BST
二叉查找树, 创建、查找、插入、删除、打印等功能都能实现,还包括先序、中序、后序遍历。可以参考,这资源规则都变了囧。
avl树,bst树(二叉查找树),rbt(红黑树),sbt(size平衡树),splay(伸展树),treap树。 3.代码以一个bst_base为基础,实现通用算法。将对象特征和存储结构通过模板参数向上传递,实现特化算法。最终各个不同...
二叉查找树的查找、插入、删除、建立操作
二叉排序树(BST)又称二叉查找树、二叉搜索树 二叉排序树(Binary Sort Tree)又称二叉查找树。它或者是一棵空树;或者是具有下列性质的二叉树: 1.若左子树不空,则左子树上所有结点的值均小于根结点的值; 2.若...
二叉排序树(又称二叉查找树):(1)若左子树不空,则左子树上所有节点的值均小于它的根结点的值;(2)若右子树不空,则右子树上所有节点均大于它的根结点的值;(3)它的左右子树分别为二叉排序树。 二叉平衡树:若...
看了算法导论之后,写的简单的二叉查找树的生成、各种遍历方式、已经插入、删除操作 使用方法: 执行./configure命令 执行make f01命令 执行./bst 100 然后就是各种操作
当二叉排序树BST中不存在结点值等于e时,插入e并返回0,否则返回-1. ③int deleteBST(BTree *T, char key);删除 若二叉排序树T中存在结点值等于key时,则删除该数据元素,并返回0;否则返回-1。 ④BTree searchBST...
二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树:1.若它的左子树非空,则左子树上所有结点的值均小于根结点的值;2.若它的右...
二叉搜索树(BST,Binary Search Tree)又称二叉查找树或二叉排序树。 一棵二叉搜索树是以二叉树来组织的,可以使用一个链表数据结构来表示,其中每一个结点就是一个对象。 一般地,除了key和位置数据之外,每个结点...
我们在上一篇博客中讲解了二叉树,这一次我们来实现二叉树的进阶——二叉查找树(Binary Search Tree),又称二插排序树(Binary Sort Tree)。所以简称为BST。二插查找树的定义如下: 1.若左子树不为空,则左子树...
主要为大家详细介绍了java二叉查找树的实现代码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
二叉排序树(Binary Search Tree,BST)是一种特殊的二叉树,它具有以下特点: 每个节点最多有两个子节点,分别称为左子节点和右子节点。 对于树中的每个节点,其左子树中的所有节点的值都小于该节点的值,而右子树...
用序列(46,88,45,39,70,58,101,10,66,34)建立一棵二叉排序树,画出此树,并求在等概率情况下查找成功时的平均查找长度。 9.2 给定一组关键字K={4,5,2,3,6,1},试按二叉排序树生成规则画出这棵二叉...
二叉排序树(Binary Search Tree,BST)是一种特殊的二叉树,它具有以下特点: 每个结点最多有两个子结点,称为左子结点和右子结点。 对于树中的每个结点,其左子树中的所有结点的值都小于该结点的值,而右子树中的...
代码如下:/** 实现二叉查找树的基本功能*/ #include <iostream>#include <cstring>#include <algorithm>#include <cstdio>#include using namespace std; const int M = 10000; //定义数据节点class dNode{public:...