0

preorder、inorder、postorder のツリー トラバーサルに関連する再帰関数を理解するのに苦労しています。私は再帰についてある程度の知識を持っています (しかし、確かに私の得意分野ではありません)。全員が最初にルートの左の子と呼び出しを行い、次に右の子と 2 回呼び出しを行うようです。しかし、これはどのように正確に可能ですか？左の子で preOrder 関数を呼び出すと、制御フローが先頭に戻り、次の呼び出しが実行されないのではないでしょうか?

void preOrder (Node* root) 
{
    if (root == NULL) return;
    cout<<root->val<<", ";
    preOrder(root->left);
    preOrder(root->right);
}
4

3 に答える 3

0

Preorder : ノードを処理し、左の子に移動、右の子に移動

void preorder(Node *root)
{
    if (root == NULL) //<- Check if the currently passed node is empty
        return; //<- if it is, return from the function back down the stack

    cout << root->val << ", "; //<- if it wasn't empty, print its value

    if (root->left != NULL) //<- check if the node to the left is empty
        preorder(root->left); //<- if not recurse to the left child

    if (root->right != NULL) //<- check if the node to the right is empty
        preorder(root->right); //<- if not recurse to the right child
}

Inorder : 左に移動、ノードを処理、右に移動

void inorder(Node *root)
{
    if (root == NULL)
        return;

    if (root->left != NULL) //<- check if the node to the left is empty
            inorder(root->left); //<- if not recurse to the left child

    cout << root->val << ", ";

    if (root->right != NULL) //<- check if the node to the right is empty
            inorder(root->right); //<- if not recurse to the right child
}

Postorder : 左のノードに移動、右のノードに移動、ノードを処理

void postorder(Node *root)
{
    if (root == NULL)
        return;

    if (root->left != NULL) //<- check if the node to the left is empty
            postorder(root->left); //<- if not recurse to the left child

    if (root->right != NULL) //<- check if the node to the right is empty
            postorder(root->right); //<- if not recurse to the right child

    cout << root->val << ", "
}
于 2015-11-20T17:46:06.720 に答える