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)的实现方法,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对我们网站的支持!

时间: 2017-04-17

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++实现二叉树遍历序列的求解方法

本文详细讲述了C++实现二叉树遍历序列的求解方法,对于数据结构与算法的学习有着很好的参考借鉴价值.具体分析如下: 一.由遍历序列构造二叉树 如上图所示为一个二叉树,可知它的遍历序列分别为: 先序遍历:ABDECFG 中序遍历:DBEAFCG 后序遍历:DEBFGCA 我们需要知道的是,由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树:由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树:但是如果只知道先序序列和后序序列,则无法唯一确定一棵二叉树. 二.已知二叉树的先序序列和中序序列,求后序

探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)

如有不足之处,还望指正! 复制代码 代码如下: // BinaryTree.cpp : 定义控制台应用程序的入口点.//C++实现链式二叉树,采用非递归的方式先序,中序,后序遍历二叉树#include "stdafx.h"#include<iostream>#include<string>#include <stack>using namespace std;template<class T>struct BiNode{ T data; 

二叉树遍历 非递归 C++实现代码

二叉树的非递归遍历 二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的.对于二叉树,有前序.中序以及后序三种遍历方法.因为树的定义本身就是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁.而对于树的遍历若采用非递归的方法,就要采用栈去模拟实现.在三种遍历中,前序和中序遍历的非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点. 一.前序遍历 前序遍历按照"根结点-左孩子-右孩子"的顺序进行访问. 1.递归实现 复制代码 代码

C++中用substr()函数消除前后空格的解决方法详解

最近做了个题目,遇到了要将字符串前后空格消除的细节问题.在Java中好像有一个字符串函数为trim()可以消除字符串后的空格.对于c++,查了一下,可以引用一个c++标准库Boost,可以轻松解决,但要下载,设置环境变量,因而没去弄.当然还可以用正则表达式进行匹配,但似乎都大材小用.不如就用substr()函数,而且string有find_last_not_of,find_first_not_of等等属性,已经够我们解决问题了. 复制代码 代码如下: #include <iostream> #

C++二叉树结构的建立与基本操作

准备数据定义二叉树结构操作中需要用到的变量及数据等. 复制代码 代码如下: #define MAXLEN 20    //最大长度typedef char DATA;    //定义元素类型struct  CBTType                   //定义二叉树结点类型 { DATA data;           //元素数据  CBTType * left;    //左子树结点指针  CBTType * right;   //右子树结点指针 }; 定义二叉树结构数据元素的类型DA

C语言数据结构 双向链表的建立与基本操作

C语言数据结构 双向链表的建立与基本操作 双向链表比单链表有更好的灵活性,其大部分操作与线性表相同.下面总结双向链表与单链表之间的不同之处及我在实现过程中所遇到的问题. 1.双向链表的建立 双向链表在初始化时,要给首尾两个节点分配内存空间.成功分配后,要将首节点的prior指针和尾节点的next指针指向NULL,这是十分关键的一步,因为这是之后用来判断空表的条件.同时,当链表为空时,要将首节点的next指向尾节点,尾节点的prior指向首节点. 2.双向链表的插入操作 由于定义双向链表时指针域中

C++基于递归和非递归算法判定两个二叉树结构是否完全相同(结构和数据都相同)

本文实例讲述了C++基于递归和非递归算法判定两个二叉树结构是否完全相同.分享给大家供大家参考,具体如下: /*两个二叉树结构是否相同(结构和数据都相同) -- 递归和非递归方法 经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <queue> using std::cout; using std::cin; using std::endl; using std::queue; /*二

Python数据结构与算法之二叉树结构定义与遍历方法详解

本文实例讲述了Python数据结构与算法之二叉树结构定义与遍历方法.分享给大家供大家参考,具体如下: 先序遍历,中序遍历,后序遍历 ,区别在于三条核心语句的位置 层序遍历  采用队列的遍历操作第一次访问根,在访问根的左孩子,接着访问根的有孩子,然后下一层 自左向右一一访问同层的结点 # 先序遍历 # 访问结点,遍历左子树,如果左子树为空,则遍历右子树, # 如果右子树为空,则向上走到一个可以向右走的结点,继续该过程 preorder(t): if t: print t.value preorde

Python 二叉树的层序建立与三种遍历实现详解

前言 二叉树(Binary Tree)时数据结构中一个非常重要的结构,其具有....(此处省略好多字)....等的优良特点. 之前在刷LeetCode的时候把有关树的题目全部跳过了,(ORZ:我这种连数据结构都不会的人刷j8Leetcode啊!!!) 所以 !!!敲黑板了!!!今天我就在B站看了数据结构中关于树的内容后,又用我浅薄的Python大法来实现一些树的建立和遍历. 关于树的建立我觉得层序建立对于使用者来说最为直观,输入很好写.(好吧,我是看LeetCode中的树输入都是采用层序输入觉得

Python实现二叉树结构与进行二叉树遍历的方法详解

二叉树的建立 使用类的形式定义二叉树,可读性更好 class BinaryTree: def __init__(self, root): self.key = root self.left_child = None self.right_child = None def insert_left(self, new_node): if self.left_child == None: self.left_child = BinaryTree(new_node) else: t = BinaryTr

C++中单链表的建立与基本操作

准备数据 准备在链表操作中需要用到的变量及数据结构 示例代码如下: 复制代码 代码如下: struct Data   //数据结点类型 { string key;  //关键字  string name; int age;};struct CLType  //定义链表结构 { Data nodeData; Data *nextNode;}; 定义了链表数据元素的类型Data以及链表的数据结构CLType.结点的具体数据保存在一个结构Data中,而指针nextNode用来指向下一个结点. 我们可以

C++二叉树实现词频分析功能

通过二叉树存单词,并且对总共的单词数量进行计数,二叉树自适应的将出现频率高的单词往上移动以减少二叉树的搜索时间. 代码如下 /***********************genSplay.h***********************/ #ifndef _GENSPLAY_H_ #define _GENSPLAY_H_ #include <iostream> using namespace std; //树节点 template<class T> class SplayingN

Python简单定义与使用二叉树示例

本文实例讲述了Python简单定义与使用二叉树的方法.分享给大家供大家参考,具体如下: class BinaryTree: def __init__(self,rootObj): self.root = rootObj self.leftChild = None self.rightChild = None def insertLeft(self,newNode): if self.leftChild == None: self.leftChild = BinaryTree(newNode) e

使用C语言构建基本的二叉树数据结构

二叉树结构常用的一些初始化代码 #include #include typedef struct Node{ int data; Node *leftchild; Node *rightchild; }Node; /* 初始化一棵二叉树排序树. */ void InitBinaryTree(Node**root,int elem) { *root=(Node*)malloc(sizeof(Node)); if(!(*root)) { printf("Memory allocation for r