二叉查找树算法导论札记

二叉查找树算法导论笔记

---------概念和定理---------

二叉查找树的属性：对于一个二叉查找树t而言，其根结点root的key值比所有的左子树都小，比所有的右子树都大。（包括“等于"的情况）

定理1：设x为一个n个结节点的二叉搜索树的根，调用INORDER-TREE-WALK（x）中序遍历的时间复杂度为@(n)。

定理2：二叉查找树上的下述操作时间复杂度均为O（h），h为树的高度：查询、最小值、最大值、后继、前驱。

定理3：二叉查找树上的插入和删除的时间复杂度也为O（h），h为树的高度。

源代码如下：

#include <iostream>
using namespace std;

typedef int DataType;

typedef struct BSTreeNode{
	DataType data;
	BSTreeNode * left, * right;
	BSTreeNode * pnt;
}BSTreeNode, *BSTree;


void InorderTreeWalk(BSTree t)
{
	if(t!=NULL)  //终止的条件为，到达空的指针 
	{
		InorderTreeWalk(t->left);
		cout<<t->data;
		InorderTreeWalk(t->right);	
	}
}

BSTree TreeSearch(BSTree t,DataType data)
{
	if(t==NULL||t->data == data)
		return t;
	else if (t->data > data)
		return TreeSearch(t->right, data);
	else
		return TreeSearch(t->left, data);
} 

BSTree IterativeTreeSearch(BSTree t,DataType data)
{
		if(t==NULL||t->data == data)
		return t;
		else if (t->data<data)
			t = t->left;
		else
			t = t->right;
}

BSTree TreeMinimum(BSTree t)
{
	while(t->left!=NULL)
		t = t->left;
	return t;
}

BSTree TreeMaximum(BSTree t)
{
	while(t->right = NULL)
 		t = t->right;
	return t;
}

BSTree TreeSuccessor(BSTree t)
{
	BSTree f;
	if(t->right!=NULL)
		return TreeMinimum(t->right);
	f = t->pnt;
	while(f!=NULL&&t==f->right)
	{
		t = f;
		f = f->pnt;
	} 
	return f;
}

BSTree TreePredecessor(BSTree t)
{
	BSTree f;
	if(t->left!=NULL)
		return TreeMaximum(t->left);
	f = t->pnt;
	while(f!=NULL&&t == f->left)
	{
		t = f;
		f = f->pnt;
	}
	return f;
}

void TreeInsert(BSTree &t, BSTree z)
{
	BSTree f=NULL;  // 父结点 
	BSTree x = t;
	while(x!=NULL)
	{
		f=x;
		if(z->data<x->data)
			x=x->left;
		else
			x=x->right;
	}
	z->pnt = f;
	if(f==NULL)
		t = z; 
	else if (z->data<f->data)
		f->left = z;
	else 
		f->right = z;
}

void Transplant(BSTree t, BSTree u, BSTree v)
{
	if(u->pnt==NULL)
		t = v;
	else if(u==u->pnt->left)
	{
		u->pnt->left= v;		
	} 
	else
		u->pnt->right= v;
	if(v!=NULL)
		v->pnt = u->pnt;
}

void TreeDelete(BSTree t,BSTree z)
{
	BSTree y;
	if(z->left==NULL)
		Transplant(t,z,z->right);
	else if(z->right==NULL)
		Transplant(t,z,z->left);
	else 	
	{
		y = TreeMinimum(z->right);
		if (y->pnt == z)
			Transplant(t,y,y->right);
			y->right = z->right;
			y->right->pnt= y;
		Transplant(t,z,y);
		y->left = z->left;
		y->left->pnt= y;
	}
	
}


int main()
{
	return 0;
}

1楼Wentasy昨天 17:14: 学习了。

二叉查找树 算法导论札记

相关推荐

二叉查找树算法导论札记