二叉排序树：

#include <iostream>
#include <queue>
using namespace std;

template <class T> class BinaryTree;

template <class T>
class Node {
public:
    Node() {};
    Node(T num) {
        data = num;
        lchild = NULL;
        rchild = NULL;
    }
    friend class BinaryTree<T>;
private:
    T data;
    Node<T>* lchild;
    Node<T>* rchild;
};

template <class T>
class BinaryTree {
public:
    BinaryTree() {
        root = NULL;
    }
    void Insert(T num);
    void PreOrder(Node<T>* r);//前序遍历
    void InOrder(Node<T>* r);//中序遍历
    void PostOrder(Node<T>* r);//后序遍历
    void LevelOrder();//层次遍历
//private:
    Node<T>* root;
};

template <class T>
void BinaryTree<T>::Insert(T num) {
    Node<T>* pnew = new Node<T>(num);
    Node<T>* p = root;
    if (!p) {
        root = pnew; 
    }
    else {
        while (p) {
            Node<T>* pre = p;
            if (num < p->data) {
                p = p->lchild;
                if (!p) {
                    pre->lchild = pnew;
                }
            }
            else if(num > p->data)
            {
                p = p->rchild;
                if (!p) {
                    pre->rchild = pnew;
                }
            }
        }
    }
}

template <class T>
void BinaryTree<T>::PreOrder(Node<T> *r) {

    if (r) {
        cout << r->data;
        PreOrder(r->lchild);
        PreOrder(r->rchild);
    }
}
template <class T>
void BinaryTree<T>::InOrder(Node<T>* r) {
    if (r) {
        InOrder(r->lchild);
        cout << r->data;
        InOrder(r->rchild);
    }
}
    
template <class T>
void BinaryTree<T>::PostOrder(Node<T>* r)
{
    if (r) {
        PostOrder(r->lchild);
        PostOrder(r->rchild);
        cout << r->data;
    }
}

template <class T>
void BinaryTree<T>::LevelOrder(){
    queue<Node<T>*> q;
    Node<T>* p = root;
    q.push(p);
    while (!q.empty()) {
        p = q.front();
        if (p->lchild) {
            q.push(p->lchild);
        }
        if (p->rchild) {
            q.push(p->rchild);
        }
        cout << q.front()->data ;
        q.pop();
    }
}

int main()
{
    BinaryTree<char> tree;
    char table[] = { 'E','C','B','A','D','J','H','G','F','I' };
    for (int i = 0; i < 10; i++) {
        tree.Insert(table[i]);
    }
    tree.PreOrder(tree.root); cout << endl;
    tree.InOrder(tree.root); cout << endl;
    tree.PostOrder(tree.root); cout << endl;
    tree.LevelOrder();
    return 0;
}

上面没有写删除函数，所以贴上以前写的删除函数。
删除节点要分好几种情况：

删除一个结点原理图.png

代码：

bool Tree::Delete(int num)
{
    Node *p = this->root;//指向要删除的结点
    Node *prev = this->root;//指向要删除结点的根结点
    
    while(p)//找到要删除的结点
    {
        if( num  > p->data )
        {
            prev = p;
            p = p->rchild;
        }else if( num < p->data )
        {
            prev = p;
            p = p->lchild;
        }else
        {
            break;
        }
    }
    if( p == NULL )//如果没找到要删除的结点，则返回错误
    {
        return false;
    }
    
    if( p->lchild == NULL && p->rchild == NULL )//如果p没有孩子
    {
        if( p == prev->lchild )//p在根的左边
        {
            prev->lchild = NULL;
            free(p);
            
        }else if( p == prev->rchild )//p在根的右边
        {
            prev->rchild = NULL;
            free(p);
        }else if( p == this->root  )//p是根结点
            this->root = NULL;
    }else if( p->lchild != NULL && p->rchild != NULL )//如果p有两个孩子
    {
        Node *p2 = p->lchild;//指向左子树最大的结点
        Node *prev2 = p;//指向p2的根结点
        while(p2)//找p左子树最大的结点
        {
            if( p2->rchild == NULL )
            {
                break;
            }else
            {
                prev2 = p2;
                p2 = p2->rchild;
            }
        }
        if( p2 == p->lchild )//如果左子树最大的结点是p的左孩子
        {
            int num = p2->data;
            p2->data = p->data;
            p->data = num;
            
            p->lchild = p2->lchild;
            p2->lchild = NULL;
            free(p2);
        }else//左子树最大的结点是p的左孩子的右子树最大结点
        {
            int num = p->data;
            p->data = p2->data;
            p2->data = num;
            
            prev2->rchild = p2->lchild;
            p2->lchild = NULL;
            free(p2);
        }
    }else//如果p只有一个孩子
    {
        if( p == this->root )//如果p是根结点
        {
            if( p->lchild != NULL )//p没有右孩子 只有左孩子
            {
                Node *psave = p->lchild;
                p->lchild = NULL;
                free(p);
                this->root = psave;
            }else if( p->rchild != NULL )//p没有左孩子 只有右孩子
            {
                Node *psave = p->rchild;
                p->rchild = NULL;
                free(p);
                this->root = psave;
            }
        }else if( p == prev->lchild )//如果p是某个根的左孩子
        {
            if( p->rchild == NULL )//p只有左孩子，没有右孩子
            {
                prev->lchild = p->lchild;
                p->lchild = NULL;
                free(p);
            }else//p只有右孩子，没有左孩子
            {
                prev->lchild = p->rchild;
                p->rchild = NULL;
                free(p);
            }
        }else if( p == prev->rchild )//如果p是某个根的右孩子
        {
            if( p->lchild == NULL )//p只有右孩子，没有左孩子
            {
                prev->rchild = p->rchild;
                p->rchild = NULL;
                free(p);
            }else//p只有左孩子，没有右孩子
            {
                prev->rchild = p->lchild;
                p->lchild = NULL;
                free(p);
            }
        }
    }
    return true;
}

非递归的先序遍历：
利用了栈，先存根结点，然后根结点出栈的同时，先存根结点的右子节点，再存左子节点；然后在出栈，再依次存出栈元素的右、左子节点。。。。。

void Tree::fpreorder()
{
    stack<Node *> b;
    Node *p = this->root;
    Node *num=NULL;
    b.push(p);
    while( !b.empty() )
    {
        p = b.top();
        num = b.top();
        b.pop();
        cout<<num->data<<" ";
        if( p->rchild )
        {
            b.push(p->rchild);    
        }
        if( p->lchild )
        {
            b.push(p->lchild);
        }
    }
}