c++二叉樹的各種操作

頭文件

#ifndef _BINARYTREE_H_
#define _BINARYTREE_H_

const int MaxSize = 100;

template
struct BTNode
{
    T data;
    BTNode *lchild;
    BTNode *rchild;
};

template
class BinaryTree
{
public:
    BinaryTree();                   //構造函數
    ~BinaryTree();                  //析構函數
    void PreOrder(){PreOrder(r);}   //遞歸前序遍歷
    void InOrder(){InOrder(r);}     //遞歸中序遍歷
    void PostOrder(){PostOrder1(r);} //遞歸後序遍歷
    void PreOrder1(){PreOrder1(r);}   //非遞歸前序遍歷
    void InOrder1(){InOrder1(r);}     //非遞歸中序遍歷
    void PostOrder1(){PostOrder(r);} //非遞歸後序遍歷
    void LevelOrder(){LevelOrder(r);}//層序遍歷
    BTNode* FindNode(T x){FindNode(r,x);}//查找結點
    int BTNodeHeigth(){BTNodeHeigth(r);}//樹的高度
    int NodeCount1(){NodeCount1(r);}    //基於前序遍歷求結點個數
    int NodeCount2(){NodeCount2(r);}    //基於中序遍歷求結點個數
    int NodeCount3(){NodeCount3(r);}    //基於後序遍歷求結點個數
    int NodeCount4(){NodeCount4(r);}    //遞歸求結點個數
    void DispLeaf(){DispLeaf(r);}       //輸出樹的葉子結點
    void printRouteLength(){printLeavesDepth(r, 0);}//輸出樹的葉子結點到根結點的路徑長度
    bool printAncestor(T x){printAncestor(r,x);}    //輸出值為x的結點的祖先結點
private:
    BTNode *r;
    BTNode* CreateTree(BTNode *t);//構造函數調用
    void DestroyTree(BTNode *t);     //析構函數調用
    void PreOrder(BTNode *t);        //遞歸前序遍歷調用
    void InOrder(BTNode *t);         //遞歸中序遍歷調用
    void PostOrder(BTNode *t);       //遞歸後序遍歷調用
    void PreOrder1(BTNode *t);        //非遞歸前序遍歷調用
    void InOrder1(BTNode *t);         //非遞歸中序遍歷調用
    void PostOrder1(BTNode *t);       //非遞歸後序遍歷調用
    void LevelOrder(BTNode *t);       //層序遍歷調用
    BTNode* FindNode(BTNode *t, T x);
    int BTNodeHeigth(BTNode *t);
    int NodeCount1(BTNode *t);       //前序遍歷求結點個數調用
    int NodeCount2(BTNode *t);       //中序遍歷求結點個數調用
    int NodeCount3(BTNode *t);       //後序遍歷求結點個數調用
    int NodeCount4(BTNode *t);       //遞歸求結點個數調用
    void DispLeaf(BTNode *t);
    void printLeavesDepth(BTNode *t,int depth);
    bool printAncestor(BTNode *t,T x);
};
//
template
BinaryTree::BinaryTree()
{
    r = CreateTree(r);
}
//
template
BinaryTree::~BinaryTree()
{
    DestroyTree(r);
}
//
template
void BinaryTree::DestroyTree(BTNode *t)
{
    if(t != NULL)
    {
        DestroyTree(t->lchild);
        DestroyTree(t->rchild);
        delete t;
    }
}
//
template
BTNode* BinaryTree::CreateTree(BTNode *t)
{
    T ch;
    std::cin>>ch;
    if(ch == '#')
    {
        t = NULL;
    }
    else
    {
        t = new BTNode;
        t->data = ch;
        t->lchild = CreateTree(t->lchild);
        t->rchild = CreateTree(t->rchild);
    }
    return t;
}
//
template
void BinaryTree::PreOrder(BTNode *t)
{
    if(t != NULL)
    {
        std::cout<data<<"  ";
        PreOrder(t->lchild);
        PreOrder(t->rchild);
    }
}
//
template
void BinaryTree::InOrder(BTNode *t)
{
    if(t != NULL)
    {
        InOrder(t->lchild);
        std::cout<data<<"  ";
        InOrder(t->rchild);
    }
}
//
template
void BinaryTree::PostOrder(BTNode *t)
{
    if(t != NULL)
    {
        PostOrder(t->lchild);
        PostOrder(t->rchild);
        std::cout<data<<"  ";
    }
}
//
template
BTNode* BinaryTree::FindNode(BTNode *t,T x)
{
    BTNode *p;
    if(t == NULL)
    {
        return NULL;
    }
    else if(t->data == x)
    {
        return t;
    }
    else
    {
        p = FindNode(t->lchild,x);
        if(p != NULL)
        {
            return p;
        }
        return FindNode(t->rchild,x);
    }
}
//
template
int BinaryTree::BTNodeHeigth(BTNode *t)
{
    int lchildh,rchildh;
    if(t == NULL)
    {
        return 0;
    }
    else
    {
        lchildh = BTNodeHeigth(t->lchild);
        rchildh = BTNodeHeigth(t->rchild);
        return (lchildh > rchildh)?(lchildh + 1):(rchildh + 1);
    }
}
//
template
int BinaryTree::NodeCount4(BTNode *t)
{
    if(t == NULL)
    {
        return 0;
    }
    else
    {
        return (NodeCount4(t->lchild) + NodeCount4(t->rchild) + 1);
    }
}
//
template
int BinaryTree::NodeCount1(BTNode *t)
{
    int m,n,k;
    if(t != NULL)
    {
        m = NodeCount1(t->lchild);
        k = 1;
        n = NodeCount1(t->rchild);
        return m + n + k;
    }
    return 0;
}
//
template
int BinaryTree::NodeCount2(BTNode *t)
{
    int m,n,k;
    if(t != NULL)
    {
        m = NodeCount2(t->lchild);
        n = NodeCount2(t->rchild);
        k = 1;
        return m + n + k;
    }
    return 0;
}
//
template
int BinaryTree::NodeCount3(BTNode *t)
{
    int m,n,k;
    if(t != NULL)
    {
        k = 1;
        m = NodeCount3(t->lchild);
        n = NodeCount3(t->rchild);
        return m + n + k;
    }
    return 0;
}
//
template
void BinaryTree::DispLeaf(BTNode *t)
{
    if(t != NULL)
    {
        if((t->lchild == NULL)&&(t->rchild == NULL))
        {
            std::cout<data<<"  ";
        }
        DispLeaf(t->lchild);
        DispLeaf(t->rchild);
    }
}
//
template
//輸出路徑長度
void BinaryTree::printLeavesDepth(BTNode *t, int depth)
{
  if (t == NULL) return;
  if (t->lchild == NULL && t->rchild == NULL)
  {
    std::cout<data<<": "<lchild, depth+1);
    printLeavesDepth(t->rchild, depth+1);
  }
}
//
template
bool BinaryTree::printAncestor(BTNode *t, T x)
{
    if(t == NULL)
    {
        return false;
    }
    if((t->lchild != NULL)&&(t->lchild->data == x))
    {
        std::cout<data<<"  ";
        return true;
    }
    if((t->rchild != NULL)&&(t->rchild->data == x))
    {
        std::cout<data<<"  ";
        return true;
    }
    if((printAncestor(t->lchild,x))||(printAncestor(t->rchild,x)))
    {
        std::cout<data<<"  ";
        return true;
    }
    return false;
}
//
template
void BinaryTree::PreOrder1(BTNode *t)
{
    BTNode *st[MaxSize];
    int top = -1;
    BTNode *p;
    top++;
    st[top] = t;                //將根結點入棧
    while(top != -1)            //棧非空
    {
        p = st[top];
        top--;
        std::cout<data<<"  ";
        if(p->rchild != NULL)   //右孩子先進棧
        {
            top++;
            st[top] = p->rchild;
        }
        if(p->lchild != NULL)   //左孩子再進棧
        {
            top++;
            st[top] = p->lchild;
        }
    }
}
//中序遍歷非遞歸算法
template
void BinaryTree::InOrder1(BTNode *t)
{
    BTNode *st[MaxSize];
    BTNode *p;
    int top = -1;
    p = t;
    while((top != -1)||(p!=NULL))   //棧不空或p不為空時
    {
        while(p != NULL)            //掃描所有左結點並進棧
        {
            top++;
            st[top] = p;
            p = p->lchild;
        }
        if(top > -1)                //若棧不為空
        {
            p = st[top];
            top--;
            std::cout<data<<"  ";
            p = p->rchild;          //轉向處理右子樹
        }
    }
}
//
template
void BinaryTree::PostOrder1(BTNode *t)
{
    BTNode *st[MaxSize],*p,*q;
    p = t;
    int top = -1;
    bool flag;
    do
    {
        while(p != NULL)        //將p結點及所有的左下結點進棧
        {
            top++;
            st[top] = p;
            p = p->lchild;
        }
        q = NULL;              //q指向棧頂結點的前一個已經訪問的結點
        flag =true;              //表示p結點的左子樹已經遍歷完
        while((top != -1)&&(flag == true))//若p結點及其右子樹已訪問或為空
        {
            p = st[top];
            if(p->rchild == q)
            {
                std::cout<data<<"  ";
                top--;
                q = p;
            }
            else
            {
                p = p->rchild;
                flag = false;
            }
        }
    }
    while(top != -1);
}
//
template
void BinaryTree::LevelOrder(BTNode *t)
{
    BTNode *qu[MaxSize],*p;
    int front = 0, rear = 0;
    rear++;
    qu[rear] = t;
    while(front != rear)    //隊列不為空
    {
        front = (front + 1) % MaxSize;
        p = qu[front];
        std::cout<data<<"  ";
        if(p->lchild != NULL)
        {
            rear = (rear + 1) % MaxSize;
            qu[rear] = p->lchild;
        }
        if(p->rchild != NULL)
        {
            rear = (rear + 1) % MaxSize;
            qu[rear] = p->rchild;
        }
    }
}
#endif // _BINARYREE_H_

#include 
#include "BinaryTree.h"

using namespace std;

int main()
{
    BinaryTree a;

    cout<<"前序遍歷：  ";
    a.PreOrder();
    cout<