二進(jìn)制排序樹對于插入和查詢數(shù)據(jù)非常方便. 還有一個平衡的二叉樹. 平衡二叉樹也是一類二叉排序樹，但是在二進(jìn)制排序數(shù)最壞的情況下查詢時間復(fù)雜度為O（n），而平衡二叉樹可以保證每個查詢?yōu)镺（logn），但是由于平衡二叉樹的內(nèi)部特性二叉排序樹+數(shù)據(jù)結(jié)構(gòu)，該實現(xiàn)的特性，在插入，刪除或修改它上花費的時間無法忽略，因此我只是對它有所了解二叉排序樹+數(shù)據(jù)結(jié)構(gòu)，并且沒有實際的代碼. 您可以參考相關(guān)博客:

此可能更廣.

#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
}

新生狗即將上四年級，筆記將以英語進(jìn)行描述. 我希望寫作效果不好.

當(dāng)前，沒有學(xué)習(xí)C ++的模板. 稍后，我將在需要時學(xué)習(xí)它，并且代碼將更改為模板.

本文來自本站，轉(zhuǎn)載請注明本文網(wǎng)址：
http://www.pc-fly.com/a/jisuanjixue/article-286103-1.html