二叉搜索树源码分享_C 语言

复制代码 代码如下:

#include <iostream>
using namespace std;

//枚举类，前中后三种遍历方式
enum ORDER_MODE
{
 ORDER_MODE_PREV = 0,
 ORDER_MODE_MID,
 ORDER_MODE_POST
};

//树节点的结构体
template <class T>
struct BinaryNode
{
 T    element;
 BinaryNode  *left;
 BinaryNode  *right;

 BinaryNode(const T& theElement,
  BinaryNode *lt,
  BinaryNode *rt):
 element(theElement),
  left(lt),
  right(rt)
 {

 }
};

template <class T>
class BinarySearchTree
{
private:

 BinaryNode<T>   *m_root;

public:
 BinarySearchTree();
 BinarySearchTree(const BinarySearchTree& rhs);
 ~BinarySearchTree();

 const T& findMin() const;
 const T& findMax() const;
 bool contains(const T& x) const;
 void printTree(ORDER_MODE eOrderMode = ORDER_MODE_PREV) const;

 void makeEmpty();
 void insert(const T& x);
 void remove(const T& x);

private:
 void insert(const T& x, BinaryNode<T>* &t) ;
 void remove(const T& x, BinaryNode<T>* &t) ;
 BinaryNode<T>* findMin( BinaryNode<T>* t) const;
 BinaryNode<T>* findMax( BinaryNode<T>* t) const;
 bool contains(const T& x, const BinaryNode<T>* t) const;
 void makeEmpty(BinaryNode<T>* &t);
 void printTreeInPrev(BinaryNode<T>* t) const;
 void printTreeInMid(BinaryNode<T>* t)const;
 void printTreeInPost(BinaryNode<T>* t)const;
};

//构造方法
template <class T>
BinarySearchTree<T>::BinarySearchTree()
{
 m_root = NULL;
}

//使用另一棵二叉搜索树的构造函数
template <class T>
BinarySearchTree<T>:: BinarySearchTree(const BinarySearchTree& rhs)
{
 m_root = rhs.m_root;
}

//析构函数，释放内存
template <class T>
BinarySearchTree<T>:: ~BinarySearchTree()
{
 makeEmpty();
}

// 判断x元素是否存在
template <class T>
bool  BinarySearchTree<T>::contains(const T& x) const
{
 return contains(x, m_root);
}

//递归调用
template <class T>
bool BinarySearchTree<T>::contains(const T& x, const BinaryNode<T>* t) const
{
 if (!t)
  return false;
 else if (x < t->element)
  return contains(x, t->left);
 else if (x > t->element)
  return contains(x, t->right);
 else
  return true;
}

// 寻找树中的最小值
template <class T>
const T& BinarySearchTree<T>::findMin() const
{
 return findMin(m_root)->element;
}

//递归搜索树中最小值
template <class T>
BinaryNode<T>* BinarySearchTree<T>::findMin( BinaryNode<T>* t) const
{
 //二叉树的一个特点就是左子叶的值比根节点小， 右子叶的比根节点的大
 if (!t)
  return NULL;
 if (t->left == NULL)
  return t;
 else
  return findMin(t->left);
}

// 寻找树中最大值
template <class T>
const T& BinarySearchTree<T>::findMax() const
{
 return findMax(m_root)->element;
}

//递归寻找树中最大值
template <class T>
BinaryNode<T>* BinarySearchTree<T>::findMax( BinaryNode<T>* t) const
{
 //二叉树的一个特点就是左子叶的值比根节点小， 右子叶的比根节点的大
 if (t != NULL)
  while (t->right != NULL)
   t = t->right;
 return t;
}

// 插入元素
template <class T>
void BinarySearchTree<T>:: insert(const T& x)
{
 insert(x, m_root);
}

//递归插入
template <class T>
void BinarySearchTree<T>::insert(const T& x, BinaryNode<T>* &t)
{
 if (t == NULL)
  t = new BinaryNode<T>(x, NULL, NULL);//注意这个指针参数是引用
 else if (x < t->element)
  insert(x, t->left);
 else if (x > t->element)
  insert(x, t->right);
 else
  ;//do nothing
}

//移除元素
template <class T>
void BinarySearchTree<T>::remove(const T& x)
{
 return remove(x, m_root);
}

//递归移除
template <class T>
void BinarySearchTree<T>::remove(const T& x, BinaryNode<T>* &t)
{
 if (t == NULL)
  return;
 if (x < t->element)
  remove(x, t->left);
 else if (x > t->element)
  remove (x, t->right);
 else // now ==
 {
  if (t->left != NULL &&
   t->right != NULL)//two child
  {
   t->element = findMin(t->right)->element;
   remove(t->element, t->right);
  }
  else
  {
   BinaryNode<T> *oldNode = t;
   t = (t->left != NULL) ? t->left : t->right;
   delete oldNode;
  }
 }
}

//清空二叉树
template <class T>
void  BinarySearchTree<T>::makeEmpty()
{
 makeEmpty(m_root);
}

//递归清空
template <class T>
void  BinarySearchTree<T>::makeEmpty(BinaryNode<T>* &t)
{
 if (t)
 {
  makeEmpty(t->left);
  makeEmpty(t->right);
  delete t;
 }
 t = NULL;
}

// 打印二叉搜索树
template <class T>
void BinarySearchTree<T>::printTree(ORDER_MODE eOrderMode /*= ORDER_MODE_PREV*/) const
{
 if (ORDER_MODE_PREV == eOrderMode)
  printTreeInPrev(m_root);
 else if (ORDER_MODE_MID == eOrderMode)
  printTreeInMid(m_root);
 else if (ORDER_MODE_POST == eOrderMode)
  printTreeInPost(m_root);
 else
  ;//do nothing
}

//前序打印
template <class T>
void BinarySearchTree<T>::printTreeInPrev(BinaryNode<T>* t) const
{
 if (t)
 {
  cout << t->element;
  printTreeInPrev(t->left);
  printTreeInPrev(t->right);
 }
}

//中序打印
template <class T>
void BinarySearchTree<T>::printTreeInMid(BinaryNode<T>* t) const
{
 if (t)
 {
  printTreeInPrev(t->left);
  cout << t->element;
  printTreeInPrev(t->right);
 }
}

//后序打印
template <class T>
void BinarySearchTree<T>::printTreeInPost(BinaryNode<T>* t) const
{
 if (t)
 {
  printTreeInPost(t->left);
  printTreeInPost(t->right);
  cout << t->element;
 }
}
```

测试代码
===
```C++
#include "BinarySearchTree.h"

int main()
{
 BinarySearchTree<int> binaryTree;
 binaryTree.insert(5);
 binaryTree.insert(1);
 binaryTree.insert(2);
 binaryTree.insert(3);
 binaryTree.insert(6);
 binaryTree.insert(8);
 //测试前中后序打印
 cout <<endl<<"前序："<<endl;
 binaryTree.printTree(ORDER_MODE_PREV);
 cout <<endl<<"中序："<<endl;
 binaryTree.printTree(ORDER_MODE_MID);
 cout <<endl<<"后序："<<endl;
 binaryTree.printTree(ORDER_MODE_POST);
 cout <<endl;

 //测试基本操作
 bool b = binaryTree.contains(1);
 cout<< "是否存在1："<<b<<endl;
 int x = binaryTree.findMin();
 cout << "最小值为："<< x <<endl;
 x = binaryTree.findMax();
 cout << "最大值为："<< x <<endl;
 binaryTree.remove(2);

 cout << "移除元素2之后"<<endl;

 //测试前中后序打印
 cout <<endl<<"前序："<<endl;
 binaryTree.printTree(ORDER_MODE_PREV);
 cout <<endl<<"中序："<<endl;
 binaryTree.printTree(ORDER_MODE_MID);
 cout <<endl<<"后序："<<endl;
 binaryTree.printTree(ORDER_MODE_POST);
 cout <<endl;

 return 0;
}

时间： 2024-10-25 09:12:22

二叉搜索树源码分享_C 语言的相关文章

纯C语言:递归二进制转十进制源码分享_C 语言

复制代码 代码如下: #include<stdio.h>#include<math.h>int change(int n,int *sum,int *m)//n为第n位,m总位数{    char c;    if(c!='#')    {        *m=*m+1;        change(n+1,sum,m);    }    if(c=='#')    {        return *sum=int(*sum+pow(2,*m-n));    }}void main

纯C语言:分治假币问题源码分享_C 语言

复制代码 代码如下: #include<stdio.h>int sum(int m,int n){ if(n==m||n==0)  return 1; else  return sum(m-1,n)+sum(m-1,n-1);}void main(){ int m,n; printf("请输入组合数中的m:"); scanf("%d",&m); printf("\n请输入组合数中的n:"); scanf("%d&qu

纯C语言:检索与周游广度深度遍历源码分享_C 语言

复制代码 代码如下: #include <stdio.h>typedef  int  datatype;   /*假定线性表元素的类型为整型*/#define  maxsize  1024    /*假定线性表的最大长度为1024*/# define n 100            /* 图的顶点最大个数 */typedef char VEXTYPE;  /* 顶点的数据类型 */typedef float ADJTYPE;  /* 权值类型 */typedef struct{  VEXTY

纯C语言：贪心Prim算法生成树问题源码分享_C 语言

复制代码 代码如下: #include <iostream.h>#define MAX 100#define MAXCOST 100000 int graph[MAX][MAX]; int Prim(int graph[MAX][MAX], int n){ /* lowcost[i]记录以i为终点的边的最小权值,当lowcost[i]=0时表示终点i加入生成树 */ int lowcost[MAX];  /* mst[i]记录对应lowcost[i]的起点 */ int mst[MAX];  

纯C语言:折半查找源码分享_C 语言

复制代码 代码如下: #include <stdio.h>       int bin_search(int key[],int low, int high,int k)      {        int mid;        if(low>high)    {       return -1;        }    else       {             mid = (low+high) / 2;             if(key[mid]==k)         

纯C语言:分治快速排序源码分享_C 语言

复制代码 代码如下: #include<stdio.h>void fun(int array[],int low,int high){    int i = low;    int j = high;      int temp = array[i];              while(i < j)     {  while((array[j] >= temp) && (i < j))  {    j--;    array[i] = array[j]; 

WinForm天猫双11自动抢红包源码分享_C#教程

本文实例为大家分享了抢红包源码,供大家参考,具体内容如下 1. 正确获取红包流程 2. 软件介绍 2.1 效果图: 2.2 功能介绍 2.2.1 账号登录 页面开始时,会载入这个网站:https://login.taobao.com/member/login.jhtml?redirect_url=http%3A%2F%2F1111.tmall.com%2F 登录成功后,会自动跳转到1111.tmall.com活动页面. 2.2.2 [去抽奖]按钮 这按钮是手动跳转到1111.tmall.com页

Cocos2d-x学习笔记之Hello World源码分析_C 语言

首先我们来说一下游戏的原理,游戏类似于一场电影,早期的电影不就是靠一张张的图片放出来的吗?把场景人物什么的画在一幅幅图片上,然后从第一张图片开始播放就可以了.游戏更是如此,其实我们玩的游戏看到的画面都是美工做出来的,我们程序员要做的事情是组织这些图片,比如先弄个背景图片,然后在某一个坐标上放置一个人物的图片,我们写好程序,控制这个图片的移动路径,等机器运行的时候每秒都要刷新画面,我们就看到人物动了起来.而刷新页面的快慢就是我们所说的帧率,这个在程序中我们可以控制.整体的意思就是游戏不过是一些图片

纯C语言:递归组合数源码分享_C 语言

复制代码 代码如下: #include<stdio.h>int sum(int m,int n){ if(n==m||n==0)  return 1; else  return sum(m-1,n)+sum(m-1,n-1);}void main(){ int m,n; printf("请输入组合数中的m:"); scanf("%d",&m); printf("\n请输入组合数中的n:"); scanf("%d&qu