• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            l

            成都手游碼農一枚
            隨筆 - 32, 文章 - 0, 評論 - 117, 引用 - 0
            數據加載中……

            [C++]二叉樹的鏈式描述。創建,遍歷,摧毀。

            前段時間寫的,不好的地方請支持,謝謝。

            /*********************************************************
            FileName:BinaryTree.cpp
            Author    :shly
            Date    :2009.9.1
            E-mail    :xlq1989@vip.qq.com
            *二叉樹的鏈式描述。創建,遍歷,摧毀。
            ********************************************************
            */

            #include 
            <iostream>
            #include 
            <deque>
            #include 
            <cassert>
            #include 
            <cstring>
            using namespace std;

            template
            <typename _Ty>
            struct BinNode
            {
                BinNode():pLeft(NULL),pRight(NULL)
                
            {
                
            //    cout<<nNode<<endl;++nNode;
                }

                BinNode
            <_Ty> *pLeft, *pRight;
                _Ty    tData;

                
            //test---
                
            //~BinNode(){--nNode;cout<<nNode<<endl;}
                
            //    static int nNode;
            }
            ;
            //template<typename _Ty>
            //int BinNode<_Ty>::nNode=0;

            template
            <typename _Ty>
            class BinaryTree
            {
                BinNode
            <_Ty>* pRoot;
            public:
                BinaryTree():pRoot(NULL)
            {}
                
            ~BinaryTree(){}
            public:
            //    void CreateBinTree(_Ty& tData);
                void CreateBinTree(_Ty* tpStart,int nSize);
                
            void DestroyBinTree();
            //    void AddBinTree(BinaryTree* pLeft,BinaryTree* pRight);
                void PreOrder();
                
            void InOrder();
                
            void PostOrder();
                
            void LevelOrder();
                
            void Vista(const _Ty& tData);
            private
                
            void _destroy(BinNode<_Ty>* pNode);
                
            void _pre(BinNode<_Ty>* pNode);
                
            void _in(BinNode<_Ty>* pNode);
                
            void _post(BinNode<_Ty>* pNode);
            }
            ;

            /*********************************************************
            *Function    :CreateBinTree
            *parameter    :_Ty tData
            *return        :void
            *為pRoot創建一個結點。
            ********************************************************
            */

            //template<typename _Ty>void BinaryTree<_Ty>::CreateBinTree(_Ty& tData){
            //    assert(NULL==pRoot);
            //    pRoot=new BinNode<_Ty>;
            //    assert(NULL!=pRoot);
            //
            //    pRoot->tData=tData;
            //    pRoot->pLeft=pRoot->pRight=NULL;
            //}
            /*********************************************************
            *Function    :CreateBinTree
            *parameter    :_Ty* tpStart,int nSize
            *return        :void
            *根據一組數據順序生成一顆二叉樹。
            ********************************************************
            */

            template
            <typename _Ty>
            void BinaryTree<_Ty>::CreateBinTree(_Ty* tpStart,int nSize)
            {
                assert(tpStart
            &&!pRoot&&nSize>0);

                deque
            <BinNode<_Ty>**> dq;
                dq.push_back(
            &pRoot);
                
                
            for(int i=0;i<nSize;)
                
            {
                    BinNode
            <_Ty>** pb=dq.front();
                    dq.pop_front();
                    assert(NULL
            ==(*pb));
                    (
            *pb)=new BinNode<_Ty>;
                    (
            *pb)->tData=tpStart[i++];
                    dq.push_back(
            &(*pb)->pLeft);
                    dq.push_back(
            &(*pb)->pRight);
                }

            }

            /*********************************************************
            *Function    :AddBinTree
            *parameter    :BinaryTree* pLeft,* pRight
            *return        :void
            *將兩個子樹組合成一個。
            ********************************************************
            */

            //template<typename _Ty>void BinaryTree<_Ty>::AddBinTree(BinaryTree* pLeft,BinaryTree* pRight){
            //    assert(NULL!=pLeft);
            //    assert(NULL!=pRight);
            //    assert(NULL!=pRoot);
            //    assert(NULL==pRoot->pLeft);
            //    assert(NULL==pRoot->pRight);
            //
            //    pRoot->pLeft=pLeft;
            //    pRoot->pRight=pRight;
            //
            //    pLeft=pRight=0;
            //}
            /*********************************************************
            *Function    :DestroyBintree
            *parameter    :void
            *return        :void
            *摧毀二叉樹。
            ********************************************************
            */

            template
            <typename _Ty>void BinaryTree<_Ty>::_destroy(BinNode<_Ty>* pNode){
            /*    if(NULL==pNode)return;
                if(NULL==pNode->pLeft
                 &&NULL==pNode->pRight){
                    delete pNode;
                    static int i=0;
                    ++i;
                    cout<<i<<"__";
                    pNode=NULL;
                //    cout<<"Destroy BinaryTree!"<<endl;
                }
                else{
                    _destroy(pNode->pLeft);
                    _destroy(pNode->pRight);
                }
            */

                
            if(!pNode)return;
                _destroy(pNode
            ->pLeft);
                _destroy(pNode
            ->pRight);
                delete pNode;
                pNode
            =NULL;
            }

            template
            <typename _Ty>
            inline 
            void BinaryTree<_Ty>::DestroyBinTree()
            {
                _destroy(pRoot);
            }


            /*********************************************************
            *Function    :PreOrder
            *parameter    :void
            *return        :void
            *先序遍歷。
            ********************************************************
            */

            template
            <typename _Ty>
            void BinaryTree<_Ty>::_pre(BinNode<_Ty>* pNode)
            {
                
            if(!pNode)return;
                Vista(pNode
            ->tData);
                _pre(pNode
            ->pLeft);
                _pre(pNode
            ->pRight);
            }

            template
            <typename _Ty>
            inline 
            void BinaryTree<_Ty>::PreOrder()
            {
                _pre(pRoot);
            }

            /*********************************************************
            *Function    :InOrder
            *parameter    :void
            *return        :void
            *中序遍歷。
            ********************************************************
            */

            template
            <typename _Ty>
            void BinaryTree<_Ty>::_in(BinNode<_Ty>* pNode)
            {
                
            if(!pNode)return;
                _in(pNode
            ->pLeft);
                Vista(pNode
            ->tData);
                _in(pNode
            ->pRight);
            }

            template
            <typename _Ty>
            inline 
            void BinaryTree<_Ty>::InOrder()
            {
                _in(pRoot);
            }

            /*********************************************************
            *Function    :PostOrder
            *parameter    :void
            *return        :void
            *后序遍歷。
            ********************************************************
            */

            template
            <typename _Ty>
            void BinaryTree<_Ty>::_post(BinNode<_Ty>* pNode)
            {
                
            if(!pNode)return;
                _post(pNode
            ->pLeft);
                _post(pNode
            ->pRight);
                Vista(pNode
            ->tData);
            }

            template
            <typename _Ty>
            inline 
            void BinaryTree<_Ty>::PostOrder()
            {
                _post(pRoot);
            }

            /*********************************************************
            *Function    :LevelOrder
            *parameter    :void
            *return        :void
            *逐層遍歷。
            ********************************************************
            */

            template
            <typename _Ty>
            void BinaryTree<_Ty>::LevelOrder()
            {
                
            if(!pRoot)return;
                deque
            <BinNode<_Ty>*> dq;
                dq.push_back(pRoot);
                
            while(!dq.empty())
                
            {
                    BinNode
            <_Ty>* temp=dq.front();
                    dq.pop_front();
                    Vista(temp
            ->tData);
                    
            if(NULL!=temp->pLeft)
                        dq.push_back(temp
            ->pLeft);
                    
            if(NULL!=temp->pRight)
                        dq.push_back(temp
            ->pRight);
                }

            }

            /*********************************************************
            *Function    :Vista
            *parameter    :const _Ty& tData
            *return        :void
            *訪問操作。
            ********************************************************
            */

            template
            <typename _Ty>
            void BinaryTree<_Ty>::Vista(const _Ty& tData)
            {
                
            if(' '!=tData)
                    cout
            <<tData<<" ";
            }


            int main()
            {
                
            //char* arr="+*/abcd";
                
            //char* arr="++d+c  ab";
                char* arr="/+*-++* axy bca";
                BinaryTree
            <char> bt;
                bt.CreateBinTree(arr,strlen(arr));
            //創建二叉樹
                bt.PreOrder();//先序遍歷
                cout<<endl;
                bt.InOrder();
            //中序遍歷
                cout<<endl;
                bt.PostOrder();
            //后序遍歷
                cout<<endl;
                bt.LevelOrder();
            //逐層遍歷
                cout<<endl;
                bt.DestroyBinTree();
            //摧毀二叉樹
                return 0;
            }

            posted on 2009-09-01 00:58 l1989 閱讀(958) 評論(2)  編輯 收藏 引用 所屬分類: 數據結構

            評論

            # re: [C++]二叉樹的鏈式描述。創建,遍歷,摧毀。  回復  更多評論   

            弱弱的說...刪除那段似乎刪了樹葉...留了個樹干 - -
            2009-09-01 10:10 | Ocean.Tu

            # re: [C++]二叉樹的鏈式描述。創建,遍歷,摧毀。  回復  更多評論   

            謝謝LS提醒,已經改了。
            這些東西真麻煩哦。。
            2009-09-01 12:37 | shly
            久久精品免费一区二区三区| 国产69精品久久久久9999APGF| 亚洲国产天堂久久综合| 久久精品三级视频| 热99RE久久精品这里都是精品免费| 狠狠人妻久久久久久综合| 国产精品成人久久久| 久久久国产精品亚洲一区| 精品人妻伦一二三区久久| 亚洲精品国产美女久久久| 伊人久久精品线影院| 久久久国产精华液| 久久久WWW免费人成精品| 欧美大香线蕉线伊人久久| 国产亚洲色婷婷久久99精品91| 久久天天躁狠狠躁夜夜2020一| 久久久久国产一级毛片高清版| 亚洲国产成人久久综合区| 久久福利青草精品资源站| 久久免费看黄a级毛片| 久久99精品久久久久久野外| 成人妇女免费播放久久久| 久久www免费人成看片| 久久九九久精品国产免费直播| 国产午夜免费高清久久影院| 久久99热这里只有精品国产| 久久综合久久鬼色| 久久久久国产成人精品亚洲午夜| 高清免费久久午夜精品| 久久香蕉超碰97国产精品| 狠狠综合久久综合88亚洲| 怡红院日本一道日本久久 | 久久久久久久91精品免费观看 | 久久91精品久久91综合| 久久精品无码一区二区WWW| 国产91色综合久久免费分享| 国产成人精品久久| 久久久久久久97| 亚洲熟妇无码另类久久久| 99久久99久久精品国产片果冻 | 热久久视久久精品18|