学步园

很基础的数据结构、不解释= =

#ifndef binaryTreeType_H_
#define binaryTreeType_H_
#define MAXSIZE 1000
#include <iostream>
#include <queue>
#include <math.h>
#include <cstdio>
using namespace std;

//二叉链表的结点
template <class T>
struct binaryNode
{
    T data;
    binaryNode<T>* lchild;
    binaryNode<T>* rchild;
};

template <class T>
class binaryTreeType
{
public:
    binaryNode<T> * root;
    binaryTreeType()//空构造函数，在里边调用creat函数按先序序列建立二叉树的左右链结构
    {
        root=NULL;
    }
    void creatHelp(binaryNode<T> *&r);
    void creat();
    void preOrder(binaryNode<T> *r);//前序遍历
    void inOrder(binaryNode<T> *r);//中序遍历
    void postOrder(binaryNode<T> *r);//后序遍历
    void levelOrder(binaryNode<T> *r);//层序遍历
    int count(binaryNode<T> *r);//结点数
    int height(binaryNode<T> *r);//高度e
    ~binaryTreeType();//析构函数
    void destroy(binaryNode<T> *&r);
private:
    int num;
};
template <class T>
void binaryTreeType<T>::creatHelp(binaryNode<T> *&r)
{
    T temp;
    cin>>temp;
    if(temp=='#')
        r=NULL;
    else
    {
        binaryNode<T> *p=new binaryNode<T>;
        p->data=temp;
        p->lchild=NULL;
        p->rchild=NULL;
        r=p;
        creatHelp(r->lchild);
        creatHelp(r->rchild);
    }
}

template <class T>
void binaryTreeType<T>::creat()
{
    creatHelp(root);
}

template <class T>
void binaryTreeType<T>::destroy(binaryNode<T> *&r)
{
    if(r!=NULL)
    {
        destroy(r->lchild);
        destroy(r->rchild);
        delete r;
        r=NULL;
    }
}

template <class T>
binaryTreeType<T>::~binaryTreeType()
{
    destroy(root);
}

template <class T>
void binaryTreeType<T>::preOrder(binaryNode<T> *r)
{
    if(r!=NULL)
    {
        cout<<r->data<<" ";
        preOrder(r->lchild);
        preOrder(r->rchild);
    }
}

template <class T>
void binaryTreeType<T>::inOrder(binaryNode<T> *r)
{
    if(r!=NULL)
    {
        inOrder(r->lchild);
        cout<<r->data<<" ";
        inOrder(r->rchild);
    }
}

template <class T>
void binaryTreeType<T>::postOrder(binaryNode<T> *r)
{
    if(r!=NULL)
    {
        postOrder(r->lchild);
        postOrder(r->rchild);
        cout<<r->data<<" ";
    }
}

template <class T>
void binaryTreeType<T>::levelOrder(binaryNode<T> *r)
{
    queue<binaryNode<T>*> q;
    binaryNode<T>* cur;
    if(r!=NULL)
    {
        q.push(r);
        while(!q.empty())
        {
            cur=q.front();
            q.pop();
            cout<<cur->data<<" ";
            if(cur->lchild)
                q.push(cur->lchild);
            if(cur->rchild)
                q.push(cur->rchild);
        }
    }
}

template <class T>
int binaryTreeType<T>::count(binaryNode<T> *r)
{
    if(r==NULL)return 0;
    int m=count(r->lchild);
    int n=count(r->rchild);
    return m+n+1;
}

template <class T>
int binaryTreeType<T>::height(binaryNode<T> *r)
{
    if(r==NULL)return 0;
    int m=height(r->lchild);
    int n=height(r->rchild);
    return (m>n)?   (m+1):(n+1);
}
#endif

 测试：

#include <iostream>
#include <cstring>
#include "binaryTreeType.h"
#include <cstdlib>
using namespace std;

int main()
{
   // freopen("in.txt","r",stdin);
   //example: 1#235###4##
    binaryTreeType<char> test;
    test.creat();
    test.preOrder(test.root);
    cout<<endl;
    test.inOrder(test.root);
    cout<<endl;
    test.postOrder(test.root);
    cout<<endl;
    test.levelOrder(test.root);
    cout<<endl;
    cout<<"num of node: "<<test.count(test.root)<<endl;
    cout<<"height of tree: "<<test.height(test.root)<<endl;
    return 0;
}