首页 > 代码库 > 二叉查找树（二叉排序树、有序二叉树）算法分析及实现

二叉查找树（二叉排序树、有序二叉树）算法分析及实现

2024-07-06 17:18:24   232人阅读

二叉查找树一般采用二叉链表作为其存储结构，我们这次也采用这样的实现。二叉查找树一般有查找、插入和删除等操作，其中查找是基础，没有查找，插入和删除则无从谈起；而删除算是难点，需处理四种不同的情况，分别是：

无左右孩子，（采取直接删除，须处理其父节点指针）

只有左孩子，（采取其父节点指针指向其左孩子）

只有右孩子、（采取其父节点指针指向其右孩子）

左右孩子都存在，（采取以直接前驱或直接后继代替，实现中我们采用直接前驱代替）。

查找的过程比较简单，如果该节点不为空，若其值大于key（要查找的值），则继续查找其左孩子；若其值小于key（要查找的值），则继续查找其右孩子；如果是等于，那么就找到了！

需要特别注意的一点是，查找是不会修改数的结构的，而插入和删除都会改变树的结构，所以在查找中我们传入的参数只是指向根节点的指针，而在插入和删除中我们传入的参数是指针引用，因为插入和删除有可能会改变根节点。举个例子，如果在删除函数中我们传入的只是指向根节点的指针，我们在删除最后一个元素后会得到一颗空树，我们当然可以在删除函数中设置T=NULL（注意是大写的），但是在主函数中呢？会出现什么情况呢？出现的情况是原来指向这棵树的根节点指向了一个无效地址，以后的操作就会出错。总而言之，要注意空树的处理。

二叉查找树的时间性能是其树的高度，平均为O（logn），最坏为O（n）。

实现如下：

#include<iostream>

using namespace std;

typedef int KeyType;

typedef struct BiTree
{
	KeyType data;
	struct BiTree *lchild;
	struct BiTree *rchild;
}BiTree;

bool SearchBST( BiTree *T,KeyType key,BiTree *&f,BiTree *&p); // f为p的父节点，f==p其实是表示f与p都指向了根节点,查找成功时p指向目标节点，失败时p指向最后查找到的节点
bool InsertBST(BiTree *&T,KeyType key);						  // 
bool DeleteBST(BiTree *&T,KeyType key);						  //
void DeleteNode(BiTree *&T,BiTree *f,BiTree *p);			  //
void MidOrderTraverse(BiTree *T);							  //

bool SearchBST( BiTree *T,KeyType key,BiTree *&f,BiTree *&p) // BiTree *&p,p为指针的引用;f为p的父节点
{
	f=T;
	p=T;
	while(T!=NULL&&T->data!=key)
	{
		if(key<T->data)
		{
			f=p;
			p=T;
			T=T->lchild;
		}
		else
		{
			f=p;
			p=T;
			T=T->rchild;
		}
	}
	if(T!=NULL) //T->data=http://www.mamicode.com/=key>


联系
我们