二叉查找树 – Alec's Blog

二叉查找树（Binary Search Tree）：

二叉查找树是一种特殊的二叉树。树中的每一个节点都父节点，左子节点，右子节点。左子节点小于等于该节点，右子节点大于等于该节点。

二叉查找树包含Search, Minimum, Maximum, Predecessor(前趋), Successor(后续), Insert, Delete等操作。这些操作的时间复杂度均为[latex]O(h)[/latex]，其中h为树的高度。

二叉查找树实现代码（部分功能）：

// BinarySearchTree.h
#pragma once
#include 

using namespace std;

template  class BinarySearchTree;

// 树的节点
template 
class TreeNode
{
	friend BinarySearchTree;
public:
	TreeNode(){data = 0; parent = 0; left = 0; right = 0;};
	TreeNode(T value) {data = value; parent = 0; left = 0; right = 0;}
private:
	T data;	
	TreeNode* parent;
	TreeNode* left;
	TreeNode* right;	
};

// 二叉查找树
template 
class BinarySearchTree
{
public:
	BinarySearchTree(void) {root = 0;}
	BinarySearchTree(T* dataArray, int count)	// 使用数组构造二叉查找树
	~BinarySearchTree(void) { }

	void InOrderTreeWalk();
	void Insert(T value);
	void Delete(T value);
	int MaxValue();	// 函数返回值：0-找到最大值 -1-未找到最大值（空树）
	int MinValue();	// 函数返回值：0-找到最小值 -1-未找到最小值（空树）
	int Successor(T value);	// 返回值为0/-1，表示是否找到
	int Predecessor(T value); // 返回值为0/-1，表示是否找到

private:
	void InOrderTreeWalk(TreeNode *node);			// 按顺序输出树中的所有数据
	TreeNode* Search(T target, TreeNode *node);	// 在树中查找给定的某个关键字对应的节点
	TreeNode* Search(T target);
	TreeNode* Minimum(TreeNode *node);			// 查询树中关键字最小的节点	
	TreeNode* Maximum(TreeNode *node);			// 查找树中关键字最大的节点
	TreeNode* Successor(TreeNode *node);			// 返回指定节点的后继节点
	TreeNode* Predecessor(TreeNode *node);		// 返回指定节点的前趋节点
	void Insert(TreeNode *node);						// 插入新节点
	TreeNode* Delete(TreeNode *node);				// 删除指定节点

private:
	TreeNode *root;
};

template 
BinarySearchTree::BinarySearchTree(T* dataArray, int count)
{
	root = 0;
	for (int i=0; i<count; ++i)
	{
		Insert(dataArray[i]);
	}
		
}

template 
void BinarySearchTree::InOrderTreeWalk()
{
	InOrderTreeWalk(root);
	cout << endl;
}

template 
void BinarySearchTree::Insert(T value)
{
	TreeNode* newNode = new TreeNode(value);
	Insert(newNode);
}

template 
void BinarySearchTree::Delete(T value)
{
	TreeNode* delNode = Search(value);
	if (delNode != 0)
		Delete(delNode);
}

template 
int BinarySearchTree::MaxValue()
{
	if (root == 0)
	{
		cout << "The tree is empty." << endl;
		return -1;
	}

	cout << "The max value is " << Maximum(root)->data << endl; // 输出最大值

	return 0;
}

template 
int BinarySearchTree::MinValue()
{
	if (root == 0)
	{
		cout << "The tree is empty." << endl;
		return -1;
	}

	cout << "The min value is " << Minimum(root)->data << endl; // 输出最大值

	return 0;
}

template 
int BinarySearchTree::Successor(T value)
{
	TreeNode* node = Search(value);
	TreeNode* successor = 0;

	if (node == 0)	// 输入value在树中不存在
	{
		cout << value << " is not exit in tree." << endl;
		return -1;
	}

	successor = Successor(node);
	if (successor == 0)
	{
		cout << "There is no successor of " << value << " in the tree." << endl;
		return -1;
	}
	else
		cout << "The successor of "<< value << " is " << successor->data << endl;

	return 0;
}

template 
int BinarySearchTree::Predecessor(T value)
{
	TreeNode* node = Search(value);
	TreeNode* predecessor = 0;

	if (node==0)
	{
		cout << value <<" is not exit in the tree." << endl;
		return -1;
	}

	predecessor = Predecessor(node);
	if (predecessor == 0)
	{
		cout << "There is no predecessor of " << value << " in the tree." << endl;
		return -1;
	}
	else
		cout << "The predecessor of " << value << " is " << predecessor->data << endl;

	return 0;
}


template 
void BinarySearchTree::InOrderTreeWalk(TreeNode *node)
{
	if (node == 0)
		return;
	else 
	{
		InOrderTreeWalk(node->left);
		cout << node->data << " ";
		InOrderTreeWalk(node->right);
	}
}


template 
TreeNode* BinarySearchTree::Search(T target)
{
	return Search(target, root);
}

template 
TreeNode* BinarySearchTree::Search(T target, TreeNode *node)
{
	if (node == 0 || node->data == target)
		return node;

	if (target < node->data)
		return Search(target, node->left);
	else
		return Search(target, node->right);
}

template 
TreeNode* BinarySearchTree::Minimum(TreeNode *node)
{
	while (node!=0 && node->left!=0)
	{
		node = node->left;
	}

	return node;
}

template 
TreeNode* BinarySearchTree::Maximum(TreeNode *node)
{
	while (node!=0 && node->right!=0)
	{
		node = node->right;
	}

	return node;
}

template 
TreeNode* BinarySearchTree::Successor(TreeNode *node)
{
	if (node->right != 0)
		return Minimum(node->right);

	while (node->parent!=0 && node == node->parent->right)	// parent.data < node.data
	{
		node = node->parent;
	}

	return node->parent;
}

template 
TreeNode* BinarySearchTree::Predecessor(TreeNode *node)
{
	if (node->left != 0)
		return Maximum(node->left);

	while (node->parent!=0 && node==node->parent->left) // parent.data > node.data
	{
		node = node->parent;
	}

	return node->parent;
}


template 
void BinarySearchTree::Insert(TreeNode *node)
{
	TreeNode *parentNode = 0;
	TreeNode *currentNode = root;

	while (currentNode != 0)	// 确定node的父节点（即插入位置）
	{
		parentNode = currentNode;
		if (node->data < currentNode->data)
			currentNode = currentNode->left;
		else
			currentNode = currentNode->right;
	}

	node->parent = parentNode;

	if (parentNode == 0)	// 空树
		root = node;
	else
	{
		if (node->data < parentNode->data)	// 确定node为父节点的左子结点还是右子节点
			parentNode->left = node;
		else
			parentNode->right = node;
	}
}

template 
TreeNode* BinarySearchTree::Delete(TreeNode *node)
{
	// 确定需要删除的节点的位置
	TreeNode* delNode;
	if (node->left==0 || node->right==0)
		delNode = node;
	else
		delNode = Successor(node);


	// 
	TreeNode* nonNullChildNode;
	if (delNode->left != 0)
		nonNullChildNode = delNode->left;
	else
		nonNullChildNode = delNode->right;

	if (nonNullChildNode != 0)
		nonNullChildNode->parent = delNode->parent;

	if (delNode->parent == 0)
		root = nonNullChildNode;
	else if (delNode == delNode->parent->left)
		delNode->parent->left = nonNullChildNode;
	else
		delNode->parent->right = nonNullChildNode;

	if (delNode != node)
		node->data = delNode->data;

	return delNode;

}

测试程序：

// main.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "BinarySearchTree.h"

int _tmain(int argc, _TCHAR* argv[])
{
	int data[] = {15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9};

// 	BinarySearchTree bst;
// 	for (int i=0; i<sizeof(data)/sizeof(int); ++i)
// 	{
// 		bst.Insert(data[i]);
// 	}

	BinarySearchTree bst(data, sizeof(data)/sizeof(int));
	
	cout << sizeof(data) << endl;
	bst.InOrderTreeWalk();
	bst.MaxValue();
	bst.MinValue();
	bst.Delete(6);
	bst.InOrderTreeWalk();
	bst.Successor(20);
	bst.Predecessor(2);
	bst.Predecessor(13);

	return 0;
}

随机构造的二叉查找树：

使用随机方法由输入序列构造二叉查找树，它通过按随机的顺序，将序列中各元素插入一颗初始为空的树。输入元素的各种排列是等概率的。

随机构造的二叉查找树的期望高度为：[latex]O(\lg{n})[/latex]。

对上述程序中的部分代码进行修改即可使用随机方法构造二叉查找树，修改、添加的代码如下：

#include 
#include 

template 
class BinarySearchTree
{
public:
	BinarySearchTree(T* dataArray, int count);	// 使用数组构造二叉查找树(随机构造版本)

private:
	void RandomizedInsert(T* dataArray, int start, int end);	// 随机插入算法
};

template 
BinarySearchTree::BinarySearchTree(T* dataArray, int count)
{
	root = 0;
	srand(time(0));	// 初始化随机数
	RandomizedInsert(dataArray, 0, count-1);
		
}

template 
void BinarySearchTree::RandomizedInsert(T* dataArray, int start, int end)
{
	if (start > end)
		return;

	if (start == end)
	{
		Insert(dataArray[start]);
		return;
	}

	int randPos = start + (double)rand() / RAND_MAX * (end-start);	// 随机选择插入元素
	Insert(dataArray[randPos]);
	RandomizedInsert(dataArray, start, randPos-1);
	RandomizedInsert(dataArray, randPos+1, end);
}

发送评论 编辑评论

发送评论编辑评论