溫故而知新垂睬。本文將回顧二叉搜索樹的基本知識，并用C++將它的三種depth-first search: 前序遍歷辰斋、中序遍歷和后序遍歷退子，以及一種breath first search: 層序遍歷算法分別實現(xiàn)出來。

1. BST的結(jié)構(gòu)

首先切端，我們先定義樹的結(jié)構(gòu)：

struct node
{
    int data;
    node *leftchild;
    node *rightchild;
    node(int val)
    {
        data = val;
        leftchild = NULL;
        rightchild = NULL;
    }
};

接下來彻坛，我們實現(xiàn)基本的插入節(jié)點操作。根據(jù)BST的特點，要求保持節(jié)點之間的有序性昌屉，即左節(jié)點<根節(jié)點<右節(jié)點钙蒙。首先找到新節(jié)點的插入位置，再將其插入即可怠益。

void insert(node* root,int val)
{
    node* tmp = new node(val);//創(chuàng)建新節(jié)點
    if(root == NULL)
    {
        root = tmp;
        return;
    }
    node* pre = root;
    while(true)
    {
    
        if(pre->data >= val)
        {
            if(pre->leftchild == NULL)
            {
                pre->leftchild = tmp;
                return;
            }
            pre = pre->leftchild;
        }
        else
        {
            if(pre->rightchild == NULL)
            {
                pre->rightchild = tmp;
                return;
            }
            pre = pre->rightchild;
        }
    }
};

2. 前序仪搔、中序、后序遍歷的遞歸實現(xiàn)

首先明確一下三種遍歷的基本概念：

前序遍歷：根節(jié)點->左子樹->右子樹
中序遍歷：左子樹->根節(jié)點->右子樹
后序遍歷：左子樹->右子樹->根節(jié)點

其中中序遍歷比較特別蜻牢，因為按照中序遍歷BST能夠得到有序的數(shù)列烤咧，這在很多題目中都有所應(yīng)用。

只要理解了三種遍歷的基本概念抢呆，它們的遞歸實現(xiàn)都比較容易寫出煮嫌。

void preordertree(node* root)
{
    if(root == NULL) return;
    if(root!=NULL)
    {
    std::cout << root->data << " ";
    preordertree(root->leftchild);
    preordertree(root->rightchild);
    }
};
void postordertree(node* root)
{
    if(root == NULL) return;
    if(root)
    {
        postordertree(root->leftchild);
        postordertree(root->rightchild);
        std::cout << root->data << " ";
    }
}
void inordertree(node* root)
{
    if(root)
    {
        inordertree(root->leftchild);
        std::cout << root->data << " ";
        inordertree(root->rightchild);
    }
}

3. 前序、中序抱虐、后序遍歷的非遞歸實現(xiàn)

3.1 前序遍歷的非遞歸實現(xiàn)

前序遍歷的非遞歸實現(xiàn)主要需要借助stack昌阿。對于stack中任意一個節(jié)點，先訪問其本身并將其pop出來恳邀，再將其右節(jié)點和左節(jié)點分別壓入棧中即可懦冰。

void iterpreordertree(node* root)
{
    if(root == NULL) return;
    
    std::stack<node *> nstack;
    nstack.push(root);
    
    while(!nstack.empty())
    {
        node* tmp = nstack.top();
        std::cout << tmp->data << " ";
        nstack.pop();
        
        if(tmp->rightchild)
            nstack.push(tmp->rightchild);
        if (tmp->leftchild)
            nstack.push(tmp->leftchild);
    }
    std::cout << std::endl;
}

3.2 中序遍歷的非遞歸實現(xiàn)

中序遍歷的非遞歸實現(xiàn)的主要難點在于：因為首先要尋找到左節(jié)點，訪問完畢后需要回到根節(jié)點谣沸，并轉(zhuǎn)換方向?qū)ふ矣覀?cè)子樹刷钢。這里，我們用一個棧stack和一個節(jié)點cur來追蹤乳附。首先將cur指定為根節(jié)點内地。

不斷搜尋cur的左子樹，并將中間路過的節(jié)點壓入棧中赋除。
當(dāng)左子樹搜尋完畢之后阱缓，將cur重新賦值為nstack.top()，訪問過后將其彈出举农。
轉(zhuǎn)換cur到其右子樹上荆针，并重復(fù)步驟1。

void iterinordertree(node* root)
{
    if(root == NULL) return;
    
    std::stack<node *> nstack;
    node* cur = root;
    
    while(cur || !nstack.empty())
    {
        //if cur is not NULL
        if(cur)
        {
            nstack.push(cur);
            cur = cur->leftchild;
        }
        else{
            cur = nstack.top();
            std::cout << cur->data << " ";
            nstack.pop();
            
            cur = cur->rightchild;
        }
    }
    
    std::cout << std::endl;
}

3.3 后序遍歷的非遞歸實現(xiàn)

后序遍歷的非遞歸實現(xiàn)是三者中最難的颁糟，需要借助兩個stack來實現(xiàn)祭犯。

void iterpostordertree(node* root)
{
    if(root == NULL) return;
    
    std::stack<node *> first,second;
    first.push(root);
    
    while(!first.empty())
    {
        node* tmp = first.top();
        first.pop();
        second.push(tmp);
        
        if(tmp->leftchild)
            first.push(tmp->leftchild);
        if (tmp->rightchild)
            first.push(tmp->rightchild);
    }
    while (!second.empty()) {
        std::cout << second.top()->data << " ";
        second.pop();
    }
    std::cout << std::endl;
}

4. 層序遍歷

層序遍歷利用的是廣度優(yōu)先搜索，利用隊列滚停，每次訪問一層，并將下一層的節(jié)點入隊粥惧。

void breathfirst(node* root)
{
    if(root == NULL) return;
    
    std::queue<node *> nqueue;
    nqueue.push(root);
    
    while (!nqueue.empty()) {
        int n = nqueue.size();
        for(int i = 0; i < n; i++)
        {
            node* cur = nqueue.front();
            std::cout << cur->data << " ";
            nqueue.pop();
            if (cur->leftchild)
                nqueue.push(cur->leftchild);
            if(cur->rightchild)
                nqueue.push(cur->rightchild);
        }
    }
    std::cout << std::endl;
}

以上即是本文的全部內(nèi)容键畴，感謝關(guān)注。

代碼清單： https://github.com/ShulinLiu/DataStructure-Algorithm/blob/master/BasicDataStructure/tree/tree.cpp

[數(shù)據(jù)結(jié)構(gòu)]C++實現(xiàn)二叉樹及其遍歷