binary_tree.cpp

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

#include "Binary_tree.h"

//function-----------------------------
string String(Error_code code)
{
	string str;
	switch(code)
	{
	case success:
		str = "success";
		break;
	case not_present:
		str = "not_present";
		break;
	case overflow:
		str = "overflow";
		break;
	case underflow:
		str = "underflow";
		break;
	case range_err:
		str = "range error";
		break;
	case duplicate_error:
		str = "duplicate_error";
		break;
	default:
		break;
	}
	return str;
}
//end function def-----------------------

//struct Binary_node def------------------------
Binary_node::Binary_node()
{
	data = -1;
	left = right = NULL;
}


Binary_node::Binary_node(const int &x)
{
	data = x;
	left = right = NULL;
}
//End def---------------------------------------

//class Binary_tree def--------------------------------------------------
Binary_tree::Binary_tree()
{
	root = NULL ;
}

bool Binary_tree::empty()
{
	return root == NULL ;
}

int Binary_tree::size()const
{
	return size_root(root);
}

void Binary_tree::clear()
{
	clear_root(root);
}

int Binary_tree::height()const
{
	return height_root(root);
}

void Binary_tree::preorder(void (*visit)(Record &))
{
	recursive_preorder(root,visit);
}

void Binary_tree::inorder(void (*visit)(Record &))
{
	recursive_inorder(root,visit);
}

void Binary_tree::postorder(void (*visit)(Record &))
{
	recursive_postorder(root,visit);
}

Binary_tree::Binary_tree(const Binary_tree &copy)
{
	root = copy_tree(copy.root);
}

Binary_tree & Binary_tree::operator = (const Binary_tree &copy)
{
	Binary_node *new_root = copy_tree(copy.root);
	clear();
	root = new_root;
	return *this;
}

Binary_tree::~Binary_tree()
{
	clear();
	delete root;
}

void Binary_tree::print_tree()
{
	print_tree_root(root);
}

int Binary_tree::size_root(Binary_node *sub_root)const
{
	if (sub_root != NULL)
		return size_root(sub_root -> left) + 1 + size_root(sub_root -> right);
	return 0 ;
}

void Binary_tree::clear_root(Binary_node *&sub_root)
{
	if (sub_root != NULL)
	{
		clear_root(sub_root -> left);
		clear_root(sub_root -> right);
		delete sub_root;
		sub_root = NULL;
	}
}

int Binary_tree::height_root(Binary_node *sub_root)const
{
	if (sub_root != NULL)
	{
		int height1 = height_root(sub_root -> left) + 1;
		int height2 = height_root(sub_root -> right) + 1;
		return height1 > height2 ? height1 : height2;
	}
	return 0;
}

void Binary_tree::recursive_preorder(Binary_node *sub_root , void (*visit)(Record &))
{
	if (sub_root != NULL)
	{
		(*visit)(sub_root -> data);
		recursive_preorder(sub_root -> left , visit);
		recursive_preorder(sub_root -> right , visit);
	}
}

void Binary_tree::recursive_inorder(Binary_node *sub_root , void (*visit)(Record &))
{
	if (sub_root != NULL)
	{
		recursive_preorder(sub_root -> left , visit);
		(*visit)(sub_root -> data);
		recursive_preorder(sub_root -> right , visit);
	}
}

void Binary_tree::recursive_postorder(Binary_node *sub_root , void (*visit)(Record &))
{
	if (sub_root != NULL)
	{
		recursive_preorder(sub_root -> left , visit);
		recursive_preorder(sub_root -> right , visit);
		(*visit)(sub_root -> data);
	}
}

Binary_node *Binary_tree::copy_tree(Binary_node *sub_root)
{
	if (sub_root != NULL)
	{
		Binary_node *pt = new Binary_node(sub_root -> data);
		pt -> left = copy_tree(sub_root -> left);
		pt -> right = copy_tree(sub_root -> right);
		return pt;
	}
	return NULL;
}
void Binary_tree::print_tree_root(Binary_node *&sub_root)
{
	if (sub_root != NULL)
	{
		print_tree_root(sub_root->left) ;
		cout << sub_root->data << endl ;
		print_tree_root(sub_root->right) ;
	}
}
//End def-----------------------------------------------------------------

//class Search_tree def---------------------------------------------------
Error_code Search_tree::insert(const Record &new_data)
{
	return search_and_insert(root , new_data);
}

Error_code Search_tree::search_and_insert(Binary_node *&sub_root ,const Record &new_data)
{
	if (sub_root == NULL)
	{
		sub_root = new Binary_node(new_data) ;
		if (sub_root == NULL) return overflow;
		return success ;
	}

	if (sub_root->data > new_data)
		return search_and_insert(sub_root -> left , new_data);
	

	if (sub_root->data < new_data)
		return search_and_insert(sub_root -> right , new_data);
	
	return duplicate_error ; 
}

Error_code Search_tree::remove(const Record &target)
{
	return search_and_destroy(root,target);
}

Error_code Search_tree::search(Record &target)const
{
	Binary_node *found = search_for_node(root,target);
	if (found == NULL) return not_present;
	target = found -> data;
	return success;
}

Error_code Search_tree::remove_root(Binary_node *&sub_root)
{
	if (sub_root == NULL) return not_present;
	Binary_node *to_delete = sub_root ;

	if (sub_root -> right == NULL) sub_root = sub_root -> left;
	else if (sub_root -> left == NULL) sub_root = sub_root -> right;
	else{
		to_delete = sub_root -> left;
		Binary_node * parent = sub_root;

		while (to_delete -> right != NULL){
			parent = to_delete ;
			to_delete = to_delete -> right ;
		}
		sub_root -> data = to_delete -> data;
		if (parent == sub_root) sub_root -> left = to_delete -> left ;
		else parent -> right = to_delete -> left;
	}
	delete to_delete;
	return success;	
}

Error_code Search_tree::search_and_destroy(Binary_node *&sub_root,const Record &target)
{
	if (sub_root == NULL || sub_root -> data == target)
		return remove_root(sub_root);
	else if (target < sub_root -> data) 
		return search_and_destroy(sub_root -> left , target);
	else return search_and_destroy(sub_root -> right , target);
}

Binary_node *Search_tree::search_for_node(Binary_node *sub_root ,const Record &target)const
{
	while (sub_root != NULL && sub_root -> data != target)
	{
		if (sub_root -> data > target) 
			sub_root = sub_root -> left;
		else sub_root = sub_root -> right;
	}
	return sub_root;
}
//End def-----------------------------------------