二叉搜索树与树的遍历非递归练习

复习了二叉搜索树的实现，包括插入、查找和删除操作，顺便做了下二叉树的三种遍历操作。全部操作采用非递归方式。
 

#include  

#include  

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 S;  

            nodePtr cur=root;  

             while(cur||!S.empty()) {  

                while(cur) {  

                    cout<val<<",";   

                    S.push(cur);  

                    cur=cur->left;  

                 }  

                 if(!S.empty()) {  

                    cur=S.top();S.pop();  

                    cur=cur->right;  

                 }  

             }  

            cout<

        }  

        /* 非递归中序遍历   用栈实现 

        对于任一结点P， 

      1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理； 

      2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子； 

      3)直到P为NULL并且栈为空则遍历结束 

         */   

        void InOrderPrint() const{  

            if(root==NULL) return;  

            stack 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<val<<",";  

                    cur=cur->right;  

                }             

            }  

            cout<

        }  

        /* 

        非递归  后序遍历  用栈实现 

        要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。 

        若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。 

        */ 

        void PostOrderPrint() const {  

            if(root==NULL) return;  

            stack 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<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;  

}