查找二叉樹的定義，所有節點的左子樹均比該結點小，右子樹均比該節點大。如下所示為一個正解的查找二叉樹：
6
5 7
1 9
8 10
根據定義，查找二叉樹的節點應包含一個存儲數據，兩個指針，分別指向節點的左、右子樹，如下所示。
 struct BNode
   {
  BNode(T dat, BNode* l, BNode* r) : data(dat), left(l), right(r){};
 T data;
BNode *left, *right;
 }
對于二叉查找樹，其優點在于快速查找節點，在樹中找到一個結點，只需讓需查找的結點N與樹中節點進行比較，若N比當前結點小，則只需查找節點的左子樹，反之，則只需查找節點的右子樹，直至找到為止，所以其查找總是為一條單一的路徑。 二叉查找樹的實現 BTree.h
#ifndef BTREE_H
#define BTREE_H
#include <iostream>
#include <queue>
static int findcounts; //用于測試查找某節點的次數
template<class T>
class BTree
{
//定義樹節點，包括一個數據，兩個指針
struct BNode
{
BNode(T dat, BNode* l, BNode* r) : data(dat), left(l), right(r){};
T data;
BNode *left, *right;
 }* root;
//插入一個節點，
void Insert(const T& data, BNode*& p)
{
if(p == 0)
{
p = new BNode(data, 0, 0);
std::cout << "Insert data=" << data << std::endl;
}
else if(data < p->data)
{
//插入數據小于父節點數據，插入左子樹
Insert(data, p->left);
}
else if(data > p->data)
{
//插入數據小于父節點數據，插入右子樹
Insert(data, p->right);
}
}
//先序遍歷
void PreOrder (BNode* p)
{
if(p != 0)
{
Print(p);
PreOrder (p->left);
PreOrder (p->right);
}
}
//中序遍歷
void InOrder (BNode* p)
{
if(p != 0)
{
InOrder (p->left);
Print(p);
InOrder (p->right);
}
}
//后序遍歷
void PostOrder (BNode* p)
{
if(p != 0)
{
PostOrder (p->left);
PostOrder (p->right);
Print(p);
}
}
//查找節點
bool Find(const T& data, BNode* p)
{
if(p != 0)
{
if(data == p->data)
{
return true;
}
else if(data < p->data)
{
findcounts ++;
Find(data, p->left);
}
else
{
findcounts ++;
Find(data, p->right);
}
}
else
{
return false;
}
}
//刪除整棵樹
void MakeEmpty(BNode* p)
{
if(p != 0)
{
MakeEmpty(p->left);
MakeEmpty(p->right);
std::cout << "del " << p->data << ",";
delete p;
}
}
public:
BTree() : root(0){}
~BTree()
{
MakeEmpty(root);
}
void Insert(const T& data)
{
Insert(data, root);
}
void PreOrder()
{
//遞歸，前序遍歷
PreOrder(root);
}
void InOrder()
{
//遞歸，中序遍歷
InOrder(root);
}
void PostOrder()
{
//遞歸，后序遍歷
PostOrder(root);
}
//層次遍歷，使用隊列的特性實現樹的非遞歸遍歷
void LevelOrder ()
{
queue<BNode*> q;
BNode* p = root;
while(p)
{
Print(p);
if(p->left != 0)
{
q.push(p->left);
}
if(p->right != 0)
{
q.push(p->right);
}
if (q.empty())
{
break;
}
p = q.front();
q.pop();
}
}
//打印一個節點值
void Print(BNode* p)
{
if(p != 0)
{
std::cout << p->data << ",";
}
}
//打印一個節點的查找次數
void PrintStatic()
{
std::cout << findcounts;
}
//遞歸查找一個節點
bool Find(const T& data)
{
findcounts = 0;
return Find(data, root);
}
};
#endif
對樹進行測試 Test.cpp
#include <iostream>
#include <cstdlib>
#include <ctime>
#include "BTree.h"
using namespace std;
int main(int argc, char *argv[])
{
//隨機生成一棵樹
BTree<int> tree;
srand((unsigned)time(NULL));
for(int i=0; i<20; ++i)
{
tree.Insert(rand() / 20);
}
cout << "前序:" << endl;
tree.PreOrder();
cout << endl;
cout << "中序" << endl;
tree.InOrder();
cout << endl;
cout << "后序" << endl;
tree.PostOrder();
cout << endl;
cout << "層次" << endl;
tree.LevelOrder();
cout << endl;
if(tree.Find(14))
{
cout << "14 is in the tree,search for " ;
tree.PrintStatic();
cout << endl;
}
else
{
cout << "14 is not in the tree,search for " ;
tree.PrintStatic();
cout << endl;
}
return 0;
}
|