binary_tree.h

二叉树实现,里面含有与二叉树有关的各种方法,希望能给初学数据结构的人员带来启发.

#include<iostream>
using namespace std;

#define Record int//

enum Error_code{
	success , not_present , overflow , underflow , range_err , duplicate_error
};
string String(Error_code code);

//struct Binary_node def------------------
struct Binary_node
{
	//data members:
	Record data;
	Binary_node *left ;
	Binary_node *right ;
	
	Binary_node();
	Binary_node(const Record &x);
};
//End def---------------------------------

//class Binary_tree def------------------------
class Binary_tree
{
public:
	Binary_tree();
	bool empty();
	int size()const;
	void clear();
	int height()const;

	void preorder(void (*visit)(Record &));
	void inorder(void (*visit)(Record &));
	void postorder(void (*visit)(Record &));

	Binary_tree(const Binary_tree &copy);
	Binary_tree & operator = (const Binary_tree &copy);
	~Binary_tree();

	void print_tree();
protected:
	//methods:
	int size_root(Binary_node *sub_root)const;
	void clear_root(Binary_node *&sub_root);
	int height_root(Binary_node *sub_root)const;
	void recursive_preorder(Binary_node *sub_root , void (*visit)(Record &));
	void recursive_inorder(Binary_node *sub_root , void (*visit)(Record &));
	void recursive_postorder(Binary_node *sub_root , void (*visit)(Record &));
	Binary_node *copy_tree(Binary_node *sub_root);

	void print_tree_root(Binary_node *&sub_root);
	//members:
	Binary_node *root ;
};
//End def--------------------------------------

//class Search_tree def---------------------------
class Search_tree : public Binary_tree//
{
public:
	//Search_tree()
	Error_code insert(const Record &new_data) ;
	Error_code remove(const Record &target) ;
	Error_code search(Record &target)const ;
protected:
	Error_code search_and_insert(Binary_node *&sub_root ,const Record &new_data) ;
	Error_code remove_root(Binary_node *&sub_root);
	Error_code search_and_destroy(Binary_node *&sub_root,const Record &target);
	Binary_node *search_for_node(Binary_node *sub_root ,const Record &target)const;
};
//End def-----------------------------------------