binary_tree_use_class

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

class node
{
	private:
		int data;
		struct node* left;
		struct node* right;
		struct node* father;
	friend class binary_tree;
};

class binary_tree
{
	public:
		binary_tree();
		void print_inorder(node* ptr);
		void print_preorder(node* ptr);
		void print_postorder(node* ptr);
		void insert_node(int value);
		void delete_node(node *ptr);
		node* find_node(int value);
		node* getroot(){return root;}
		int getdata(node* ptr){return ptr->data;}
		~binary_tree();
	private:
		void freeall(node* ptr);

		node *root;
};
binary_tree::binary_tree(void)
{
	root=NULL;
}
binary_tree::~binary_tree(void)
{
	freeall(root);
}
void binary_tree:: insert_node(int value)
{
 	node *new_node;
 	node *current;
 	node *parent;
 	new_node = (node *)malloc(sizeof(node));
 	new_node->data = value;
 	new_node->left = NULL;
 	new_node->right = NULL;
 	new_node->father=NULL;
 	if(root == NULL)
 	{root=new_node;}
 	else
 	{
 		current = root;
 		while(current != NULL)
 		{
 			parent = current;
 			if(current->data > value)
 			{current = current->left;}
 			else
 			{current = current->right;}
		}
 		if(parent->data > value)
 		{
		 	parent->left = new_node;
		 	new_node->father=parent;
		}
 		else
 		{
		 	parent->right = new_node;
			new_node->father=parent;
		}
 	}
}

node *binary_tree::find_node(int value)
{
	node* ptr=root;
	while(ptr!=NULL)
	{
		if(ptr->data==value)
		{return ptr;}
		else
		{
			if (ptr->data>value)
			{ptr=ptr->left;}
			else
			{ptr=ptr->right;}
		}
	}
	return NULL;
}
void binary_tree::print_inorder(node* ptr)
{
 	if(ptr != NULL)
	 {
 		print_inorder(ptr->left);
 		printf("%d ", ptr->data);
 		print_inorder(ptr->right);
 	}
}

 void binary_tree::print_preorder(node* ptr)
{
	 if(ptr != NULL)
 	{
 		printf("%d ", ptr->data);
 		print_preorder(ptr->left);
 		print_preorder(ptr->right);
	 }
}

void binary_tree::print_postorder(node* ptr)
{
	 if(ptr != NULL)
 	{
 		print_postorder(ptr->left);
 		print_postorder(ptr->right);
 		printf("%d ", ptr->data);
 	}
}

void binary_tree::freeall(node* ptr)	//要從最後一個往前殺
{
	 if(ptr!= NULL)
 	{
 		freeall(ptr->left);
 		freeall(ptr->right);
 		free(ptr);
 	}
}

// 刪除節點
void binary_tree::delete_node(node *ptr)
{
	node *parent = ptr->father;
	if(ptr->left == NULL)		// 情況1: 節點沒有左子樹 如果要刪的是根節點
	{
		if(root == ptr)	// 如果要刪的是根節點
		{root = root->right;}
		else				// 其他
		{
			if( ptr->data > parent->data )
			{parent->right = ptr->right;}//要刪除的節點在父節點右方,所以將父節點的右節點指向刪除節點的右節點
			else
			{parent->left = ptr->right;}//要刪除的節點在父節點左方,所以將父節點的左節點指向刪除節點的右節點
		}
		free(ptr);
	}
	else if(ptr->right == NULL)	// 情況2: 節點沒有右子樹
	{
		if(root!=ptr)
		{
			if( ptr->data > parent->data )
			{parent->right = ptr->left;}//要刪除的節點在父節點右方,所以將父節點的右節點指向刪除節點的左節點
			else
			{parent->left = ptr->left;}//要刪除的節點在父節點左方,所以將父節點的左節點指向刪除節點的左節點
		}
		else
		{root = root->left;}
		free(ptr);
	}
	else						// 情況3: 節點有左右子樹
	{
		node* new_node = ptr->left;
		// 找新結點取得ptr的位置, 新結點要最接近ptr, 以維持ptr左邊小於他，右邊大於他
		//所以是從左邊找最大(右)，或從右邊找最小(左)
		//此例從左邊找最大
		if(new_node->right!=NULL)
		{
			while(new_node->right != NULL)	// 往左子節點之右子樹找最大值當取代點
			{new_node = new_node->right;}
			ptr->right = new_node->left; // 要用new_node取得ptr，所以開始把new_node的子孫灌給ptr
		}
		else
		{ptr->left=new_node->left;}
		ptr->data = new_node->data;		// 取代!!
		free(new_node);	// 刪除next (注意: 不是刪除ptr)
	}
}
 int main()
 {
 	binary_tree bt;
 	int key;
 	node *ptr;
 	int value;

 	while(1)
	{
		scanf("%d",&key);
		switch(key)
		{
			case 1:
				scanf("%d",&value);
				bt.insert_node(value);
				break;
			case 2:
				bt.print_inorder(bt.getroot());
				printf("\n");
				break;
			case 3:
				bt.print_preorder(bt.getroot());
				printf("\n");
				break;
			case 4:
				bt.print_postorder(bt.getroot());
				printf("\n");
				break;
			case 5:
				scanf("%d",&value);
				ptr=bt.find_node(value);
				if(ptr==NULL)
				{printf("cannot delete\n");}
				else
				{
					bt.delete_node(ptr);
					printf("delete %d ok\n",value);//ptr已經刪除，所以要用value來顯示
				}
				break;
			case 6:
				scanf("%d",&value);
				ptr=bt.find_node(value);
				if(ptr==NULL)
				{printf("not found\n");}
				else
				{printf("found: %d\n",bt.getdata(ptr));}
				break;
			case 8:
				return 0;
		}
	}
 	return 0;
 }