二叉树基本操作经典实例

该完整程序主要是递归函数的使用及模板的使用，完成了对二叉树基本的链表操作，主要有二叉树的建立，前序、中序、后序遍历，求树的高度，每层结点数（包含树的最大宽度），左右结点对换，二叉树的内存释放，求解树的叶子数。

#include 

using namespace std;

#define  FLAG '#'

typedef  char Record;

template

struct Binary_Node

{

    Entry data;

    Binary_Node*left;

    Binary_Node*right;

    Binary_Node();

    Binary_Node(const Entry& x);

};

template

Binary_Node::Binary_Node()

{

  left=NULL;

  right=NULL;

}

template

Binary_Node::Binary_Node(const Entry &x)

{

    data=x;

    left=NULL;

    right=NULL;

}

template

class Binary_tree

{

public:

    bool empty()const;

    Binary_tree();

    Binary_tree(Binary_tree&org);

    void create_tree(Binary_Node*&tree);//建立二叉树

     void recursive_copy(Binary_Node*&tree,Binary_Node*&cur);

    void pre_traverse(Binary_Node *tree);//前序

    void mid_traverse(Binary_Node *tree);//中序

    void post_traverse(Binary_Node *tree);//后序遍历

    void  count_node(Binary_Node *tree,int &count);//计算结点数

    void count_leaves(Binary_Node *tree,int &count);//计算叶子数

    int tree_height(Binary_Node *tree);//树的高度

    void Ltree_To_Rtree(Binary_Node*tree);//左右树互换

    void count_width(Binary_Node *tree,int *count_width,int count);//计算树的最大宽度

    int get_count()const;//得到树的结点数

    Binary_Node*get_root()const; 

    void destroy_tree(Binary_Node *tree);//删除数

    Binary_tree&operator=(Binary_tree&org);

protected:

    T*pre_visit;

    T*mid_visit;

    Binary_Node*root;    

    int node_numb;

};

template

Binary_tree::Binary_tree()

{

    root=NULL;

    node_numb=0;

}

template

void Binary_tree::recursive_copy(Binary_Node*&tree,Binary_Node*&cur)

{ 

    if(tree==NULL)

    {

        return;

    }

    else

    {  

        cur=new Binary_Node(tree->data);

         node_numb++;

    recursive_copy(tree->left,cur->left);

    recursive_copy(tree->right,cur->right);

    }

}

template

Binary_tree::Binary_tree( Binary_tree&org)

{

    recursive_copy(org.root,root);

}

template

Binary_tree& Binary_tree::operator =(Binary_tree&org)

{

  recursive_copy(org.root,root);

  return *this;

}

template

bool Binary_tree::empty() const

{

    return root==NULL;

}

template

int Binary_tree::get_count()const

{

    return node_numb;

}

template

void Binary_tree::create_tree(Binary_Node*&tree)

{  

    T val; 

    cout<<"请输入数据，若空以#输入: ";

    cin>>val;

    tree=new Binary_Node(val); 

    if(val==FLAG)

    {

        tree=NULL;

        return;

    }

    else

    {           

        node_numb++;

        if(root==NULL)  

            root=tree;             

           create_tree(tree->left);

          create_tree(tree->right);

    }

}

template

Binary_Node* Binary_tree::get_root() const

{

    return root;

}

template

void Binary_tree::count_node(Binary_Node *tree,int& count)

{

    if(tree)

    {

        count++;

        count_node(tree->left,count);

        count_node(tree->right,count);

    }

}

template

void Binary_tree::count_leaves(Binary_Node *tree,int& count)

{

    if(tree)

    {    if((tree->left==NULL)&&(tree->right==NULL))

            count++;

        count_leaves(tree->left,count);    

        count_leaves(tree->right,count);

    }

}

template

void Binary_tree::count_width(Binary_Node *tree,int *count_mid,int count)

{   

    if(tree)

    {   

        if(tree!=root)

            count++;

        count_width(tree->left,count_mid,count);

        count_width(tree->right,count_mid,count);

        count_mid[count]++;

    }

}

template

int Binary_tree::tree_height(Binary_Node *tree)

{

    int count_left=0, count_right=0;

    if(tree==NULL)return 0;

    else

    { 

        count_left=tree_height(tree->left);

        count_right=tree_height(tree->right);

        return(count_left>count_right)?(count_left+1):(count_right+1);

    }

}

template

void Binary_tree::Ltree_To_Rtree(Binary_Node*tree)

{

    if(tree)

    {

    Ltree_To_Rtree(tree->left);    

    Ltree_To_Rtree(tree->right);

    if(tree->left!=NULL||tree->right!=NULL)

    {

        Binary_Node*temp=tree->left;

        tree->left=tree->right;

        tree->right=temp;

    }

    }

}

template

void Binary_tree::destroy_tree(Binary_Node *tree)

{  

    if(tree)

    { 

     Binary_Node *parent=tree;

     destroy_tree(tree->left);    

     destroy_tree(tree->right);

     if(parent==root)

        {

        delete root;

           root=NULL;

           parent=NULL;

           node_numb--;

        }

     else{    

     delete parent;

     parent=NULL;

     node_numb--;}

    }

}

template

void Binary_tree::pre_traverse(Binary_Node *tree)

{

    if(root==NULL)

    {

        cout<<"树为空，不能遍历"<        return;

    }

    if(tree)

    {

        cout<<" "<data;

        pre_traverse(tree->left);

        pre_traverse(tree->right);

    }

}

template

void Binary_tree::mid_traverse(Binary_Node *tree)

{  

    if(root==NULL)

    {

        cout<<"树为空，不能遍历"<        return;

    }

    if(tree)

    {

        mid_traverse(tree->left);

        cout<<" "<data;

        mid_traverse(tree->right);

    }

}

template

void Binary_tree::post_traverse(Binary_Node *tree)

{

    if(root==NULL)

    {

        cout<<"树为空，不能遍历"<        return;

    }

    if(tree)

    {

        post_traverse(tree->left);

        post_traverse(tree->right);

        cout<<" "<data;

    }

}

void main()

{

    int m=0,leaves=0,Tree_height;

    Binary_treeTree;

    Binary_Node*pp;

    Tree.create_tree(pp);

    Binary_treeTree1(Tree);

    cout<<"前序遍历结果为：";

    Tree.pre_traverse(Tree.get_root());

    cout<    Tree.mid_traverse(Tree.get_root());

    cout<    Tree.post_traverse(Tree.get_root());

    cout<    Tree.count_node(Tree.get_root(),m);

    cout<<"结点个数为:"<    Tree.count_leaves(Tree.get_root(),leaves);

    cout<<"叶子个数为:"<    Tree_height=Tree.tree_height(Tree.get_root());

    cout<<"树高度为:"<    m=0;

    int *count_wid=new int[Tree_height];

    for(int i=0;i        count_wid[i]=0;

    Tree.count_width(Tree.get_root(),count_wid,m);

    int Max=count_wid[0];

    m=0;

    for(int i=0;i    {

        cout<<"在第"<        if(Max        {

            Max=count_wid[i];

            m=i;

        }

    }

    cout<<"在第"<    Tree.Ltree_To_Rtree(Tree.get_root());

    Tree.destroy_tree(Tree.get_root());

     delete  []count_wid; 

}

           树如下：               

                     (a)

                  (b)     (c)

               (d)  (e)  (f)  (g) 

输入：

输出：