二叉樹的原理和3種周遊方式（C++實作）

二叉樹

• 每個節點最多有兩顆子樹，即度 <= 2， 有序樹

性質

• 二叉樹的第i層上最多有2^i個節點，i從0開始；
• 深度為k的二叉樹上至多有2^(k+1) - 1個節點，k從0開始；
• 目前節點編号為i，則其子節點（如果有）為2i+1和2i+2；

完全二叉樹

葉子節點隻在最大兩層出現；

對于任一節點，其右側分支最大層次為l，則左分支為l或者l+1

滿二叉樹

深度為k且有2^(k+1) - 1個節點的二叉樹

樹的節點

struct BiTreeNode {
    char data;
    BiTreeNode *lChild;
    BiTreeNode *rChild;
    BiTreeNode *Parent;
};
           

前序周遊

遞歸解決

void BiTree::PreTraverse(BiTreeNode *root) const {

    if (root != NULL)
    {
        cout << root->data;
        PreTraverse(root->lChild);
        PreTraverse(root->rChild);
    }
}
           

棧解決

//先輸出目前節點的值，并将該節點放入棧中，繼續通路左節點直到終端，
//輸出節點值，退棧,通路右節點
void BiTree::PreOrderTraverse(BiTreeNode *root) const {
    stack<BiTreeNode *> Tree;
    while (!Tree.empty() || root != NULL)
    {
        while (root != NULL)
        {
            cout << root->data;
            Tree.push(root);
            root = root->lChild;
        }
        root = Tree.top();
        Tree.pop();
        root = root->rChild;
    }
}
           

中序周遊

遞歸解決

void BiTree::InTraverse(BiTreeNode *root) const {
    if (root != NULL)
    {
        InTraverse(root->lChild);
        cout << root->data;
        InTraverse(root->rChild);
    }
}
           

棧解決

//通路左節點直到NULL輸出棧頂節點值，退棧通路右節點
void BiTree::InOrderTraverse(BiTreeNode *root) const {
    stack<BiTreeNode *> Tree;
    while (!Tree.empty() || root != NULL)
    {
        while (root != NULL)
        {
            Tree.push(root);
            root = root->lChild;
        }
        root = Tree.top();
        cout << root->data;
        Tree.pop();
        root = root->rChild;
    }

}
           

後序周遊

遞歸解決

void BiTree::PostTraverse(BiTreeNode *root) const {
    if (root != NULL)
    {
        PostTraverse(root->lChild);
        PostTraverse(root->rChild);
        cout << root->data;
    }
}
           

棧解決

//對父節點出現在棧頂的次數進行計數：第一次出現的時候不出棧，
//第二次再出現，表明右孩子子樹已經周遊完畢，這個時候再出棧并完成周遊。
void BiTree::PostOrderTraverse(BiTreeNode *root) const {
    stack<BiTreeNode *> Tree;
    stack<int> Times; //計數
    while (!Tree.empty() || root != NULL)
    {
        while (root != NULL)
        {
            Tree.push(root);
            Times.push(); //首次通路該節點
            root = root->lChild;
        }
        if (Times.top() == ) //已經通路了2次
        {
            cout << Tree.top()->data;
            Times.pop(); //删除棧頂元素
            Tree.pop();
        }
        else
        {
            root = Tree.top();
            Times.top() = ; //第二次通路該節點
            root = root->rChild;
        }
    }
}