查找二叉树的定义，所有节点的左子树均比该结点小，右子树均比该节点大。如下所示为一个正解的查找二叉树：
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;
}
|