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

#include<iostream>using namespace std;#define FLAG'#'typedef char Record;template<typename Entry>struct Binary_Node{Entry data;Binary_Node<Entry>*left;Binary_Node<Entry>*right;Binary_Node();Binary_Node(const Entry& x);};template<typename Entry>Binary_Node<Entry>::Binary_Node(){left=NULL;right=NULL;}template<typename Entry>Binary_Node<Entry>::Binary_Node(const Entry &x){data=x;left=NULL;right=NULL;}template<class T>class Binary_tree{public:bool empty()const;Binary_tree();Binary_tree(Binary_tree<T>&org);void create_tree(Binary_Node<T>*&tree);//建立二叉树void recursive_copy(Binary_Node<T>*&tree,Binary_Node<T>*&cur);void pre_traverse(Binary_Node<T> *tree);//前序void mid_traverse(Binary_Node<T> *tree);//中序void post_traverse(Binary_Node<T> *tree);//后序遍历void count_node(Binary_Node<T> *tree,int &count);//计算结点数void count_leaves(Binary_Node<T> *tree,int &count);//计算叶子数int tree_height(Binary_Node<T> *tree);//树的高度void Ltree_To_Rtree(Binary_Node<T>*tree);//左右树互换void count_width(Binary_Node<T> *tree,int *count_width,int count);//计算树的最大宽度int get_count()const;//得到树的结点数Binary_Node<T>*get_root()const;void destroy_tree(Binary_Node<T> *tree);//删除数Binary_tree<T>&operator=(Binary_tree&org);protected:T*pre_visit;T*mid_visit;Binary_Node<T>*root;int node_numb;};template<class T>Binary_tree<T>::Binary_tree(){root=NULL;node_numb=0;}template<class T>voidBinary_tree<T>::recursive_copy(Binary_Node<T>*&tree,Binary_Node<T>*&cur) {if(tree==NULL){return;}else{cur=new Binary_Node<T>(tree->data);node_numb++;recursive_copy(tree->left,cur->left);recursive_copy(tree->right,cur->right);}}template<class T>Binary_tree<T>::Binary_tree( Binary_tree<T>&org)recursive_copy(org.root,root);}template<class T>Binary_tree<T>& Binary_tree<T>::operator =(Binary_tree<T>&org) {recursive_copy(org.root,root);return *this;}template<class T>bool Binary_tree<T>::empty() const{return root==NULL;}template<class T>int Binary_tree<T>::get_count()const{return node_numb;}template<class T>void Binary_tree<T>::create_tree(Binary_Node<T>*&tree){T val;cout<<"请输入数据，若空以#输入: ";cin>>val;tree=new Binary_Node<T>(val);if(val==FLAG){tree=NULL;return;}else{node_numb++;if(root==NULL)root=tree;create_tree(tree->left);create_tree(tree->right);}template<class T>Binary_Node<T>* Binary_tree<T>::get_root() const{return root;}template<class T>void Binary_tree<T>::count_node(Binary_Node<T> *tree,int& count){if(tree){count++;count_node(tree->left,count);count_node(tree->right,count);}}template<class T>void Binary_tree<T>::count_leaves(Binary_Node<T> *tree,int& count){if(tree){ if((tree->left==NULL)&&(tree->right==NULL))count++;count_leaves(tree->left,count);count_leaves(tree->right,count);}}template<class T>void Binary_tree<T>::count_width(Binary_Node<T> *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<class T>int Binary_tree<T>::tree_height(Binary_Node<T> *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<class T>void Binary_tree<T>::Ltree_To_Rtree(Binary_Node<T>*tree){if(tree){Ltree_To_Rtree(tree->left);Ltree_To_Rtree(tree->right);if(tree->left!=NULL||tree->right!=NULL){Binary_Node<T>*temp=tree->left;tree->left=tree->right;tree->right=temp;}}}template<class T>void Binary_tree<T>::destroy_tree(Binary_Node<T> *tree){if(tree){Binary_Node<T> *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<class T>void Binary_tree<T>::pre_traverse(Binary_Node<T> *tree) {if(root==NULL){cout<<"树为空，不能遍历"<<endl;return;}if(tree){cout<<" "<<tree->data;pre_traverse(tree->left);pre_traverse(tree->right);}}template<class T>void Binary_tree<T>::mid_traverse(Binary_Node<T> *tree) {if(root==NULL){cout<<"树为空，不能遍历"<<endl;return;}if(tree){mid_traverse(tree->left);cout<<" "<<tree->data;mid_traverse(tree->right);}}template<class T>void Binary_tree<T>::post_traverse(Binary_Node<T> *tree) {if(root==NULL){cout<<"树为空，不能遍历"<<endl;return;}if(tree){post_traverse(tree->left);post_traverse(tree->right);cout<<" "<<tree->data;}}void main(){int m=0,leaves=0,Tree_height;Binary_tree<Record>Tree;Binary_Node<Record>*pp;Tree.create_tree(pp);Binary_tree<Record>Tree1(Tree);cout<<"前序遍历结果为：";Tree.pre_traverse(Tree.get_root());cout<<endl<<"中序遍历结果为：";Tree.mid_traverse(Tree.get_root());cout<<endl<<"后序遍历结果为：";Tree.post_traverse(Tree.get_root());cout<<endl;Tree.count_node(Tree.get_root(),m);cout<<"结点个数为:"<<m<<endl;Tree.count_leaves(Tree.get_root(),leaves);cout<<"叶子个数为:"<<leaves<<endl;Tree_height=Tree.tree_height(Tree.get_root());cout<<"树高度为:"<<Tree_height<<endl;m=0;int *count_wid=new int[Tree_height];for(int i=0;i<Tree_height;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<Tree_height;i++){cout<<"在第"<<i<<"层，共有结点"<<count_wid[i]<<"个"<<endl;if(Max<count_wid[i]){Max=count_wid[i];m=i;}}cout<<"在第"<<m<<"层结点最多，共有结点"<<Max<<"个"<<endl;Tree.Ltree_To_Rtree(Tree.get_root());Tree.destroy_tree(Tree.get_root());delete []count_wid;}树如下：(a)(b) (c)(d) (e) (f) (g)输入：输出：。