對于二叉樹，在此我不做過多講解，如有不懂，請參照一下鏈接點擊打開鏈接

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價值的長期合作伙伴，公司提供的服務(wù)項目有：域名注冊、虛擬空間、營銷軟件、網(wǎng)站建設(shè)、臨湘網(wǎng)站維護(hù)、網(wǎng)站推廣。

 1、在此二叉樹的定義：

struct BinaryTreeNode    
{    
    BinaryTreeNode<T> *_Left;    
    BinaryTreeNode<T> *_Right;    
    T _data;    
public:    
    BinaryTreeNode(const T& x)    
        :_Left(NULL)    
        , _Right(NULL)    
        , _data(x)    
    {}    
};    
    
template<class T>    
class BinaryTree    
{    
    typedef BinaryTreeNode<T> Node;    
public:    
    BinaryTree()    
        :_root(NULL)    
    {}    
}

2、由前序遍歷和中序遍歷重建二叉樹

 思想：
  1、二叉樹前序遍歷中，第一個元素總是根節(jié)點的值，
   2、中序遍歷，左子樹的結(jié)點的值位于根節(jié)點值得左邊，
   3、右子樹的節(jié)點的值位于根節(jié)點值得右邊。
   4、如果前序遍歷為空或中序遍歷為空或結(jié)點個數(shù)小于等于0，返回NULL；
   5、創(chuàng)建根節(jié)點，前序遍歷的第一個數(shù)據(jù)就是根節(jié)點的數(shù)據(jù)，在中序遍歷中找到根節(jié)點位置
  6、分別得知左子樹和右子樹的前序和中序遍 歷序列，重建左右子樹。

遞歸形式實現(xiàn)：

Node * RebuildBinaryTree(T* PrevOrder, T* InOrder, int num)    
    {    
        if (PrevOrder == NULL || InOrder == NULL || num <= 0)    
        {    
            return NULL;    
        }    
        Node* root = new Node(PrevOrder[0]);    
        // 前序遍歷的第一個數(shù)據(jù)就是根節(jié)點數(shù)據(jù)    
            
        //中序遍歷，根節(jié)點左為左子樹，右為右子樹    
        int rootposition = -1;    
        for (int i = 0; i < num; i++)    
        {    
            if (InOrder[i] == root->_data)    
            {    
                rootposition = i;    
            }    
        }    
        if (rootposition == -1)    
            return NULL;    
        //重建左子樹(根節(jié)點)遞歸    
        int LeftNum = rootposition;    
        int *PrevOrderLeft = PrevOrder + 1; //前序第二個即為根節(jié)點的左子樹    
        int *InOrderLeft = InOrder; //中序第一個 即為其左子樹。    
        root->_Left = RebuildBinaryTree(PrevOrderLeft, InOrderLeft, LeftNum);    
        //重建右子樹(根節(jié)點)遞歸    
        int RightNum = num - LeftNum - 1;    
        int *PrevOrderRight = PrevOrder + 1 + LeftNum;    
        int *InOrderRight = InOrder + LeftNum + 1;    
        root->_Right = RebuildBinaryTree(PrevOrderRight, InOrderRight, RightNum);    
        return root;    
    }

分享題目：前序遍歷和中序遍歷重建二叉樹
標(biāo)題URL：http://jinyejixie.com/article10/ieppdo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供面包屑導(dǎo)航、虛擬主機、手機網(wǎng)站建設(shè)、定制開發(fā)、、建站公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)