二进制排序树（数据结构）

二进制排序树对于插入和查询数据非常方便. 还有一个平衡的二叉树. 平衡二叉树也是一类二叉排序树，但是在二进制排序数最坏的情况下查询时间复杂度为O（n），而平衡二叉树可以保证每个查询为O（logn），但是由于平衡二叉树的内部特性二叉排序树+数据结构，该实现的特性，在插入，删除或修改它上花费的时间无法忽略，因此我只是对它有所了解二叉排序树+数据结构，并且没有实际的代码. 您可以参考相关博客:

此可能更广.

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct BinaryTree
{
	int data;
	BinaryTree *parent,*left,*right;
	BinaryTree()
	{
		data=-1;
		parent=left=right=NULL;
	}
};
BinaryTree  *root=new BinaryTree;
bool insert(BinaryTree *R,int x);
bool search(BinaryTree *R,int x);
void InOrderTra(BinaryTree *R);
bool dele(BinaryTree *R,int x);
void clear(BinaryTree *R);
int getheight(BinaryTree *R);
int size(BinaryTree *R);
bool empty();
int main()
{
	int n;
	if(insert(root,1)) cout<<"Successfully Insert Value 1\n";
	if(dele(root,1)) cout<<"Successfully Delete Value 1\n";
	
	while(cin>>n)
	{
		insert(root,n);
	}
	
	if(search(root,6))	cout<<"Found!"<<endl;
	cout<<"Depth: "<<getheight(root)<<endl;
	cout<<"Size: "<<size(root)<<endl;
	
	InOrderTra(root);cout<<endl;
	
	dele(root,10);	//10 12 13 5 7 6 4
	InOrderTra(root);cout<<endl;
	insert(root,6);
	
	dele(root,7);
	InOrderTra(root);cout<<endl;
	insert(root,7);InOrderTra(root);cout<<endl;
	
	dele(root,5);
	InOrderTra(root);cout<<endl;
	
	if(empty())	cout<<"Empty\n";
	else cout<<"Not Yet\n";
	
	clear(root);
	if(empty())	cout<<"Empty\n";
	else cout<<"Not Yet\n";/**/
	
	return 0;
}
bool insert(BinaryTree *R,int x)
{
	if(R->data==-1)
	{
		R->data=x;
		return 1;
	}
	else if(R->data==x)		//this value has already been inserted
		return 0;
	else 
	{
		BinaryTree *node;//10 12 13 5 7 6 4
		if(x<R->data)
		{
			if(R->left==NULL)
			{
				R->left=new BinaryTree;
				node=R->left;
				node->parent=R;
			}
			else node=R->left;
		}
		else if(x>R->data)
		{
			if(R->right==NULL)
			{
				R->right=new BinaryTree;
				node=R->right;
				node->parent=R;
			}
			else node=R->right;
		}
		insert(node,x);
	}
}
bool search(BinaryTree *R,int x)
{
	if(R==NULL)	return 0;
	else if(x==R->data)	return 1;
	else if(x<R->data)
		search(R->left,x);
	else search(R->right,x);
}
void InOrderTra(BinaryTree *R)	//found sth accidently -- if you traverse a binarytree in order, all the numbers will be printed out in increasing order
{
	if(R==NULL)	return;
	InOrderTra(R->left);
	cout<<R->data<<endl;
	InOrderTra(R->right);
}
bool dele(BinaryTree *R,int x)
{
	if(R==NULL)	return 0;	//if this value is not in this tree, return false
	if(x<R->data)	dele(R->left,x);
	else if(x>R->data)	dele(R->right,x);
	else
	{
		if(R->left==NULL&&R->right==NULL)	//if this value is on the leaf
		{
			if(R==root)		//if this value is also on the root
				R->data=-1;		//just reset root's value
			else
			{
				BinaryTree *Pra=R->parent;		//or must alter its parent's left/right child to NULL
				if(Pra->left==R)	Pra->left=NULL;
				else Pra->right=NULL;
				delete R;	//only then can you delete R, otherwise there may be a TLE
			}
		}
		else 
		{
			BinaryTree *node;
			if(R->left==NULL||R->right==NULL)	//if this node has only one child
			{
				node=(R->left==NULL)? R->right: R->left;	//use its left/right child's value to cover its original value
				R->data=node->data;
				R->left=R->right=NULL;	//remember to alter them to NULL
			}
			else		//if this node has 2 children (complicated situation...)
			{
				node=R->right;		//need to find out the least value on its right subsidiary tree
				while(node->left!=NULL)	
					node=node->left;
				R->data=node->data;	//use this value to cover the original
				BinaryTree *r=node->right;	//attention! this node may also have a right subsidiary tree!
				if(node->parent!=R)	//if this node's parent is not T
					node->parent->left=r;	//alter its parent's left child to r
				else R->right=r;	//else alter R's right child to r
			}
			delete node;
		}
	}
	return 1;
}
void destroy()
{
	root=NULL;
}
void clear(BinaryTree *R)
{
	if(R==NULL)	return;
	clear(R->left);
	clear(R->right);
	delete R;
	if(R==root)	
		destroy();
}
bool empty()
{
	if(root!=NULL)
		if(root->data!=-1)
			return 0;
	return 1;
}
int getheight(BinaryTree *R)
{
	if(R==NULL)
		return 0;
	return max(getheight(R->left),getheight(R->right))+1;	//the max depth of left subsidiary tree or right subsidiary tree plus 1 will be the answer
}
int size(BinaryTree *R)
{
	if(R==NULL)
		return 0;
	return size(R->left)+size(R->right)+1; //the number of nodes of left subsidiary tree plus the number of nodes of the right plus 1 will be the answer
}

新生狗即将上四年级，笔记将以英语进行描述. 我希望写作效果不好.

当前，没有学习C ++的模板. 稍后，我将在需要时学习它，并且代码将更改为模板.

本文来自本站，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-286103-1.html