二叉查找树解析及其C++实现

BDplanDante 2017-01-21

介绍
二叉查找树，又称二叉搜索树、有序二叉树、排序二叉树。
它是特殊的二叉树，对于二叉树，假设x为二叉树中的任意一个结点，x结点包含关键字key，结点x的key值记为key[ x ]。如果y是x的左子树中的一个结点，则key[ y ] <= key[ x ]；如果y是x的右子树中的一个结点，则key[ y ] >= key[ x ]；那么，这棵树就是二叉查找树，如下图所示：

二叉查找树解析及其C++实现

二叉查找树具有以下性质：

1）若任意结点的左子树非空，则左子树上所有结点的值均小于它的根节点的值
2）若任意结点的右子树非空，则右子树上所有结点的值均大于它的根节点的值
3）任意结点的左、右子树叶分别为二叉查找树
4）没有键值相等的结点

算法实现
结点和二叉查找树的定义

template<class T>
class BSTNode
{
 public:
  T key; // 关键字（键值）
  BSTNode *left; // 左孩子
  BSTNode *right; // 右孩子
  BSTNode *parent; // 父结点
 
  BSTNode(T value, BSTNode *p, BSTNode *l, BSTNode *r):
   key(value),parent(p),left(l),right(r) {}
};

template<class T>
class BSTree
{
 private:
  BSTNode<T> *root; // 根结点
 
 public:
  BSTree(){};
  ~BSTree(){};
 
  // 前序遍历
  void preOrder();
  // 中序遍历
  void inOrder();
  // 后序遍历
  void postOrder();
 
  // （递归实现）查找二叉树中键值为key的结点
  BSTNode<T>* search(T key);
  // （非递归实现） 查找二叉树中键值为key的结点
  BSTNode<T>* iterativeSearch(T key);
 
  // 查找最小结点（返回键值）
  T minimum();
  // 查找最大结点（返回键值）
  T maximum();
 
  // 找结点（x）的后继结点。即查找二叉树中键值大于该结点的最小结点
  BSTNode<T>* successor(BSTNode<T> *x);
  // 找结点（x）的前驱结点。即查找二叉树中键值小于该结点的最大结点
  BSTNode<T>* predecessor(BSTNode<T> *x);
 
  // 将键值为key的结点插入到二叉树中
  void insert(T key);
 
  // 删除键值为key的结点
  void remove(T key);
 
  // 销毁二叉树
  void destroy();
 
  // 打印二叉树
  void print();
 
 private:
  // 重载函数，提供内部接口
  // 前序遍历
  void preOrder(BSTNode<T> *tree) const;
  // 中序遍历
  void inOrder(BSTNode<T> *tree) const;
  // 后序遍历
  void postOrder(BSTNode<T> *tree) const;
 
  // （递归实现）查找二叉树中键值为key的结点
  BSTNode<T>* search(BSTNode<T> *x, T key) const;
  // （非递归实现） 查找二叉树中键值为key的结点
  BSTNode<T>* iterativeSearch(BSTNode<T> *x, T key) const;
 
  // 查找最小结点（返回键值）
  BSTNode<T>* minimum(BSTNode<T> *tree);
  // 查找最大结点（返回键值）
  BSTNode<T>* maximum(BSTNode<T> *tree);
 
  // 将结点z插入到二叉树tree中
  void insert(BSTNode<T>* &tree, BSTNode<T> *z);
 
  // 删除二叉树中的结点z，并返回该结点
  BSTNode<T>* remove(BSTNode<T>* &tree, BSTNode<T> *z);
 
  // 销毁二叉树
  void destroy(BSTNode<T>* &tree);
 
  // 打印二叉树
  void print(BSTNode<T>* &tree, T key, int direction);
};

遍历

前序遍历

template<class T>
void BSTree<T>::preOrder(BSTNode<T> *tree) const
{
 if(tree!=NULL)
 {
  cout<<tree->key<<" ";
  preOrder(tree->left);
  preOrder(tree->right);
 }
}

template<class T>
void BSTree<T>::preOrder()
{
 preOrder(root);
}

中序遍历

template<class T>
void BSTree<T>::inOrder(BSTNode<T> *tree) const
{
 if(tree!=NULL)
 {
  inOrder(tree->left);
  cout<<tree->key<<" ";
  inOrder(tree->right);
 }
}

template<class T>
void BSTree<T>::inOrder()
{
 inOrder(root);
}

后序遍历

template<class T>
void BSTree<T>::postOrder(BSTNode<T> *tree) const
{
 if(tree!=NULL)
 {
  postOrder(tree->left);
  postOrder(tree->right);
  cout<<tree->key<<" ";
 }
}

template<class T>
void BSTree<T>::postOrder()
{
 postOrder(root);
}

查找

递归方式进行查找

template<class T>
BSTNode<T>* BSTree<T>::search(BSTNode<T>* x, T key) const
{
 if(x==NULL || x->key==key)
  return x;
 if(key<x->key)
  search(x->left, key);
 else
  search(x->right, key);
}

template<class T>
BSTNode<T>* BSTree<T>::search(T key)
{
 search(root, key);
}

非递归方式进行查找

template<class T>
BSTNode<T>* BSTree<T>::interativeSearch(BSTNode<T>* x, T key) const
{
 while(x!=NULL && x->key!=key)
 {
  if(key<x->key)
   x = x->left;
  else
   x = x->right;
 }
 return x;
}

template<class T>
BSTNode<T>* BSTree<T>::interativeSearch(T key)
{
 interativeSearch(root, key);
}

最大值和最小值

查找最大值

template<class T>
BSTNode<T>*  BSTree<T>::maximum(BSTNode<T> *tree)
{
 if(tree==NULL)
  return NULL;
 while(tree->right!=NULL)
  tree = tree->right;
 return tree;
}

template<class T>
T BSTree<T>::maximum()
{
 BSTNode<T> *p = maximum(root);
 if(p!=NULL)
  return p->key;
 return (T)NULL;
}

查找最小值

template<class T>
BSTNode<T>*  BSTree<T>::minimum(BSTNode<T> *tree)
{
 if(tree==NULL)
  return NULL;
 while(tree->left!=NULL)
  tree = tree->left;
 return tree;
}

template<class T>
T BSTree<T>::minimum()
{
 BSTNode<T> *p = minimum(root);
 if(p!=NULL)
  return p->key;
 return (T)NULL;
}

前驱和后继

查找前驱

template<class T>
BSTNode<T>* BSTree<T>::predecessor(BSTNode<T> *x)
{
 // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
 if(x->left!=NULL)
  return maximum(x->left);
 // 如果x没有左孩子。则x有以下两种可能：
    // (1) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
    // (2) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
    BSTNode<T> *p = x->parent;
    while(p!=NULL && x==p->left)
    {
     x = p;
     p = p->parent;
 }
 return p;
}

查找后继

template<class T>
BSTNode<T>* BSTree<T>::successor(BSTNode<T> *x)
{
 // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
 if(x->right!=NULL)
  return minimum(x->right);
 // 如果x没有右孩子。则x有以下两种可能：
    // (1) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
    // (2) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
    BSTNode<T> *p = x->parent;
    while(p!=NULL && x==p->right)
    {
     x = p;
     p = p->parent;
 }
 return p;
}

插入

template<class T>
void BSTree<T>::insert(BSTNode<T>* &tree, BSTNode<T> *z)
{
 BSTNode<T> *y = NULL;
 BSTNode<T> *x = tree;
 
 // 查找z的插入位置
 while(x!=NULL)
 {
  y = x;
  if(z->key < x->key)
   x = x->left;
  else // else if(z->key > x->key)
   x = x->right;
//  若禁止插入相同键值
//  else
//  {
//   free(z)；// 释放之前分配的结点
//   return;
//  }
 }
 z->parent = y;
 if(y==NULL)
  tree = z;
 else if(z->key<y->key)
  y->left = z;
 else
  y->right = z;
}

template<class T>
void BSTree<T>::insert(T key)
{
 BSTNode<T> *z = NULL;
 
 // 如果新建结点失败，则返回
 if((z=new BSTNode<T>(key,NULL,NULL,NULL))==NULL)
  return;
 
 insert(root,z);
}

删除

template<class T>
BSTNode<T>* BSTree<T>::remove(BSTNode<T>* &tree, BSTNode<T> *z)
{
 BSTNode<T> *x = NULL;
 BSTNode<T> *y = NULL;
 
 if(z->left==NULL || z->right==NULL)
  y = z;
 else
  y = successor(z);
 
 if(y->left!=NULL)
  x = y->left;
 else
  x = y->right;
 
 if(x!=NULL)
  x->parent = y->parent;
 
 if(y->parent==NULL)
  tree = x;
 else if(y==y->parent->left)
  y->parent->left = x;
 else
  y->parent->right = x;
 
 if(y!=z)
  z->key = y->key;
 return y;
}

template<class T>
void BSTree<T>::remove(T key)
{
 BSTNode<T> *z, *node;
 
 if((z=search(root,key))!=NULL)
  if((node=remove(root,z))!=NULL)
   delete node;
}

打印

template<class T>
void BSTree<T>::print(BSTNode<T> *tree, T key, int direction)
{
 if(tree!=NULL)
 {
  if(direction==0)
   cout<<setw(2)<<tree->key<<"is root"<<endl;
  else
   cout<<setw(2)<<tree->key<<"is"<<setw(2)<<key<<"'s"<<setw(12)<<(direction==1 ? "right child":"left child")<<endl;
  print(tree->left,tree->key,-1);
  print(tree->right,tree->key,1);
 }
}

template<class T>
void BSTree<T>::print()
{
 if(root!=NULL)
  print(root,root->key,0);
}

销毁

template<class T>
void BSTree<T>::destroy(BSTNode<T> *&tree)
{
 if(tree==NULL)
  return ;
 if(tree->left!=NULL)
  return destroy(tree->left);
 if(tree->right!=NULL)
  return destroy(tree->right);
 
 delete tree;
 tree=NULL;
}

template<class T>
void BSTree<T>::destroy()
{
 destroy(root);
}

二叉查找树完整实现：BSTree.h

#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE

#include<iomanip>
#include<iostream>
using namespace std;

template<class T>
class BSTNode
{
 public:
  T key; // 关键字（键值）
  BSTNode *left; // 左孩子
  BSTNode *right; // 右孩子
  BSTNode *parent; // 父结点
 
  BSTNode(T value, BSTNode *p, BSTNode *l, BSTNode *r):
   key(value),parent(p),left(l),right(r) {}
};

template<class T>
class BSTree
{
 private:
  BSTNode<T> *root; // 根结点
 
 public:
  BSTree() {};
  ~BSTree() {};
 
  // 前序遍历
  void preOrder();
  // 中序遍历
  void inOrder();
  // 后序遍历
  void postOrder();
 
  // （递归实现）查找二叉树中键值为key的结点
  BSTNode<T>* search(T key);
  // （非递归实现） 查找二叉树中键值为key的结点
  BSTNode<T>* iterativeSearch(T key);
 
  // 查找最小结点（返回键值）
  T minimum();
  // 查找最大结点（返回键值）
  T maximum();
 
  // 找结点（x）的后继结点。即查找二叉树中键值大于该结点的最小结点
  BSTNode<T>* successor(BSTNode<T> *x);
  // 找结点（x）的前驱结点。即查找二叉树中键值小于该结点的最大结点
  BSTNode<T>* predecessor(BSTNode<T> *x);
 
  // 将键值为key的结点插入到二叉树中
  void insert(T key);
 
  // 删除键值为key的结点
  void remove(T key);
 
  // 销毁二叉树
  void destroy();
 
  // 打印二叉树
  void print();
 
 private:
  // 重载函数，提供内部接口
  // 前序遍历
  void preOrder(BSTNode<T> *tree) const;
  // 中序遍历
  void inOrder(BSTNode<T> *tree) const;
  // 后序遍历
  void postOrder(BSTNode<T> *tree) const;
 
  // （递归实现）查找二叉树中键值为key的结点
  BSTNode<T>* search(BSTNode<T> *x, T key) const;
  // （非递归实现） 查找二叉树中键值为key的结点
  BSTNode<T>* iterativeSearch(BSTNode<T> *x, T key) const;
 
  // 查找最小结点（返回键值）
  BSTNode<T>* minimum(BSTNode<T> *tree);
  // 查找最大结点（返回键值）
  BSTNode<T>* maximum(BSTNode<T> *tree);
 
  // 将结点z插入到二叉树tree中
  void insert(BSTNode<T>* &tree, BSTNode<T> *z);
 
  // 删除二叉树中的结点z，并返回该结点
  BSTNode<T>* remove(BSTNode<T>* &tree, BSTNode<T> *z);
 
  // 销毁二叉树
  void destroy(BSTNode<T>* &tree);
 
  // 打印二叉树
  void print(BSTNode<T>* &tree, T key, int direction);
};

template<class T>
void BSTree<T>::preOrder(BSTNode<T> *tree) const
{
 if(tree!=NULL)
 {
  cout<<tree->key<<" ";
  preOrder(tree->left);
  preOrder(tree->right);
 }
}

template<class T>
void BSTree<T>::preOrder()
{
 preOrder(root);
}

template<class T>
void BSTree<T>::inOrder(BSTNode<T> *tree) const
{
 if(tree!=NULL)
 {
  inOrder(tree->left);
  cout<<tree->key<<" ";
  inOrder(tree->right);
 }
}

template<class T>
void BSTree<T>::inOrder()
{
 inOrder(root);
}

template<class T>
void BSTree<T>::postOrder(BSTNode<T> *tree) const
{
 if(tree!=NULL)
 {
  postOrder(tree->left);
  postOrder(tree->right);
  cout<<tree->key<<" ";
 }
}

template<class T>
void BSTree<T>::postOrder()
{
 postOrder(root);
}

template<class T>
BSTNode<T>* BSTree<T>::search(BSTNode<T>* x, T key) const
{
 if(x==NULL || x->key==key)
  return x;
 if(key<x->key)
  return search(x->left, key);
 else
  return search(x->right, key);
}

template<class T>
BSTNode<T>* BSTree<T>::search(T key)
{
 search(root, key);
}

template<class T>
BSTNode<T>* BSTree<T>::iterativeSearch(BSTNode<T>* x, T key) const
{
 while(x!=NULL && x->key!=key)
 {
  if(key<x->key)
   x = x->left;
  else
   x = x->right;
 }
 return x;
}

template<class T>
BSTNode<T>* BSTree<T>::iterativeSearch(T key)
{
 iterativeSearch(root, key);
}

template<class T>
BSTNode<T>*  BSTree<T>::maximum(BSTNode<T> *tree)
{
 if(tree==NULL)
  return NULL;
 while(tree->right!=NULL)
  tree = tree->right;
 return tree;
}

template<class T>
T BSTree<T>::maximum()
{
 BSTNode<T> *p = maximum(root);
 if(p!=NULL)
  return p->key;
 return (T)NULL;
}

template<class T>
BSTNode<T>*  BSTree<T>::minimum(BSTNode<T> *tree)
{
 if(tree==NULL)
  return NULL;
 while(tree->left!=NULL)
  tree = tree->left;
 return tree;
}

template<class T>
T BSTree<T>::minimum()
{
 BSTNode<T> *p = minimum(root);
 if(p!=NULL)
  return p->key;
 return (T)NULL;
}

template<class T>
BSTNode<T>* BSTree<T>::predecessor(BSTNode<T> *x)
{
 // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
 if(x->left!=NULL)
  return maximum(x->left);
 // 如果x没有左孩子。则x有以下两种可能：
    // (1) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
    // (2) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
    BSTNode<T> *p = x->parent;
    while(p!=NULL && x==p->left)
    {
     x = p;
     p = p->parent;
 }
 return p;
}

template<class T>
BSTNode<T>* BSTree<T>::successor(BSTNode<T> *x)
{
 // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
 if(x->right!=NULL)
  return minimum(x->right);
 // 如果x没有右孩子。则x有以下两种可能：
    // (1) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
    // (2) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
    BSTNode<T> *p = x->parent;
    while(p!=NULL && x==p->right)
    {
     x = p;
     p = p->parent;
 }
 return p;
}

template<class T>
void BSTree<T>::insert(BSTNode<T>* &tree, BSTNode<T> *z)
{
 BSTNode<T> *y = NULL;
 BSTNode<T> *x = tree;
 
 // 查找z的插入位置
 while(x!=NULL)
 {
  y = x;
  if(z->key < x->key)
   x = x->left;
  else // else if(z->key > x->key)
   x = x->right;
//  若禁止插入相同键值
//  else
//  {
//   free(z)；// 释放之前分配的结点
//   return;
//  }
 }
 z->parent = y;
 if(y==NULL)
  tree = z;
 else if(z->key<y->key)
  y->left = z;
 else
  y->right = z;
}

template<class T>
void BSTree<T>::insert(T key)
{
 BSTNode<T> *z = NULL;
 
 // 如果新建结点失败，则返回
 if((z=new BSTNode<T>(key,NULL,NULL,NULL))==NULL)
  return;
 
 insert(root,z);
}

template<class T>
BSTNode<T>* BSTree<T>::remove(BSTNode<T>* &tree, BSTNode<T> *z)
{
 BSTNode<T> *x = NULL;
 BSTNode<T> *y = NULL;
 
 if(z->left==NULL || z->right==NULL)
  y = z;
 else
  y = successor(z);
 
 if(y->left!=NULL)
  x = y->left;
 else
  x = y->right;
 
 if(x!=NULL)
  x->parent = y->parent;
 
 if(y->parent==NULL)
  tree = x;
 else if(y==y->parent->left)
  y->parent->left = x;
 else
  y->parent->right = x;
 
 if(y!=z)
  z->key = y->key;
 return y;
}

template<class T>
void BSTree<T>::remove(T key)
{
 BSTNode<T> *z, *node;
 
 if((z=search(root,key))!=NULL)
  if((node=remove(root,z))!=NULL)
   delete node;
}

template<class T>
void BSTree<T>::print(BSTNode<T> *&tree, T key, int direction)
{
 if(tree!=NULL)
 {
  if(direction==0)
   cout<<setw(2)<<tree->key<<"is root"<<endl;
  else
   cout<<setw(2)<<tree->key<<"is"<<setw(2)<<key<<"'s"<<setw(12)<<(direction==1 ? "right child":"left child")<<endl;
  print(tree->left,tree->key,-1);
  print(tree->right,tree->key,1);
 }
}

template<class T>
void BSTree<T>::print()
{
 if(root!=NULL)
  print(root,root->key,0);
}

template<class T>
void BSTree<T>::destroy(BSTNode<T> *&tree)
{
 if(tree==NULL)
  return ;
 if(tree->left!=NULL)
  return destroy(tree->left);
 if(tree->right!=NULL)
  return destroy(tree->right);
 
 delete tree;
 tree=NULL;
}

template<class T>
void BSTree<T>::destroy()
{
 destroy(root);
}

#endif

测试代码：BSTreeTest.cpp

#include<iostream>
#include "BSTree.h"
using namespace std;

static int arr[] = {1,5,4,3,2,6};

int main()
{
 int i,len;
 BSTree<int> *tree = new BSTree<int>();
 
 cout<<"依次添加：";
 len = sizeof(arr)/sizeof(arr[0]);
 for(i=0;i<len;++i)
 {
  cout<<arr[i]<<" ";
  tree->insert(arr[i]);
 }
 
 cout<<"\n前序遍历：";
 tree->preOrder();
 cout<<"\n中序遍历：";
 tree->inOrder();
 cout<<"\n后序遍历：";
 tree->postOrder();
 cout<<endl;
 
 cout<<"最小值："<<tree->minimum()<<endl;
 cout<<"最大值："<<tree->maximum()<<endl;
 cout<<"树的详细信息："<<endl;
 tree->print();
 
 cout<<" \n删除根节点："<<arr[3];
 tree->remove(arr[3]);
 
 cout<<"\n中序遍历：";
 tree->inOrder();
 cout<<endl;
 
 // 销毁二叉树
 tree->destroy();

 return 0;
}

BDplanDante

BDplanDante

相关推荐

python实现二叉查找树

# 以列表作为底层存储。# 初始化内置list，并将索引reset. # 若key=sub_tree的key ,替换value. # 如果树为空，则将新建节点并返回，若key小于根节点，则递归插入左子树，key大于根节点，递归插入右子树

yawei / 0评论 2020-06-12

数据结构--二叉查找树

　　比如要在上图查找结点值为4的节点，从根节点开始→4小于8，则查找左子树→4大于3，则查找右子树→4小于6，则查找左子树→查找成功。　　2.在最好的情况下，二叉查找树的N个节点是平衡的，最差时，二叉查找树退化为链表

shenwenjie / 0评论 2020-06-04

数据结构与算法之美_25_红黑树（上）：为什么工程中都用红黑树这种二叉树？

二叉查找树是最常用的一种二叉树，它支持快速插入、删除、查找操作，各个操作的时间复杂度跟树的高度成正比，理想情况下，时间复杂度是 O。不过，二叉查找树在频繁的动态更新过程中，可能会出现数的高度远大于 log2^n 的情况，从而导致各个操作的效率下降。在工程中

lickylin / 0评论 2020-04-22

看懂这篇文章，玩转二叉查找树

大家好，我是鸭血粉丝，拼着头发掉光的风险给大家总结了这篇文章，我愿拿我明年的今天还是单身来祝愿你们能学会～。所谓二叉查找树，就是按照二分进行查找，每次查询只需要选择其中一个子树就进行查找，从而减少查找次数，提升查询效率!在前面的文章中，我们对树这种数据结构

Wofficre / 0评论 2020-02-14

《深入浅出话数据结构》系列之什么是B树、B+树？为什么二叉查找树不行？

本文将为大家介绍B树和B+树，首先介绍了B树的应用场景，为什么需要B树；然后介绍了B树的查询和插入过程；最后谈了B+树针对B树的改进。B树是一种为辅助存储设计的一种数据结构，普遍运用在数据库和文件系统中。大家的第一反应肯定是二叉查找树，下面先谈谈为什么二叉

ipqtjmqj / 0评论 2020-01-18

LeetCode 二叉查找树（BST)

root->left=insertIntoBST;//必须是这样，不能是insertIntoBST(). 既然确定使用递归，那么接下来就应该考虑具体的实现问题了。基本条件/终止条件 - 返回值需斟酌。递归步/条件递归 - 能使原始问题收敛。有了递归步

ustbfym / 0评论 2019-12-29

Mysql索引——B-Tree/B+Tree架构

在进一步分析为什么MySQL数据库索引选择使用B+树之前，我相信很多小伙伴对数据结构中的树还是有些许模糊的，因此我们由浅入深一步步探讨树的演进过程，在一步步引出B树以及为什么MySQL数据库索引选择使用B+树！学过数据结构的一般对最基础的树都有所认识，因此

逍遥斩舞 / 0评论 2019-12-27

MySQL索引-B+树（看完你就明白了）

索引是一种数据结构，用于帮助我们在大量数据中快速定位到我们想要查找的数据。索引最形象的比喻就是图书的目录了。注意这里的大量，数据量大了索引才显得有意义，如果我想要在 [1,2,3,4] 中找到 4 这个数据，直接对全数据检索也很快，没有必要费力气建索引再去

vivenwan / 0评论 2019-12-23

查找算法——二叉查找树

　　二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低,为O。中序遍历二叉查找树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉查找树变成一个有序序列，构造树的过程即将无序序列中元素逐个插入到二叉查找树的过程。

darlingtangli / 0评论 2019-06-28

数据结构-二叉树和二叉查找树

二叉树和二叉查找树正如前面提到的那样, 二叉树 每一个节点的子节点不允许超过两个. 通过将子节点的个数限定为2, 可以写出高效的程序在树中插入、查找和删除数据.其次检查BST是否有根节点, 如果没有, 那么这是棵新树, 该节点就是根节点, 这个方法到此也就

lickylin / 0评论 2019-06-28

JavaScript实现简单二叉查找树

前两天接到了蚂蚁金服的面试电话，面试官很直接，上来就抛出了三道算法题。。。其中有一道关于二叉树实现中序遍历的，当时没回答好，所以特意学习了一把二叉树的知识，行文记录总结。官方语言的定义是：是一个有限元素的集合,该集合或者为空、或者由一个称为根的元素及两个不

郭岚 / 0评论 2019-06-28

AVL平衡二叉树详解与实现

本文从属于笔者的数据结构与算法系列文章。因此，我们希望最理想的状态下是使二叉查找树始终处于良好的结构形态。1962年，Adelson-Velsikii和Landis提出了一种结点在高度上相对平衡的二叉查找树，又称为AVL树。

dushine00 / 0评论 2019-06-20

JavaScript数据结构之二叉查找树的定义与表示方法

本文实例讲述了JavaScript数据结构之二叉查找树的定义与表示方法。分享给大家供大家参考，具体如下：。树的节点包含一个数据元素及若干指向其子树的分支。结点拥有的子树称为结点的度。树中结点的最大层次称为树的深度或高度。二叉树具有一些特殊的计算性质，使得在

rainsnowing / 0评论 2017-04-12

数据结构之二叉查找树Java实现源码及注释

二叉查找树，它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。//首先定义一个BNode节点，里

Annihilation / 0评论 2018-12-11

js代码实现二叉查找树的算法

理论二叉查找树，又称二叉排序树或二叉搜索树，是属于二叉树的一种。它最大的特点是每个节点的左子节点永远比该节点小，而每个节点的右子节点却永远比该节点大，即任意节点的左子树上所有结点永远比该节点的右子树上所有结点的值小，它的任意左、右子树也分别为二叉查找树。代

wangxiaohua / 0评论 2017-03-15

python实现二叉查找树实例代码

本文研究的主要是python实现二叉查找树的相关内容，具体介绍及实现如下。左子树不为空的时候，左子树的结点值小于根节点，右子树不为空时，右子树的结点值大于根节点，左右子树分别为二叉查找树。如果结点S的左孩子或者右孩子为空，可以直接删除这个结点S。

pyphrb / 0评论 2018-02-08

AVL树-自平衡二叉查找树(Java实现)

在计算机科学中，AVL树是最先发明的自平衡二叉查找树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 "An algorithm for the organization

明明蠢萌的夏木君 / 0评论 2014-06-08

为什么MySQL数据库索引选择使用B+树?

在进一步分析为什么MySQL数据库索引选择使用B+树之前，我相信很多小伙伴对数据结构中的树还是有些许模糊的，因此我们由浅入深一步步探讨树的演进过程，在一步步引出B树以及为什么MySQL数据库索引选择使用B+树！学过数据结构的一般对最基础的树都有所认识，因此

数据库成长之路 / 0评论 2019-04-18

【算法导论】二叉查找树的操作C++实现

=NULL) { returnt->node_value; } else { return-1; } } Tree*TreeMinimum { if { returnp; } TreeMin

mal / 0评论 2012-10-15

浅谈AVL树,红黑树,B树,B+树原理及应用

看完这篇文章你就会了解到这些数据结构的原理以及它们各自的应用场景., K[M-1]；且K[i] < K[i+1]；非叶子结点的指针：P[1], P[2], …

松鼠的窝 / 0评论 2018-04-23

算法：二叉查找树进阶[TEMP]

</strong>　　//中序遍历，可以将二叉树从小到达排列出来！

松鼠的窝 / 0评论 2018-02-13

算法：二叉查找树进阶

</strong>　　//中序遍历，可以将二叉树从小到达排列出来！

松鼠的窝 / 0评论 2018-02-13