C++ 二叉搜索树(BST)的实现方法
废话不多说了，直接给大家贴代码了，具体代码如下所示：
class BST
{
public:
struct Node
{
int key;//节点的key
int value;//节点的value
Node* left;
Node *right;
int N;//节点的叶子节点数目
Node(int _key, int _value, int _N)
{
key = _key;
value = _value;
N = _N;
}
};
BST();
~BST();
void put(int key, int value);
int get(int key);
int deleteKey(int key);
private:
Node* _deleteKey(int key, Node *x);
Node* _deleteMin(Node *x);
int size(Node *x);
int _get(int key, Node* x);
Node * _put(int key, int value,Node *x);
Node * min(Node *x);
Node* root;
};
inline int BST::size(Node * x)
{
if (x == nullptr)return 0;
return x->N;
}
int BST::_get(int key, Node * x)
{
if (x == nullptr)return 0;
if (x->key < key)_get(key, x->right);
else if (x->key > key)_get(key, x->left);
else {
return x->value;
}
return 0;
}
BST::Node* BST::_put(int key, int value, Node * x)
{
if (x == nullptr) {
Node *tmp = new Node(key, value, 1);
return tmp;
}
if (x->key > key) {
x->left=_put(key, value, x->left);
}
else if (x->key < key) {
x->right=_put(key, value, x->right);
}
else x->key = key;
x->N = size(x->left) + size(x->right) + 1;
return x;
}
BST::Node* BST::min(Node * x)
{
if (x->left == nullptr)return x;
return min(x->left);
}
BST::BST()
{
}
BST::~BST()
{
}
void BST::put(int key, int value)
{
root=_put(key, value, root);
}
int BST::get(int key)
{
return _get(key, root);
}
BST::Node* BST::_deleteKey(int key, Node * x)
{
if (x->key > key)x->left = _deleteKey(key, x->left);
else if (x->key < key)x->right = _deleteKey(key, x->right);
else {
if (x->left == nullptr)return x->right;
else if (x->right == nullptr)return x->left;
else {
Node *tmp = x;
x = min(tmp->right);
x->left = tmp->left;
x->right = _deleteMin(tmp->right);
}
}
x->N = size(x->left) + size(x->right) + 1;
return x;
}
BST::Node* BST::_deleteMin(Node * x)
{
if (x->left == nullptr)return x->right;
x->left = _deleteMin(x->left);
x->N = size(x->left) + size(x->right) + 1;
return x;
}
int BST::deleteKey(int key)
{
return _get(key, root);
}
以上所述是小编给大家介绍的C++ 二叉搜索树(BST)的实现方法，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！
相关推荐
-
C++二叉树结构的建立与基本操作
准备数据定义二叉树结构操作中需要用到的变量及数据等. 复制代码 代码如下: #define MAXLEN 20 //最大长度typedef char DATA; //定义元素类型struct CBTType //定义二叉树结点类型 { DATA data; //元素数据 CBTType * left; //左子树结点指针 CBTType * right; //右子树结点指针 }; 定义二叉树结构数据元素的类型DA
-
探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)
如有不足之处,还望指正! 复制代码 代码如下: // BinaryTree.cpp : 定义控制台应用程序的入口点.//C++实现链式二叉树,采用非递归的方式先序,中序,后序遍历二叉树#include "stdafx.h"#include<iostream>#include<string>#include <stack>using namespace std;template<class T>struct BiNode{ T data;
-
C++实现二叉树遍历序列的求解方法
本文详细讲述了C++实现二叉树遍历序列的求解方法,对于数据结构与算法的学习有着很好的参考借鉴价值.具体分析如下: 一.由遍历序列构造二叉树 如上图所示为一个二叉树,可知它的遍历序列分别为: 先序遍历:ABDECFG 中序遍历:DBEAFCG 后序遍历:DEBFGCA 我们需要知道的是,由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树:由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树:但是如果只知道先序序列和后序序列,则无法唯一确定一棵二叉树. 二.已知二叉树的先序序列和中序序列,求后序
-
c++二叉树的几种遍历算法
1. 前序/中序/后序遍历(递归实现) 复制代码 代码如下: // 前序遍历void BT_PreOrder(BiTreePtr pNode){ if (!pNode) return; visit(pNode); BT_PreOrder(pNode->left); BT_PreOrder(pNode->right); }// 中序遍历void BT_PreOrder(BiTreePtr pNode){ if (!pNode) return; BT_PreOrder(
-
二叉树遍历 非递归 C++实现代码
二叉树的非递归遍历 二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的.对于二叉树,有前序.中序以及后序三种遍历方法.因为树的定义本身就是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁.而对于树的遍历若采用非递归的方法,就要采用栈去模拟实现.在三种遍历中,前序和中序遍历的非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点. 一.前序遍历 前序遍历按照"根结点-左孩子-右孩子"的顺序进行访问. 1.递归实现 复制代码 代码
-
C++中用substr()函数消除前后空格的解决方法详解
最近做了个题目,遇到了要将字符串前后空格消除的细节问题.在Java中好像有一个字符串函数为trim()可以消除字符串后的空格.对于c++,查了一下,可以引用一个c++标准库Boost,可以轻松解决,但要下载,设置环境变量,因而没去弄.当然还可以用正则表达式进行匹配,但似乎都大材小用.不如就用substr()函数,而且string有find_last_not_of,find_first_not_of等等属性,已经够我们解决问题了. 复制代码 代码如下: #include <iostream> #
-
C++ 二叉搜索树(BST)的实现方法
废话不多说了,直接给大家贴代码了,具体代码如下所示: class BST { public: struct Node { int key;//节点的key int value;//节点的value Node* left; Node *right; int N;//节点的叶子节点数目 Node(int _key, int _value, int _N) { key = _key; value = _value; N = _N; } }; BST(); ~BST(); void put(int ke
-
Java删除二叉搜索树的任意元素的方法详解
本文实例讲述了Java删除二叉搜索树的任意元素的方法.分享给大家供大家参考,具体如下: 一.删除思路分析 在删除二叉搜索树的任意元素时,会有三种情况: 1.1 删除只有左孩子的节点 节点删除之后,将左孩子所在的二叉树取代其位置:连在原来节点父亲元素右节点的位置,比如在图中需要删除58这个节点. 删除58这个节点后,如下图所示: 1.2 删除只有右孩子的节点: 节点删除之后,将右孩子所在的二叉树取代其位置:连在原来节点的位置,比如在下图中需要删除58这个节点. 删除58这个节点后,如下图所示: 这
-
Python实现二叉搜索树BST的方法示例
二叉排序树(BST)又称二叉查找树.二叉搜索树 二叉排序树(Binary Sort Tree)又称二叉查找树.它或者是一棵空树:或者是具有下列性质的二叉树: 1.若左子树不空,则左子树上所有结点的值均小于根结点的值: 2.若右子树不空,则右子树上所有结点的值均大于根节点的值: 3.左.右子树也分别为二叉排序树. 求树深度 按序输出节点值(使用中序遍历) 查询二叉搜索树中一个具有给点关键字的结点,返回该节点的位置.时间复杂度是O(h),h是树的高度. 递归/迭代求最大关键字元素 递归/迭代求最小关
-
Python二叉搜索树与双向链表转换实现方法
本文实例讲述了Python二叉搜索树与双向链表实现方法.分享给大家供大家参考,具体如下: # encoding=utf8 ''' 题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表. 要求不能创建任何新的结点,只能调整树中结点指针的指向. ''' class BinaryTreeNode(): def __init__(self, value, left = None, right = None): self.value = value self.left = left self.
-
PHP实现绘制二叉树图形显示功能详解【包括二叉搜索树、平衡树及红黑树】
本文实例讲述了PHP实现绘制二叉树图形显示功能.分享给大家供大家参考,具体如下: 前言: 最近老师布置了一个作业:理解并实现平衡二叉树和红黑树,本来老师是说用C#写的,但是我学的C#基本都还给老师了,怎么办?那就用现在最熟悉的语言PHP来写吧! 有一个问题来了,书上在讲解树的时候基本上会给出形象的树形图.但是当我们自己试着实现某种树,在调试.输出的时候确只能以字符的形式顺序地输出.这给调试等方面带来了很大的不便.然后在各种百度之后,我发现利用PHP实现二叉树的图形显示的资源几乎是零!好吧,那我就
-
C语言判定一棵二叉树是否为二叉搜索树的方法分析
本文实例讲述了C语言判定一棵二叉树是否为二叉搜索树的方法.分享给大家供大家参考,具体如下: 问题 给定一棵二叉树,判定该二叉树是否是二叉搜索树(Binary Search Tree)? 解法1:暴力搜索 首先说明一下二叉树和二叉搜索树的区别.二叉树指这样的树结构,它的每个结点的孩子数目最多为2个:二叉搜索树是一种二叉树,但是它有附加的一些约束条件,这些约束条件必须对每个结点都成立: 结点node的左子树所有结点的值都小于node的值. 结点node的右子树所有结点的值都大于node的值. 结点n
-
Java二叉搜索树基础原理与实现方法详解
本文实例讲述了Java二叉搜索树基础原理与实现方法.分享给大家供大家参考,具体如下: 前言:本文通过先通过了解一些二叉树基础知识,然后在转向学习二分搜索树. 1 树 1.1 树的定义 树(Tree)是n(n>=0)个节点的有限集.n=0时称为空树.在任意一颗非空树中: (1)有且仅有一个特定的称为根(Root)的节点: (2)当n>1时,其余节点可分为m(m>0)个互不相交的有限集T1.T2........Tn,其中每一个集合本身又是一棵树,并且称为根的子树. 此外,树的定义还需要强调以
-
Java删除二叉搜索树最大元素和最小元素的方法详解
本文实例讲述了Java删除二叉搜索树最大元素和最小元素的方法.分享给大家供大家参考,具体如下: 在前面一篇<Java二叉搜索树遍历操作>中完成了树的遍历,这一节中将对如何从二叉搜索树中删除最大元素和最小元素做介绍: 我们要想删除二分搜索树的最小值和最大值,就需要先找到二分搜索树的最小值和最大值,其实也还是很容易的,因为根据二叉搜索树的特点,它的左子树一定比当前节点要小,所以二叉搜索树的最小值一定是左子树一直往下走,一直走到底.同样在二叉搜索树中,右子树节点值,一定比当前节点要大,所以右子树一直
-
javascript数据结构之二叉搜索树实现方法
本文实例讲述了javascript二叉搜索树实现方法.分享给大家供大家参考,具体如下: 二叉搜索树:顾名思义,树上每个节点最多只有二根分叉:而且左分叉节点的值 < 右分叉节点的值 . 特点:插入节点.找最大/最小节点.节点值排序 非常方便 二叉搜索树-javascript实现 <script type="text/javascript"> // <![CDATA[ //打印输出 function println(msg) { document.write(msg
-
C#创建二叉搜索树的方法
本文实例讲述了C#创建二叉搜索树的方法.分享给大家供大家参考.具体如下: public static BinaryTreeNode BuildBinarySearchTree(int[] sortedArray) { if (sortedArray.Length == 0) return null; int _mid = sortedArray.Length / 2; BinaryTreeNode _root = new BinaryTreeNode(sortedArray[_mid]); in