二叉木の原理と3種類の遍歴方式(C++実現)

二叉木

ノードごとに最大2つのサブツリー、すなわち度<=2、秩序ツリー

がある.
せいしつ

二叉木のi層目には最大2^i個のノードがあり、iは0から始まる.

深さkの二叉木には2^(k+1)-1ノードまであり、kは0から始まる.

現在のノード番号がiである場合、そのサブノード(ある場合)は2 i+1および2 i+2であり、

完全二叉木
リーフノードは最大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 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 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 Tree;
    stack<int> Times; //  
    while (!Tree.empty() || root != NULL)
    {
        while (root != NULL)
        {
            Tree.push(root);
            Times.push(0); //       
            root = root->lChild;
        }
        if (Times.top() == 1) //     2 
        {
            cout << Tree.top()->data;
            Times.pop(); //      
            Tree.pop();
        }
        else
        {
            root = Tree.top();
            Times.top() = 1; //        
            root = root->rChild;
        }
    }
}