注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

云水禅心

淡若秋菊何妨瘦, 清到梅花不畏寒.

 
 
 

日志

 
 

C++实现链式二叉树,采用非递归的方式先序,中序,后序遍历二叉树  

2012-12-10 14:25:42|  分类: c++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://blog.csdn.net/yushuai007008/article/details/7101663


[cpp] view plaincopy

    // BinaryTree.cpp : 定义控制台应用程序的入口点。 
    //C++实现链式二叉树,采用非递归的方式先序,中序,后序遍历二叉树 
    #include "stdafx.h" 
    #include<iostream> 
    #include<string> 
    #include <stack> 
     
    using namespace std; 
     
    template<class T> 
    struct BiNode 
    { 
        T data; 
        struct BiNode<T> *rchild,*lchild; 
    }; 
     
    template<class T> 
    class BiTree 
    { 
    public: 
        BiTree(){ 
            cout<<"请输入根节点:"<<endl; 
            Create(root); 
            if (NULL != root) 
            { 
                cout<<"root="<<root->data<<endl; 
            } 
            else 
            { 
                cout << "The BinaryTree is empty." << endl; 
            } 
        } 
        ~BiTree(){Release(root);} 
        void InOrderTraverse(); 
        void PreOrderTraverse(); 
        void PostOrderTraverse(); 
     
    private: 
        BiNode<T> *root; 
        void Create(BiNode<T>* &bt); 
        void Release(BiNode<T> *bt); 
    }; 
     
    //析构函数 
    template <class T> 
    void BiTree<T>::Release(BiNode<T> *bt)  
    { 
         
        if(bt==NULL) 
        { 
            Release(bt->lchild ); 
            Release(bt->rchild ); 
            delete bt; 
        } 
    } 
    //建立二叉树 
    template <class T> 
    void BiTree<T>::Create(BiNode<T>* &bt)  
    { 
        T ch; 
        cin>>ch; 
        if(ch== 0)bt=NULL; 
        else 
        { 
            bt=new BiNode<T>; 
            bt->data =ch; 
            cout<<"调用左孩子"<<endl; 
            Create(bt->lchild ); 
            cout<<"调用右孩子"<<endl; 
            Create(bt->rchild ); 
        } 
    } 
    /************************************************************************
    方法:中序遍历(非递归形式)
    思想:向左走到尽头,入栈。出栈,访问节点,向右一步
    ************************************************************************/ 
    template <class T> 
    void BiTree<T>::InOrderTraverse() 
    { 
        stack<BiNode<T>*> sta; //定义一个存放BiNode型指针的空栈 
        BiNode<T>* p = root; 
        sta.push(p);   //将根指针入栈 
        while(!sta.empty()) 
        { 
            while (NULL != p) 
            {//向左走到尽头,并保留所经过的节点指针,入栈 
                p = p->lchild;  
                if (NULL != p) 
                { 
                    sta.push(p); 
                } 
            } 
     
            if (!sta.empty()) 
            { 
                p = sta.top();   
                cout << p->data << " ";  //访问栈顶元素, 
                sta.pop();     //栈顶元素出栈 
                p = p->rchild;  //向右一步    
                if (NULL != p) 
                { 
                    sta.push(p); 
                } 
            }        
        } 
    } 
    /************************************************************************
    方法:先序遍历(非递归形式)
    思想:向左走到尽头,入栈,访问节点。出栈,向右一步
    ************************************************************************/ 
    template<class T> 
    void BiTree<T>::PreOrderTraverse() 
    { 
        stack<BiNode<T>*> sta; 
        BiNode<T>* p = root; 
        sta.push(p);   //将根指针入栈 
        while(!sta.empty()) 
        { 
            while (NULL != p) 
            {//向左走到尽头,并保留所经过的节点指针,入栈 
                cout << p->data << " "; 
                p = p->lchild;  
                if (NULL != p) 
                { 
                    sta.push(p); 
                }    
            } 
     
            if (!sta.empty()) 
            { 
                p = sta.top();   
                sta.pop();     //栈顶元素出栈 
                p = p->rchild;  //向右一步    
                if (NULL != p) 
                { 
                    sta.push(p); 
                } 
            }        
        } 
    } 
     
    /************************************************************************
     后序遍历(非递归形式)                                               
     思想:从根节点开始,向左走到尽头,并入栈,同时设置标志位为1.
     出栈时如果这个节点有右子树,则判断是第几次访问,如果是第1次访问,
     则不出栈,将标志位改为2;如果是第二次访问,则出栈。
                                                   
    ************************************************************************/ 
    template<class T> 
    void BiTree<T>::PostOrderTraverse() 
    { 
        stack<BiNode<T>*> sta; //存放节点指针的栈 
        stack<int> flagsta;  //存放标志位的栈,每出(入)一个节点指针,同步出(入)一个标志位 
        unsigned flag;  //设置标志位,1-第一次访问,2-第二次访问 
        BiNode<T>* p = root; 
        sta.push(p);   //将根指针入栈 
        flagsta.push(1); 
        while(!sta.empty()) 
        { 
            while (NULL != p && NULL != p->lchild) 
            {//向左走到尽头,并保留所经过的节点指针,入栈 
                p = p->lchild;  
                sta.push(p); 
                flagsta.push(1); 
            } 
     
            if (!sta.empty()) 
            { 
                flag = flagsta.top(); 
                flagsta.pop(); 
                p = sta.top(); 
     
                if ((NULL != p->rchild) && flag == 1 ) 
                {//如果右子树不空,且是第一次访问 
                    flagsta.push(2);      //第一次访问时元素不出栈,但将标志位设置为2    
                    p = p->rchild;    //向右一步 
                    sta.push(p); 
                    flagsta.push(1); 
                } 
                else 
                { 
                    sta.pop(); //元素出栈 
                    cout << p->data << " ";  //访问栈顶元素 
                    p = NULL; //将指针置为空 
                }        
            }        
        } 
    } 

[cpp] view plaincopy

    //测试程序 
    void main() 
    {  
        BiTree<int> a; 
        cout << "The InOrderTraverse is: " ; 
        a.InOrderTraverse(); 
        cout << endl; 
     
        cout << "The PreOrderTraverse is: " ; 
        a.PreOrderTraverse(); 
        cout << endl; 
     
        cout << "The PostOrderTraverse is: " ; 
        a.PostOrderTraverse(); 
        cout << endl; 
    } 


当在键盘上一次输入3,2,5,0,0,4,0,0,6,0,0,(这里逗号代表实际输入时的回车键),即构造了二叉树

          3

     2      6

5     4

输出:

root=3
The InOrderTraverse is: 5 2 4 3 6
The PreOrderTraverse is: 3 2 5 4 6
The PostOrderTraverse is: 5 4 2 6 3

达到预期效果。
  评论这张
 
阅读(1344)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018