C++二叉树的基本操作

#include <iostream>
using namespace std;
class BinaryTree ;
class BinTreeNode                                   //结点类的定义
{
    friend  BinaryTree;
private:
    BinTreeNode *leftChild, *rightChild;  //左、右子女链域
    char data;                                              //数据域
public:
    BinTreeNode ( )
    {
        leftChild =NULL;
        rightChild =NULL;
    }
    BinTreeNode ( char x,BinTreeNode *left = NULL,BinTreeNode *right = NULL ) : data (x), leftChild (left), rightChild(right) { }               //构造函数
    ~BinTreeNode ( ) { }                                   //析构函数

};
class BinaryTree
{

private:
    BinTreeNode  *root;                    //二叉树的根指针
    char RefValue;                    //数据输入停止标志
    void CreateBinTree( BinTreeNode * & subTree) ;
    BinTreeNode  *Parent ( BinTreeNode * subTree,BinTreeNode  *current );
    int Height(BinTreeNode  *subTree);
    int Size(BinTreeNode  *subTree);
    void preOrder(BinTreeNode *subTree );     //前序遍历
    void inOrder(BinTreeNode *subTree );       //中序遍历
    void postOrder(BinTreeNode *subTree );   //后序遍历
    void levelOrder(BinTreeNode *subTree);    //层序遍历
    void destroy(BinTreeNode* &subTree) {};
    int Leafnum(BinTreeNode *subtree);
    int Find(char C,BinTreeNode * sub);
    void out(BinTreeNode* node, int lay);
public:
    BinaryTree(): root (NULL) { };
    BinaryTree ( char value )
    {
        RefValue =value;
        root =NULL;
    }
    ~BinaryTree()
    {
        destroy ( root );
    }
    void CreateBinTree( )
    {
        CreateBinTree(root);
    }

    bool IsEmpty ( )
    {
        return (root == NULL) ? true : false;
    }
    BinTreeNode  *Parent ( BinTreeNode  *current )
    {
        return (root == NULL || root == current)? NULL : Parent ( root,current );
    }

    BinTreeNode  *LeftChild (BinTreeNode  *current )
    {
        return (current != NULL )? current->leftChild :NULL;
    }
    BinTreeNode  *RightChild (BinTreeNode  *current )
    {
        return ( current!= NULL) ? current->rightChild : NULL;
    }

    int Height( )
    {
        return Height(root);
    }
    int Size( )
    {
        return Size(root);
    }
    BinTreeNode  *GetRoot ( ) const
    {
        return root;
    }
    void preOrder( )
    {
        preOrder(root);   //前序遍历
    }
    void inOrder( )
    {
        inOrder(root);   //中序遍历
    }
    void postOrder( )
    {
        postOrder(root);   //后序遍历
    }
    void levelOrder()
    {
        levelOrder(root);   //层序遍历
    }
    int leafnum()
    {
        return Leafnum(root);
    }
    int Find(char C)
    {
        return Find(C,root);
    }
    void out()
    {
        out(root,Height());
    }
};

void BinaryTree ::CreateBinTree(BinTreeNode* & subTree)  //私有函数: 建立根为subTree的子树
{
    char item;
    cin>> item;
    if (item != RefValue)
    {
        subTree = new   BinTreeNode (item);
        CreateBinTree( subTree->leftChild);
        CreateBinTree( subTree->rightChild);
    }
    else
        subTree = NULL;
};

void BinaryTree ::inOrder( BinTreeNode  *subTree )
{
    //私有函数，中序遍历以subTree为根的二叉树
    if (subTree != NULL)
    {
        inOrder (subTree->leftChild);
        cout << subTree->data<<" ";
        inOrder (subTree->rightChild );
    }
}
void BinaryTree ::preOrder( BinTreeNode  *subTree )
{
    //私有函数，中序遍历以subTree为根的二叉树
    if (subTree != NULL)
    {
        cout << subTree->data<<" ";
        preOrder (subTree->leftChild);
        preOrder (subTree->rightChild );
    }
}
void BinaryTree ::postOrder( BinTreeNode  *subTree )
{
    //私有函数，后序遍历以subTree为根的二叉树
    if (subTree != NULL)
    {
        postOrder(subTree->leftChild);
        postOrder(subTree->rightChild );
        cout << subTree->data<<" ";
    }
}

int BinaryTree::Leafnum(BinTreeNode* subtree)
{
    int sum = 0;
    if(subtree == NULL)
        return sum;
    if(subtree->leftChild == NULL && subtree->rightChild == NULL)
    {
        sum++;
    }
    else
    {
        sum += Leafnum(subtree->leftChild) + Leafnum(subtree->rightChild);
    }
    return sum;
}

int BinaryTree::Height(BinTreeNode* subTree)
{
    int height = 0;
    if(subTree != NULL)
    {
        height++;
        return height + max(Height(subTree->leftChild),Height(subTree->rightChild));
    }
    else
        return height;
}

int BinaryTree::Size(BinTreeNode* subTree)
{
    int t = 0;
    if(subTree == NULL)
        return 0;
    else
    {
        t++;
        t += Size(subTree->leftChild) + Size(subTree->rightChild);
    }
    return t;
}

int BinaryTree::Find(char C, BinTreeNode* sub)
{
    int sum=0;
    if(sub->data == C)
    {
        sum++;
        sub = sub->leftChild;
        sum += Find(C,sub);
        sub = sub->rightChild;
        sum += Find(C,sub);
    }
    return sum;
}

void BinaryTree::out(BinTreeNode* node, int lay)
{
    if(node != NULL)
    {
        for(int i=lay;i<Height();i++)  cout << "  ";
        cout <<node->data << endl;
        lay--;
        out(node->leftChild,lay);
        out(node->rightChild,lay);
    }
}

int main()
{
    char C;
    int pre,in,post;
    cin >> C;
    if(C == 'C')
    {

        BinaryTree a = BinaryTree('#');
        cout << "Created success!"<<endl;
        a.CreateBinTree();
        cin >> C;
        if(C == 'H')
        {
            cout<<"Height="<<a.Height()<<"."<<endl;
        }
        cin >> C;
        if(C == 'L')
        {
            cout<<"Leaf="<<a.leafnum()<<"."<<endl;
        }
        cin >> C;
        if(C == 'N')
        {
            cout<<"Nodes="<<a.Size()<<"."<<endl;
        }
        cin >> pre;
        if(pre == 1)
        {
            cout <<"Preorder is:";
            a.preOrder();
            cout << "."<<endl;
        }
        cin >> in;
        if(in == 2)
        {
            cout <<"Inorder is:";
            a.inOrder ();
            cout <<"."<<endl;
        }
        cin >> post;
        if(post == 3)
        {
            cout << "Postorder is:";
            a.postOrder();
            cout << "."<<endl;
        }
        cin >> C;
        if(C == 'F')
        {
            cin >> C;
            cout << "The count of "<<C<< " is "<<a.Find(C)<<"."<<endl;
        }
        cin >> C;
        if(C == 'P')
        {
            cout <<"The tree is:"<<endl;
            a.out();
        }
    }

}