树和图是两大类常用的数据结构，在树这一类数据结构中，二叉查找树是掌握后续各种树的基础，所以，我们先学习二叉查找树。看一下二叉查找树是怎么实现的，怎么实现常规的插入、删除、查找等操作。
一、树的相关概念
空树：是高度为0的合法树；
单一节点：是高度为1的树（是节点既是根也是叶子的唯一情况）；
极端情况下，树退化为链表；（比如二叉查找树中，数据正好是已经排好序的，此时数据元素全部位于左子树或右子树，相当于链表结构）
二叉树：节点可以包含两个子节点（也可能为空）的树，每一个子节点都区分为左子节点或右子节点。
完全二叉树：所有的非终端节点都有两个子节点，所有的叶节点都位于同一层次；
对于非空二叉树，若其所有的非终端节点刚好有两个非空子节点，则叶节点的数目m大于非终端节点的数目k，并且m=k+1；
二叉查找树（有序二叉树）：对于树中的每个节点n，其左子树（根节点为左子节点的树）中的值小于节点n中的值v，其右子树中的值大于节点n中的值v。
二、二叉树的实现
二叉树至少可以有两种方式实现：数组和链接结构。这里使用链接结构实现。
二叉查找树的性质：
对于树中的每个节点X，它的左子树中所有项的值都要小于X中的项；
对于树中的每个节点Y，它的右子树中所有项的值都要大于Y中的项。
下面我们详细介绍通用二叉查找树的实现。
二叉树的实现
// tree.cpp : 通用二叉查找树的实现代码
#include "stdafx.h"
#include<iostream>
#include<list>
#include<stack>
#include<queue>
using namespace std;
//栈实现
template<class T>
class Stack : public stack<T> {
public:
T pop() {
T tmp = stack<T>::top();
stack<T>::pop();
return tmp;
}
};
//队列实现
template<class T>
class Queue : public queue<T> {
public:
T dequeue() {
T tmp = queue<T>::front();
queue<T>::pop();
return tmp;
}
void enqueue(const T& el) {
queue<T>::push(el);
}
};
//树节点类
template<class T>
class Node {
public:
Node():left(NULL),right(NULL){}
Node(const T& e,Node<T>* l=NULL,Node<T>*r=NULL):data(e),left(l),right(r){}
~Node(){}
T data;
Node* left;
Node* right;
};
//二叉查找树的实现类
template<class T>
class BST {
public:
BST():root(NULL){}
BST(T* a, int len); //根据数组中的数据构造树，调试测试用
~BST() {
clear();
}
bool isEmpty() const {
return NULL == root;
}
void clear() {
clear(root);
root = NULL;
}
void insert(const T&);
//插入
void remove(const T &x); // 删除二叉查找树中指定的值
void recursiveInsert(const T& el) {
recursiveInsert(root, el);
}
Node<T>* search(const T& el) const { //查找
return search(root, el);
}
Node<T>* recursiveSearch(const T& el) const {
return recursiveSearch(root, el);
}
void preorder() {//深度遍历之前序树遍历
preorder(root);
}
void inorder() {//深度遍历之中序树遍历
inorder(root);
}
void postorder() {//深度遍历之后序树遍历
postorder(root);
}
void iterativePreorder(); //深度遍历之前序树遍历
void iterativeInorder(); //深度遍历之中序树遍历
void iterativePostorder(); //深度遍历之后序树遍历
void breadthFirst();
//广度优先遍历
const T& findMin()const; // 查找最小值，并返回最小值
const T &findMax() const; // 查找最大值，并返回最大值
protected:
Node<T>* root; //根节点
void clear(Node<T>*);
void recursiveInsert(Node<T>*&, const T&);
Node<T>* search(Node<T>*, const T&) const;
Node<T>* recursiveSearch(Node<T>*, const T&) const;
void preorder(Node<T>*);
void inorder(Node<T>*);
void postorder(Node<T>*);
virtual void visit(Node<T>* p) {
cout << p->data << ' ';
}
Node<T>* findMin(Node<T>* t) const;
//迭代方式实现
Node<T>* findMax(Node<T>* t) const;
//迭代方式实现
Node<T>* findMin_loop(Node<T>* t) const;
//循环方式实现
Node<T>* findMax_loop(Node<T>* t) const;
//循环方式实现
void remove(const T&x,Node<T>*& t) const;
};
//根据数组中的内容构造树
template<class T>
BST<T>::BST(T* a, int len) {
root = NULL;
for (int i = 0; i < len; i++) {
insert(a[i]);
}
}
//清除节点p及其子节点
template<class T>
void BST<T>::clear(Node<T> *p) {
if (p != NULL) {
clear(p->left);
clear(p->right);
delete p;
}
}
int main()
{
int a[] = { 13,10,25,2,12,20,31,29 };
BST<int> tree(a, sizeof(a) / sizeof(a[0]));
cout << endl;
tree.inorder();
cout << endl;
tree.iterativeInorder();
system("pause");
return 0;
}
插入操作
//插入，非递归形式
template<class T>
void BST<T>::insert(const T& el) {
Node<T> *p = root, *prev = NULL;
while (p != NULL) { // find a place for inserting new node;
prev = p;
if (el < p->data)
p = p->left;
else p = p->right;
}
if (root == NULL) // tree is empty;
root = new Node<T>(el);
else if (el < prev->data)
prev->left = new Node<T>(el);
else prev->right = new Node<T>(el);
}
//插入，递归实现
template<class T>
void BST<T>::recursiveInsert(Node<T>*& p, const T& el) {
if (p == NULL)
p = new Node<T>(el);
else if (el < p->data)
recursiveInsert(p->left, el);
else recursiveInsert(p->right, el);
}
查找操作
//查找
template<class T>
Node<T>* BST<T>::search(Node<T>* p, const T& el) const {
while (p != NULL) {
if (el == p->data)
return &p->el;
else if (el < p->data)
p = p->left;
else p = p->right;
}
return NULL;
}
//查找，递归实现
template<class T>
Node<T>* BST<T>::recursiveSearch(Node<T>* p, const T& el) const {
if (p != NULL)
if (el == p->data)
return p;
else if (el < p->data)
return recursiveSearch(p->left, el);
else return recursiveSearch(p->right, el);
else return NULL;
}
删除操作
