二叉树基本操作经典实例

本程序由SOGOF完成

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

#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);

}