二叉查找树的实现

// binarySearchTree.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <assert.h>
#include <iostream>
using namespace std;
typedef struct _Node
{
int data;
_Node* parent;
_Node* left;
_Node* right;
}Node;
typedef struct _Tree
{
Node* root;
}Tree;
static Tree* g_tree;
void initNode(Node* node)
{
node->parent = nullptr;
node->left = nullptr;
node->right = nullptr;
}
void init()
{
g_tree = new Tree;
g_tree->root = nullptr;
}
void destoryTree(Node* node)
{
if (nullptr != node)
{
destoryTree(node->left);
destoryTree(node->right);
delete node;
}
}
void finit()
{
destoryTree(g_tree->root);
delete g_tree;
}
void inorderTreeWalk(Node* node)
{
if (nullptr != node)
{
inorderTreeWalk(node->left);
cout << node->data << " ";
inorderTreeWalk(node->right);
}
}
Node* treeSearch(Node* node, int key)
{
if (nullptr == node || key == node->data)
{
return node;
}
if (node->data > key)
{
return treeSearch(node->left, key);
}else
return treeSearch(node->right, key);
}
Node* iterativeTreeSearch(Node* node, int key)
{
while (nullptr != node && key != node->data)
{
if (key < node->data)
{
node = node->left;
}else
node = node->right;
}
return node;
}
Node* treeMinimum(Node* node)
{
assert(nullptr != node);
while (nullptr != node->left)
{
node = node->left;
}
return node;
}
Node* treeMaximum(Node* node)
{
assert(nullptr != node);
while (nullptr != node->right)
{
node = node->right;
}
return node;
}
Node* treeSuccessor(Node* node)
{
assert(nullptr != node);
if (nullptr != node->right)
{
return treeMinimum(node->right);
}
Node* p = node->parent;
while(nullptr != p && node == p->right)
{
node = p;
p = p->parent;
}
return p;
}
Node* treePredecessor(Node* node)
{
assert(nullptr != node);
if (nullptr != node->left)
{
return treeMaximum(node->left);
}
Node* p = node->parent;
while (nullptr != p && node == p->left)
{
node = p;
p = p->parent;
}
return p;
}
void treeInsert(Tree* tree, Node* node)
{
assert(nullptr != node);
Node* y = nullptr;
Node* x = tree->root;
while (nullptr != x)
{
y = x;
if (node->data < x->data)
{
x = x->left;
}else
x = x->right;
}
node->parent = y;
if (nullptr == y)
{
tree->root = node;
}else if (node->data < y->data)
{
y->left = node;
}else
y->right = node;
}
Node* treeDelete(Tree* tree, Node* node)
{
assert(nullptr != node);
Node* y = nullptr;
if (nullptr == node->left
|| nullptr == node->right)
{
y = node;
}else
y = treeSuccessor(node);
Node* x = nullptr;
if (nullptr != y->left)
{
x = y->left;
}else
x = y->right;
if (nullptr != x)
{
x->parent = y->parent;
}
if (nullptr == y->parent)
{
tree->root = x;
}else if (y == y->parent->left)
{
y->parent->left = x;
}else
y->parent->right = x;
if (y != node)
{
node->data = y->data;
}
return y;
}
Node* createNode(int data)
{
Node* node = new Node;
initNode(node);
node->data = data;
return node;
}
int _tmain(int argc, _TCHAR* argv[])
{
init();
for (int i = 0; i < 10; ++ i)
{
Node* p = createNode(i);
treeInsert(g_tree, p);
}
Node* q = createNode(15);
treeInsert(g_tree, q);
for (int i = 20; i < 100; ++ i)
{
Node* p = createNode(i);
treeInsert(g_tree, p);
}
inorderTreeWalk(g_tree->root);
cout << endl;
Node* pFind = treeSearch(g_tree->root, 15);
assert(nullptr != pFind);
cout << "find data = " << pFind->data << endl;
pFind = iterativeTreeSearch(g_tree->root, 15);
assert(nullptr != pFind);
cout << "iterative find data = " << pFind->data << endl;
Node* predecessor = treePredecessor(pFind);
assert(nullptr != predecessor);
cout << pFind->data << "'s predecessor is " << predecessor->data << endl;
Node* successor = treeSuccessor(pFind);
assert(nullptr != successor);
cout << pFind->data << "'s successor is " << successor->data << endl;
pFind = treeDelete(g_tree, pFind);
assert(pFind == q);
cout << "delete pFind success" << endl;
pFind = treeSearch(g_tree->root, 15);
assert(nullptr == pFind);
cout << "not find 15" << endl;
finit();
return 0;
}