欧美大屁股bbbbxxxx,狼人大香伊蕉国产www亚洲,男ji大巴进入女人的视频小说,男人把ji大巴放进女人免费视频,免费情侣作爱视频

歡迎來到入門教程網(wǎng)!

C語言

當(dāng)前位置:主頁 > 軟件編程 > C語言 >

二叉搜索樹源碼分享

來源:本站原創(chuàng)|時間:2020-01-10|欄目:C語言|點擊: 次

復(fù)制代碼 代碼如下:

#include <iostream>
using namespace std;

//枚舉類,前中后三種遍歷方式
enum ORDER_MODE
{
 ORDER_MODE_PREV = 0,
 ORDER_MODE_MID,
 ORDER_MODE_POST
};

//樹節(jié)點的結(jié)構(gòu)體
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;
};

//構(gòu)造方法
template <class T>
BinarySearchTree<T>::BinarySearchTree()
{
 m_root = NULL;
}

//使用另一棵二叉搜索樹的構(gòu)造函數(shù)
template <class T>
BinarySearchTree<T>:: BinarySearchTree(const BinarySearchTree& rhs)
{
 m_root = rhs.m_root;
}

//析構(gòu)函數(shù),釋放內(nèi)存
template <class T>
BinarySearchTree<T>:: ~BinarySearchTree()
{
 makeEmpty();
}

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

//遞歸調(diào)用
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
{
 //二叉樹的一個特點就是左子葉的值比根節(jié)點小, 右子葉的比根節(jié)點的大
 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
{
 //二叉樹的一個特點就是左子葉的值比根節(jié)點小, 右子葉的比根節(jié)點的大
 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);//注意這個指針參數(shù)是引用
 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;
}

上一篇:Recommended C Style and Coding Standards中文翻譯版第1/3頁

欄    目:C語言

下一篇:C語言的數(shù)字游戲算法效率問題探討實例

本文標(biāo)題:二叉搜索樹源碼分享

本文地址:http://mengdiqiu.com.cn/a1/Cyuyan/3686.html

網(wǎng)頁制作CMS教程網(wǎng)絡(luò)編程軟件編程腳本語言數(shù)據(jù)庫服務(wù)器

如果侵犯了您的權(quán)利,請與我們聯(lián)系,我們將在24小時內(nèi)進行處理、任何非本站因素導(dǎo)致的法律后果,本站均不負(fù)任何責(zé)任。

聯(lián)系QQ:835971066 | 郵箱:835971066#qq.com(#換成@)

Copyright © 2002-2020 腳本教程網(wǎng) 版權(quán)所有