算法导论第12章-搜索二叉树伪代码的C++程序全实现

搜索二叉树的特性：左子树比根小，右子树比根大。

如下图：

算法导论这本书的伪代码其实非常清晰，这是她比很多其他书更优秀的特点。

但是实实在在的测试程序更有利于学习。

插入只会在叶子节点发生，如插入值13的图：

删除比较麻烦，有几种情况，如下图：

下面是本章节中所有伪代码的C++程序，包括测试程序：

原创地址：http://blog.csdn.net/kenden23/article/details/15335057

void inorderTreeWalk(BinaryTree *root, void (*visit)(BinaryTree*))
{
	if(!root) return;
	inorderTreeWalk(root->left, visit);
	visit(root);
	inorderTreeWalk(root->right, visit);
}

void treePrint(BinaryTree *node)
{
	cout<<node->val<<"  ";
}

BinaryTree* treeSearch(BinaryTree *root, int key)
{
	if(root==nullptr || key == root->val) return root;
	if(key<root->val) return treeSearch(root->left, key);
	else return treeSearch(root->right, key);
}

BinaryTree* iterativeTreeSearch(BinaryTree *root, int key)
{
	BinaryTree *cur = root;
	while (cur && cur->val != key)
	{
		if(key<cur->val) cur=cur->left;
		else cur=cur->right;
	}
	return cur;
}

BinaryTree* treeMinimum(BinaryTree *root)
{
	BinaryTree *cur = root;
	while (cur->left)
	{
		cur = cur->left;
	}
	return cur;
}

BinaryTree* treeMaximum(BinaryTree *root)
{
	BinaryTree *cur = root;
	while (cur->right)
	{
		cur = cur->right;
	}
	return cur;
}

BinaryTree* treeSuccesor(BinaryTree *node)
{
	if(node->right) return treeMinimum(node->right);
	BinaryTree *p = node->parent;
	while (p && node == p->right)
	{
		node = p;
		p = p->parent;
	}
	return p;
}

void treeInsert(BinaryTree *root, BinaryTree *node)
{
	BinaryTree *pre = nullptr;
	BinaryTree *cur = root;
	while (cur)
	{
		pre = cur;
		if(node->val < cur->val) cur = cur->left;
		else cur = cur->right;
	}
	node->parent = pre;
	if(!pre) root = node;
	else if (node->val<pre->val)
	{
		pre->left = node;
	}
	else
	{
		pre->right = node;
	}
}

//v查到u的位置，并处理了其v的新的parent和u的parent一样，但是没有处理孩子节点
void transplant(BinaryTree *root, BinaryTree *u, BinaryTree *v)
{
	if(u->parent == nullptr) root = v;
	else if (u == u->parent->left)
	{
		u->parent->left = v;
	}
	else
	{
		u->parent->right = v;
	}
	if(v) v->parent = u->parent;
}

void treeDelete(BinaryTree *root, BinaryTree *node)
{
	if(!node) return;
	if(!node->left) transplant(root, node, node->right);
	else if (!node->right)
	{
		transplant(root, node, node->left);
	}
	else
	{
		BinaryTree *p = treeMinimum(node->right);
		if(p->parent != node)
		{
			transplant(node->right, p, p->right);
			p->right = node->right;
			p->right->parent = p;
		}
		p->left = node->left;
		p->left->parent = p;
	}
}

测试主程序：

#include<iostream>

using namespace std;

void testSearch(BinaryTree *root, int key)
{
	BinaryTree *st = treeSearch(root, key);
	BinaryTree *sti = iterativeTreeSearch(root, key);
	if(st == sti)
		cout<<"treeSearch and IterativeTreeSearch produce the same result. Correct!\n";

	if(st->parent)
		cout<<"Search parent: "<<st->parent->val<<endl;
	else cout<<"No parent."<<endl;

	cout<<"Search value is: "<<st->val<<"\n";

	if(st->left)
		cout<<"Search left: "<<st->left->val<<"\n";
	else cout<<"No left child."<<endl;

	if(st->right)
		cout<<"Search right: "<<st->right->val<<"\n";
	else cout<<"No right child."<<endl;
	cout<<endl;
}

int main()
{
	BinaryTree t1(15);
	BinaryTree t2(23);
	BinaryTree t3(13);
	BinaryTree t4(43);
	BinaryTree t5(25);
	BinaryTree t6(46);
	BinaryTree t7(37);
	BinaryTree t8(28);
	BinaryTree t9(19);
	BinaryTree *root = new BinaryTree(30);

	treeInsert(root, &t2);
	treeInsert(root, &t3);
	treeInsert(root, &t4);
	treeInsert(root, &t5);
	treeInsert(root, &t6);
	treeInsert(root, &t7);
	treeInsert(root, &t8);
	treeInsert(root, &t9);

	cout<<"Print and In order test:"<<endl;
	inorderTreeWalk(root,treePrint);
	cout<<endl<<endl;

	cout<<"Search test:\n";
	testSearch(root, 13);

	cout<<"Tree minimum test:\n";
	cout<<treeMinimum(root)->val<<endl;

	cout<<"Tree maximum test:\n";
	cout<<treeMaximum(root)->val<<endl;

	cout<<"Tree succesor test:\n";
	cout<<t5.val<<"'s succesor is: ";
	cout<<treeSuccesor(&t5)->val<<endl;

	cout<<"Tree insert test:\n";
	BinaryTree ti(18);
	treeInsert(root, &ti);
	inorderTreeWalk(root,treePrint);
	cout<<endl;

	cout<<"Tree delete test:\n";
	treeDelete(root, &t5);
	inorderTreeWalk(root,treePrint);
	cout<<endl;

	delete root;
	system("pause");
	return 0;
}

然后是测试结果：

可以看到所有功能都实现了。