[数据结构] 二叉树

数据结构的练习与巩固
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include<iostream>
using namespace std;

template <class T> 
struct BTNode
{                                               //二叉树结点类定义
       T data;                                  //数据域
    BTNode<T> *lChild, *rChild;
                                                //左子女、右子女链域
    BTNode ()                                   //构造函数
       { 
               lChild = NULL;  
               rChild = NULL; 
       }
       
    BTNode (T& x, BTNode<T> *l = NULL, BTNode<T> *r = NULL)
       { 
            data = x;  
            lChild = l;  
            rChild = r; 
       }
};

//二叉树类定义
template <class T> 
class BT 
{            
public:
     BTNode<T> *root;          //二叉树的根指针
     T RefValue;               //数据输入停止标志
public:
        
    BT () : root (NULL) {}                          //构造函数
    BT (T value) : RefValue(value), root(NULL) {}   //构造函数
 
    BTNode<T> *lChild (BTNode<T> *t)
       { return (t != NULL)?t->lChild : NULL; }     //返回左子女
    BTNode<T> *rChild (BTNode<T> *t)
       { return (t != NULL)?t->rChild : NULL; }     //返回右子女
                                                          
    bool IsEmpty() { return root == NULL; }         //判二叉树空否                                                          
    BTNode<T> * & getRoot () { return root; }       //取根
     
    void PreOrder (BTNode<T>*& subTree);            //前序遍历
    void InOrder  (BTNode<T>*& subTree);            //中序遍历
    void postOrder(BTNode<T>*& subTree);            //后序遍历
    
    void CreateBT(BTNode<T>* & subTree);
      52     
    void Size (BTNode<T> * &subTree,int &count);    //返回结点数
    
    void leaf (BTNode<T> * &subTree,int &count);    //返回叶子数
};

template<class T>
void BT<T>::PreOrder(BTNode<T>* &subTree)
{
    if (subTree != NULL)
    {
        cout << subTree->data <<‘ ‘;
        PreOrder(subTree->lChild);
        PreOrder(subTree->rChild);
    }
}

template<class T>
void BT<T>::InOrder(BTNode<T>* &subTree)
{
    if (subTree != NULL)
    {
        InOrder(subTree->lChild);
        cout << subTree->data <<‘ ‘;
        InOrder(subTree->rChild);
    }
}

template<class T>
void BT<T>::postOrder(BTNode<T>*& subTree)
{
    if (subTree != NULL)
    {
        postOrder(subTree->lChild);
        postOrder(subTree->rChild);
        cout << subTree->data <<‘ ‘;
    }
}

//前序创建二叉树
template<class T>
void BT<T>::CreateBT(BTNode<T>*&subTree)               //注意用引用接收指针  如果只传入指针 形参的指针指向改变 实参不会变
{
    T ch;
    cin >> ch;
        if (ch == RefValue) subTree = NULL;
        else
        {
            subTree = new BTNode<T>(ch);                    //有参构造函数 建立结点
            CreateBT(subTree->lChild);                      //递归
            CreateBT(subTree->rChild);
        }
}

template<class T>
void BT<T>::Size (BTNode<T> * &subTree,int &count)
{
    if (subTree != NULL)
    {
        count++;
        Size(subTree->lChild,count);
        Size(subTree->rChild,count);
    }
    else
    return;
}

template<class T>
void BT<T>::leaf (BTNode<T> * &subTree,int &count)
{
    if(subTree!=NULL)
    {
        if(subTree->lChild==NULL && subTree->rChild==NULL)
        {
            count++;
            return;
        }
        else
        {
            leaf(subTree->lChild,count);
            leaf(subTree->rChild,count);
        }    
    }
}

int main()
{
    int c1=0,c2=0;
    BT<char> t(‘#‘);
    t.CreateBT(t.getRoot());
        cout<<"前序遍历"<<endl; 
    t.PreOrder(t.getRoot());
        cout<<endl<<"中序遍历"<<endl;
    t.InOrder(t.getRoot());
        cout<<endl<<"后序遍历"<<endl;
    t.postOrder(t.getRoot());
    t.Size(t.getRoot(),c1);
        cout<<endl<<"结点总个数："<<c1<<endl;
    t.leaf(t.getRoot(),c2);
    cout<<"叶子结点总个数："<<c2<<endl;
}