search3.cpp

数据结构的查询方式及其应用

// search3.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "iostream"
using namespace std;
struct Binary_node 
{
	int data;
	int lev;
	Binary_node *left;
	Binary_node *right;
	Binary_node();
};

Binary_node::Binary_node()
{
	left = NULL;
	right =NULL;
	data = 0;
	lev = 0;
}
class Binary_tree
{
public:
	Binary_tree();
	void read();
	bool insert(Binary_node *&sub_root,int data);
	bool search(Binary_node *sub_root,const int data);
	bool del(Binary_node *&sub_root,int data);
	void output(Binary_node *sub_root);
	void level(Binary_node *sub_root);
private:
	bool remove_root(Binary_node *&sub_root);
	Binary_node *root;
	int count;
};
void Binary_tree::level(Binary_node *sub_root)
{
	if (sub_root->left!= NULL || sub_root->right != NULL)
	{
		if(sub_root->left != NULL)
		{
			sub_root->left->lev = sub_root->lev +1;
			level(sub_root->left);
		}
		if (sub_root->right != NULL)
		{
			sub_root->right->lev = sub_root->lev +1;
			level(sub_root->right);
		}
	}

}
Binary_tree::Binary_tree()
{
	root = NULL;
	count = 0;
}
bool Binary_tree::insert(Binary_node *&sub_root,int data)
{
	if (sub_root == NULL)
	{
		sub_root = new Binary_node;
		sub_root->data = data;
		return 1;
	}
	else if(data < sub_root->data)
		return insert(sub_root->left,data);
	else if(data > sub_root->data)
		return insert(sub_root->right,data);
	else return 0;
}
bool Binary_tree::search(Binary_node *sub_root,const int data)
{
	if (sub_root->data == data)
	{
		cout<<sub_root->data<<endl;
		return 1;
	}
	else if(sub_root->data < data)
	{
		cout<<sub_root->data<<',';
		return search(sub_root->right,data);
	}
	else 
	{
		cout<<sub_root->data<<',';
		return search(sub_root->left,data);
	}
	return 0;
}
bool Binary_tree::del(Binary_node *&sub_root,int data)
{
	if (sub_root->data == data)
	{
		remove_root(sub_root);
		return 1;
	}
	else if (sub_root->data < data)
	{
		return del(sub_root->right,data);
	}
	else 
		return del(sub_root->left,data);
	return 0;
}
bool Binary_tree::remove_root(Binary_node *&sub_root)
{
	if (sub_root == NULL)
	{
		return 0;
	}
	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 1;
}
void Binary_tree::output(Binary_node *sub_root)
{
	if (sub_root != NULL)
	{
		for (int i = 0;i <sub_root->lev;i++)
		{
			cout<<' ';
		}
		cout<<sub_root->data<<endl;
		output(sub_root->left);
		output(sub_root->right);
	}
}
void Binary_tree::read()
{
	int x,i = 0;
	cin>>x;
	count = x;
	cout<<"输入先序序列："<<endl;
	while (i!= count && cin >> x)
	{
		insert(root,x);
		i++;
	}
	char y;
	cin >>y;
	cin >>x;
	switch (y)
	{
	case 'S':
		search(root,x);
		break;
	case 'D':
		del(root,x);
		level(root);
		output(root);
		cout<<endl;
		break;
	}
}
int _tmain(int argc, _TCHAR* argv[])
{
	Binary_tree tree;
	tree.read();
	return 0;
}