复习了二叉搜索树的实现，包括插入、查找和删除操作，顺便做了下二叉树的三种遍历操作。全部操作采用非递归方式。
#include<iostream>
#include<stack>
using namespace std;
typedef int T; // 值类型
// 节点定义
struct node {
T val;
node *left,*right;
node(const T& val):val(val),left(NULL),right(NULL){
}
};
typedef node* nodePtr; // 节点指针
// 二叉搜索树实现
class BST {
public:
BST(nodePtr r=NULL):root(r){
}
// 二叉树插入元素
void insert(const T& val) {
if(root==NULL) {
root=new node(val);return;
}
//cur为当前节点 pre为cur的 前驱节点
node *cur=root,*pre;
//遍历找到合适的插入位置
while(cur) {
pre=cur; // 记录前驱节点
cur=cur->val>val?cur->left:cur->right; // 前进
}
//根据前驱节点的值 判断插入左还是右
if(pre->val>val) pre->left=new node(val);
else pre->right=new node(val);
}
// 二叉树查找元素
nodePtr find(const T& val) {
nodePtr cur=root;
while(cur) {
if(cur->val==val) return cur;
cur=cur->val>val?cur->left:cur->right; // 前进
}
return NULL;
}
// 删除指定元素
void del(const T& val) {
//cur为当前节点 pre为cur的 前驱节点
nodePtr cur=root,pre;
while(cur) {
if(cur->val==val) break;
pre=cur;
cur=cur->val>val?cur->left:cur->right; // 前进
}
// 如果未找到节点
if(!cur) return;
// 如果是叶子节点 直接删除即可并改变前驱节点的指向为空
if(cur->left==NULL&&cur->right==NULL) {
if(cur==root) // 如果刚好是根节点
root=NULL;
else if(pre->left==cur) // 左叶子
pre->left=NULL;
else // 右叶子
pre->right=NULL;
delete cur;
} // 如果是单儿子节点 接删除即可并改变前驱节点的指向为儿子节点
else if(cur->left==NULL||cur->right==NULL) {
if(cur==root) // 根节点
root=cur->left==NULL?cur->right:cur->left;
else if(pre->left==cur) // 左儿子
pre->left=cur->left==NULL?cur->right:cur->left;
else // 右儿子
pre->right=cur->left==NULL?cur->right:cur->left;
delete cur;
} // 双儿子节点
else {
//找到左儿子中最大值
pre=cur;
nodePtr p=pre->left;
//最大值在最右边
while(p->right) {
pre=p;
p=p->right;
}
cur->val=p->val;
if(pre->left==p)
pre->left=NULL;
else
pre->right=NULL;
delete p;
}
}
/* 非递归前序遍历 用栈实现
对于任一结点P：
1)访问结点P，并将结点P入栈;
2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P;
3)直到P为NULL并且栈为空，则遍历结束。
*/
void PreOrderPrint() const{
if(root==NULL) return;
stack<nodePtr> S;
nodePtr cur=root;
while(cur||!S.empty()) {
while(cur) {
cout<<cur->val<<",";
S.push(cur);
cur=cur->left;
}
if(!S.empty()) {
cur=S.top();S.pop();
cur=cur->right;
}
}
cout<<endl;
}
/* 非递归中序遍历 用栈实现
对于任一结点P，
1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
3)直到P为NULL并且栈为空则遍历结束
*/
void InOrderPrint() const{
if(root==NULL) return;
stack<nodePtr> S;
nodePtr cur=root;
while(cur||!S.empty()) {
while(cur)
{
S.push(cur);
cur=cur->left;
}
if(!S.empty()) { // 访问当前节点并右子树入栈
cur=S.top();S.pop();
cout<<cur->val<<",";
cur=cur->right;
}
}
cout<<endl;
}
/*
非递归 后序遍历 用栈实现
要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。
若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
*/
void PostOrderPrint() const {
if(root==NULL) return;
stack<nodePtr> S;
nodePtr cur,pre=NULL; //当前节点和前一次访问的节点
S.push(root);
while(!S.empty()) {
cur=S.top();
if((cur->left==NULL&&cur->right==NULL)||(pre!=NULL&&(pre==cur->left||pre==cur->right)))
{
cout<<cur->val<<","; //如果当前结点没有孩子结点或者孩子节点都已被访问过
S.pop();
pre=cur;
}
else
{
if(cur->right!=NULL)
S.push(cur->right);
if(cur->left!=NULL)
S.push(cur->left);
}
}
}
private :
nodePtr root; // 根节点
};
int main(int argc, char* argv[])
{
BST bst;
bst.insert(12);bst.insert(2);bst.insert(1);bst.insert(122);bst.insert(6);
//bst.insert(11);bst.insert(3);bst.insert(66);bst.insert(30);
//bst.del(12);
bst.InOrderPrint();
bst.PreOrderPrint();
bst.PostOrderPrint();
return 0;
}