면접문제 두 갈래 나무의 앞 순서, 중간 순서, 뒤 순서(귀속 실현)

이전 순차 반복 반복 반복 해법:
(1) 두 갈래 나무가 비어 있으면 빈 조작
(2) 두 갈래 나무가 비어 있지 않으면 뿌리 노드를 방문하고 왼쪽 트리를 앞뒤로 옮긴다. 오른쪽 트리를 앞뒤로 옮긴다.
두 갈래 나무가 비어 있으면 비어 있습니다.(2) 두 갈래 나무가 비어 있지 않으면 왼쪽 트리에 중순으로, 뿌리 노드에 접근하고, 오른쪽 트리에 중순으로
뒷차례 역귀환법 (1) 두 갈래 나무가 비어 있다면, 빈 조작 (2) 두 갈래 나무가 비어 있지 않으면, 뒷차례 왼쪽 트리, 뒷차례 오른쪽 트리, 뿌리 노드에 접근
참조 구현 코드:
4

[/u1/yyang/study/algorithm/binarytree](203)yyang@dcmvrh12#cat binarytree.h
#include <stdio.h>
#include <stdlib.h>

typedef struct  BinaryTreeNode
{
        int value;
        BinaryTreeNode* left;
        BinaryTreeNode* right;

}BTN;

BTN* CreateBTNode(int value)
{
        BTN* btnode = new BinaryTreeNode();
        if(btnode)
        {
                btnode->value = value;
                btnode->left = NULL;
                btnode->right = NULL;
        }
        return btnode;
}

void CreateBTree(BTN* root, BTN* left, BTN* right)
{
        if(root)
        {
                root->left = left;
                root->right =right;
        }
}

void DeleteNode(BTN* root)
{
        if(root == NULL)
                return ;
        if(root->left) DeleteNode(root->left);
        if(root->right) DeleteNode(root->right);
        delete root;
        root = NULL;
}

cpp 파일
4

[/u1/yyang/study/algorithm/binarytree] (208)yyang@dcmvrh12#cat rectranverse.cpp
#include "binarytree.h"

void preOrder(BTN* root)
{
        if(root == NULL)
                return;
        printf(" %d ",root->value);
        preOrder(root->left);
        preOrder(root->right);
}

void  inOrder(BTN* root)
{
        if(root == NULL)
                return;
        inOrder(root->left);
        printf(" %d ",root->value);
        inOrder(root->right);
}

void postOrder(BTN* root)
{
        if(root == NULL)
                return;
        postOrder(root->left);
        postOrder(root->right);
        printf(" %d ",root->value);
}

int main()
{

        //            1
        //         /      \
        //        2        3
        //       /\         \
        //      4  5         6
       //         /
        //        7
       //create BTN*node
        BTN* btnode1 = CreateBTNode(1);
        BTN* btnode2 = CreateBTNode(2);
        BTN* btnode3 = CreateBTNode(3);
        BTN* btnode4 = CreateBTNode(4);
        BTN* btnode5 = CreateBTNode(5);
        BTN* btnode6 = CreateBTNode(6);
        BTN* btnode7 = CreateBTNode(7);

        CreateBTree(btnode1,btnode2,btnode3);
        CreateBTree(btnode2,btnode4,btnode5);
        CreateBTree(btnode3,NULL,btnode6);
        CreateBTree(btnode5,btnode7,NULL);

        printf("preOrder is :
");
        preOrder(btnode1);

        printf("
inOrder is :
");
        inOrder(btnode1);

        printf("
postOrder is :
");
        postOrder(btnode1);
        printf("
");
        //free the node
        DeleteNode(btnode1);
}

컴파일 및 실행 결과:
4

[/u1/yyang/study/algorithm/binarytree](209)yyang@dcmvrh12#g++ rectranverse.cpp -o rectranverse
[/u1/yyang/study/algorithm/binarytree](210)yyang@dcmvrh12#./rectranverse
preOrder is :
 1  2  4  5  7  3  6
inOrder is :
 4  2  7  5  1  3  6
postOrder is :
 4  7  5  2  6  3  1

결과가 정확하다.