数据结构基础之二叉搜索树的思想与实现

柔光的暖阳◎ 2022-08-02 02:17 142阅读 0赞

【摘要】

> 首先，本文阐述二叉搜索树的基本概念，然后，对二叉搜索树的数据结构进行性能分析并给出优化数据结构。最后，贴上了二叉搜索树的创建与遍历的源码。

【正文】

二叉排序树（BinarySortTree）

> 二叉排序树（BinarySortTree）又称二叉查找树、二叉搜索树。
> 
> 它或者是一棵空树；或者是具有下列性质的二叉树：
> 
> 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；若右子树不空，则右子树上所有结点的值均大于它的根结点的值；左、右子树也分别为二叉排序树。
> 
> 若子树为空，查找不成功。

二叉排序树性能分析

> 每个结点的C(i)为该结点的层次数。最坏情况下，当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树，树的深度为，其平均查找长度为(n+1)/2(和顺序查找相同），最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log 2 (n)成正比。

二叉排序树优化

> AVL树、红黑树、Size Balanced Tree(SBT)、Treap(Tree+Heap)这些均可以使查找树的高度为O(log(n))。

【二叉搜索树的创建与遍历源码】

#include <iostream>
 using namespace std;
 //树结点类的实现
 template<class Elem>
 class TreeNode
 {
 public:
 	TreeNode(Elem dataVal,TreeNode* leftVal     = NULL,TreeNode* rightVal     = NULL)
 	{
 		data     = dataVal;
 		left     = leftVal;
 		right     = rightVal;
 	}
 	TreeNode(TreeNode* leftVal     = NULL,TreeNode* rightVal     = NULL)
 	{
 		left     = leftVal;
 		right     = rightVal;
 	}
 	TreeNode* GetLeft()
 	{
 		return left;
 	}
 	TreeNode* GetRight()
 	{
 		return right;
 	}
 	Elem GetVal()
 	{
 		return data;
 	}
 	void SetVal(Elem it)
 	{
 		data     = it;
 	}
 	void SetLeft(TreeNode<Elem>* l)
 	{
 		left     = l;
 	}
 	void SetRight(TreeNode<Elem>* r)
 	{
 		right     = r;
 	}
 	TreeNode* left;
 	TreeNode* right;
 	Elem data;
 };
 //树的类型实现。
 template<class Elem>
 class SearchTree
 {
 public:
 	SearchTree(Elem it)
 	{
 		init(it);
 	}
 	~SearchTree()
 	{
 		DeleteTree(root);
 	}
 	void init(Elem);
 	void DeleteTree(TreeNode<Elem>*);
 	void InsertNode(TreeNode<Elem>*,Elem item);
 	void PreOrder(TreeNode<Elem>*);
 	bool Find(TreeNode<Elem>*,Elem);
 	TreeNode<Elem>* GetRoot()
 	{
 		return root;
 	}
 	void InOrder(TreeNode<Elem>* T);
 	void PostOrder(TreeNode<Elem>* T);
 private:
 	TreeNode<Elem>* root;
 };
 template<class Elem>
 void SearchTree<Elem>::init(Elem item)
 {
 	root     = new TreeNode<Elem>(item,NULL,NULL);
 }
 template<class Elem>
 void SearchTree<Elem>::DeleteTree(TreeNode<Elem>* T)
 {
 	if(T!     = NULL)
 	{
 		DeleteTree(T->GetLeft());
 		DeleteTree(T->GetRight());
 		delete T;
 	}
 }
 //插入结点。
 template<class Elem>
 void SearchTree<Elem>::InsertNode(TreeNode<Elem>* T,Elem item)
 {
 	TreeNode<Elem>* pointer     = NULL;
 	if(T     =     = NULL)
 	{
 		init(item);
 		return;
 	}
 	else pointer     = T;
 	while(1)
 	{
 		if(pointer->GetVal()     =     = item) 
 			return;
 		else 
 			if(pointer->GetVal()>item)
 			{ 
 				if(pointer->GetLeft()     =     = NULL)
 				{
 					pointer->left     = new TreeNode<Elem>(item,NULL,NULL);
 					return;
 				}
 				else
 					pointer     = pointer->left;
 			}
 			else
 			{
 				if(pointer->GetRight()     =     = NULL)
 				{
 					pointer->right     = new TreeNode<Elem>(item,NULL,NULL);
 					return;
 				}
 				else
 					pointer     = pointer->right;
 			}
 	}
 }
 //前序递归遍历。
 template<class Elem>
 void SearchTree<Elem>::PreOrder(TreeNode<Elem>*T)
 {
 	if(T!     = NULL)
 		{
 			cout<<T->GetVal()<<" ";
 			PreOrder(T->GetLeft());
 			PreOrder(T->GetRight());
 		}
 }
 //二叉递归查找
 template<class Elem>
 bool SearchTree<Elem>::Find(TreeNode<Elem>* T,Elem item)
 {
 	if(T     =     = NULL)
 		return false;
 	else if(T->GetVal()>item)
 		return  Find(T->left,item);
 	else if(T->GetVal()<item)
 		return Find(T->right,item);
 	else
 	{
 		item     = T->GetVal();
 		return true;
 	} 
 }
 //中序递归遍历。
 template<class Elem>
 void SearchTree<Elem>::InOrder(TreeNode<Elem>*T)
 {
 	if(T!     = NULL)
 	{
 		InOrder(T->left);
 		cout<<T->data<<" ";
 		InOrder(T->right);
 	}
 }
 //后序递归遍历。
 template<class Elem>
 void SearchTree<Elem>::PostOrder(TreeNode<Elem>* T)
 {
 	if(T!     = NULL)
 	{
 		PostOrder(T->left);
 		PostOrder(T->right);
 		cout<<T->data<<" ";
 	}
 }
 int main()
 {
 	SearchTree<char> A('h');//先创建一个根结点。
 	char it;
 	char item;
 	TreeNode<char>* b;
 	b     = A.GetRoot();
 	cout<<"insert any number in the tree"<<endl;
 	cout<<"when you enter '# 'is end!"<<endl;
 	cin>>item;
 	while(item!     = '#')
 	{
 		A.InsertNode(b,item);    //连续插入结点。
 		cin>>item;
 	}
 	cout<<"PreOrder print all the number:";
 	A.PreOrder(b);
 	cout<<endl;
 	cout<<"inorder print:";
 	A.InOrder(b);
 	cout<<endl;
 	cout<<" PostOrder print:";
 	A.PostOrder(b);
 	cout<<endl;
 	cin>>it;
 	if(A.Find(b,it))
 		cout<<"there is the same number!";
 	else
 		cout<<"there isn't the number!";
 	return 0;
 }

【后序遍历判断是否二叉树】

http://blog.csdn.net/pengyan0812/article/details/46409745