头文件——————————————————————————————
#ifndef _BINARY_SEARCH_TREE_H_
#define _BINARY_SEARCH_TREE_H_
#include <stdlib.h>
#include <iomanip>
#include <iostream>
#include <stack>
#include <set>
#define Element int
struct TreeNode
{
Element data;
struct TreeNode *left;
struct TreeNode *right;
};
typedef struct TreeNode *Position;
typedef Position BinarySearchTree;
void MakeEmpty(BinarySearchTree* pbst);
Position Find(Element x, BinarySearchTree bst);
Position FindMin(BinarySearchTree bst);
Position FindMax(BinarySearchTree bst);
void Insert(Element x, BinarySearchTree* pbst);
void Delete(Element x, BinarySearchTree* pbst);
Element Retrieve(Position p);
void PrintTree(BinarySearchTree bst, int Depth, int ctrl);
void PreOrder(BinarySearchTree bst);
void InOrder(BinarySearchTree bst);
void PostOrder(BinarySearchTree bst);
void PreOrderNotRecursion(BinarySearchTree bst);
void InOrderNotRecursion(BinarySearchTree bst);
void PostOrderNotRecursion(BinarySearchTree bst);
#endif
源文件——————————————————————————————
#include "BinarySearchTree.h"
void MakeEmpty(BinarySearchTree* pbst)
{
if(NULL != (*pbst))
{
MakeEmpty(&((*pbst)->left));
MakeEmpty(&((*pbst)->right));
free(*pbst);
*pbst = NULL;
}
return ;
}
Position Find(Element x, BinarySearchTree bst)
{
while(NULL != bst)
{
if(x < Retrieve(bst))
bst = bst->left;
else if(x > Retrieve(bst))
bst = bst->right;
else
break;
}
return bst;
}
Position FindMin(BinarySearchTree bst)
{
while(NULL != bst && NULL != bst->left)
bst = bst->left;
return bst;
}
Position FindMax(BinarySearchTree bst)
{
while(NULL != bst && NULL != bst->right)
bst = bst->right;
return bst;
}
void Insert(Element x, BinarySearchTree* pbst)
{
if(NULL == *pbst)
{
Position tmp = (Position)malloc(sizeof(struct TreeNode));
if(NULL == tmp)
return ;
tmp->data = x;
tmp->left = tmp->right = NULL;
*pbst = tmp;
}
else if(x < (*pbst)->data)
Insert(x, &((*pbst)->left));
else if(x > (*pbst)->data)
Insert(x, &((*pbst)->right));
else
return ;
}
void Delete(Element x, BinarySearchTree* pbst)
{
if(NULL == *pbst)
return ;
if(x < (*pbst)->data)//go left
Delete(x, &((*pbst)->left));
else if(x > (*pbst)->data)//go right
Delete(x, &((*pbst)->right));
else //the x is found, the *pbst points to the x
{
if(NULL != (*pbst)->left && NULL != (*pbst)->right)//the x has two children
{
Position tmp = FindMin((*pbst)->right);
(*pbst)->data = tmp->data;
Delete((*pbst)->data, &((*pbst)->right));
}
else //the x has one or none child
{
Position tmp = (*pbst);
if(NULL != (*pbst)->left) //the x has left child
(*pbst) = tmp->left;
else if(NULL != (*pbst)->right) //the x has right child
(*pbst) = tmp->right;
else //the x has none child
(*pbst) = NULL;
free(tmp);
}
}
}
Element Retrieve(Position p)
{
return p->data;
}
void PrintTree(BinarySearchTree bst, int Depth, int ctrl)//ctrl:0=root 1=left 2=right
{
if(NULL != bst)
{
std::cout<<std::setw(Depth);
if(0 == ctrl)
std::cout<<"rt:";
else if(1 == ctrl)
std::cout<<"l";
else if(2 == ctrl)
std::cout<<"r";
std::cout<<bst->data<<std::endl;
PrintTree(bst->left, Depth+3, 1);
PrintTree(bst->right, Depth+3, 2);
}
}
void PreOrder(BinarySearchTree bst)
{
if(NULL != bst)
{
std::cout<<bst->data<<"-";
PreOrder(bst->left);
PreOrder(bst->right);
}
}
void InOrder(BinarySearchTree bst)
{
if(NULL != bst)
{
InOrder(bst->left);
std::cout<<bst->data<<"-";
InOrder(bst->right);
}
}
void PostOrder(BinarySearchTree bst)
{
if(NULL != bst)
{
PostOrder(bst->left);
PostOrder(bst->right);
std::cout<<bst->data<<"-";
}
}
void InOrderNotRecursion(BinarySearchTree bst)//二叉查找数的非递归版中序遍历，利用栈来模拟函数递归调用
{
std::stack<Position> s;
while(NULL != bst)//沿着最左的方向将左儿子依次压入栈中
{
s.push(bst);
bst = bst->left;
}
while(!s.empty())
{
Position pos = s.top();
s.pop();
std::cout<<pos->data<<"-";
if(NULL != pos->right)//pos has right child
{
pos = pos->right;
while(NULL != pos)//沿着最左的方向将左儿子依次压入栈中
{
s.push(pos);
pos = pos->left;
}
}
}
}
void PreOrderNotRecursion(BinarySearchTree bst)//二叉查找数的非递归版先序遍历
{
std::stack<Position> s;
s.push(bst);
while(!s.empty())
{
Position pos = s.top();
s.pop();
std::cout<<pos->data<<"-";
if(NULL != pos->right)//如果pos有右儿子就先将其右儿子压入栈中
s.push(pos->right);
if(NULL != pos->left)//如果pos有左儿子就再将其左儿子压入栈中
s.push(pos->left);
}
}
void PostOrderNotRecursion(BinarySearchTree bst)//二叉查找数的非递归版后序遍历
{
std::stack<Position> s;
std::set<Position> rchild_visited;
while(NULL != bst)//沿着最左的方向将左儿子依次压入栈中
{
s.push(bst);
bst = bst->left;
}
while(!s.empty())
{
Position pos = s.top();
//s.pop();
if(NULL == pos->right)//pos没有右儿子因此可以直接访问pos
{
std::cout<<pos->data<<"-";
s.pop();
}
else if(rchild_visited.find(pos) == rchild_visited.end())
{//pos有右儿子我们不可以访问pos，需要先访问完其右子树后才可访问pos
//因此要进入其右儿子中递归访问右子树同时标记pos的右儿子已经被我们访问过了
rchild_visited.insert(pos);
pos = pos->right;
while(NULL != pos)//把右子树的根连同其左儿子沿着左儿子的方向依次压入栈中
{
s.push(pos);
pos = pos->left;
}
}
else if(rchild_visited.find(pos) != rchild_visited.end())
{//此时pos右儿子已经被访问过了因此我们可以直接访问pos了
std::cout<<pos->data<<"-";
rchild_visited.erase(pos);
s.pop();
}
}
}