树和图是两大类常用的数据结构，在树这一类数据结构中，二叉查找树是掌握后续各种树的基础，所以，我们先学习二叉查找树。看一下二叉查找树是怎么实现的，怎么实现常规的插入、删除、查找等操作。

一、树的相关概念

• 空树：是高度为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;     }