검지offer 면접문제-두 갈래 나무의 앞뒤 순서 두루

제목은 한 나무의 뿌리 노드에 전달되고 각각 비귀속으로 나무의 앞차례, 중차례, 뒷차례를 반복한다.노드 정의는 다음과 같습니다.

struct BinaryTreeNode
{   
    BinaryTreeNode(char data)
    :_pLeftChild(NULL)
    , _pRightChild(NULL)
    , _data(data)
    {}
    BinaryTreeNode *_pLeftChild;
    BinaryTreeNode *_pRightChild;
    char _data;
};

트리 코드 만들기

void _CreateBinaryTree(BinaryTreeNode *&pRoot, char *pStr, size_t size, size_t& index)
{// index 
    if (index < size && '#' != pStr[index])
    {
        pRoot = new  BinaryTreeNode(pStr[index]);
        _CreateBinaryTree(pRoot->_pLeftChild, pStr, size, ++index);
        _CreateBinaryTree(pRoot->_pRightChild, pStr, size, ++index);
    }
}

전면 순차

사고방식 실현

창고를 사용하면 우선 루트를 창고에 넣고 빈 순환으로 창고 꼭대기 요소에 접근하지 않으며, 창고에서 나온 오른쪽 아이는 빈 오른쪽 아이가 아니라 왼쪽 아이는 빈 왼쪽 아이가 아니다.

구현 코드

void PreOrder(BinaryTreeNode *pRoot)
{
    if (NULL == pRoot)
        return;
    stack s;
    s.push(pRoot);
    while (!s.empty())
    {
        BinaryTreeNode *top = s.top();
        cout << top->_data;
        s.pop();
        if (top->_pRightChild)
            s.push(top->_pRightChild);
        if (top->_pLeftChild)
            s.push(top->_pLeftChild);   
    }
}

테스트 용례:

void testpre()
{
    BinaryTreeNode *pRoot;
    char *str = "abcd"; //  
    size_t size = 0;
    _CreateBinaryTree(pRoot, str, strlen(str), size);
    PreOrder(pRoot);
    cout << endl;
    str = "a#b#c#d";// 
    size = 0;
    _CreateBinaryTree(pRoot, str, strlen(str), size);
    PreOrder(pRoot);
    cout << endl;
    str = "ab#df##g##ce#h";// 
    size = 0;
    _CreateBinaryTree(pRoot, str, strlen(str), size);
    PreOrder(pRoot);
    PreOrder(NULL);
}

중순 스트리밍

사고방식 실현

하나의 결점을 정의하고 뿌리에서 가장 왼쪽의 결점 창고가 비어 있지 않고 결점이 비어 있지 않으며, 결점이 비어 있지 않은 순환을 위해 가장 왼쪽 노드를 찾고, 길을 따라 결점을 창고에 넣고 창고 꼭대기 요소를 방문한다. 창고에서 나온 오른쪽 아이가 있으면 오른쪽 아이를 정의된 결점에 부여한다.

구현 코드

void Inorder(BinaryTreeNode *pRoot)
{
    if (NULL == pRoot)
        return;
    stack s;
    BinaryTreeNode *pCur = pRoot;
    while (!s.empty() || pCur)
    {
        while (pCur)
        {
            s.push(pCur);
            pCur = pCur->_pLeftChild;// 
        }
        BinaryTreeNode *top = s.top();
        cout << top->_data;
        s.pop();
        pCur = top->_pRightChild;
    }
}

테스트 용례

void testin()
{
    BinaryTreeNode *pRoot;
    char *str = "abcd"; //  //dcba
    size_t size = 0;
    _CreateBinaryTree(pRoot, str, strlen(str), size);
    Inorder(pRoot);
    cout << endl;
    str = "a#b#c#d";// //abcd
    size = 0;
    _CreateBinaryTree(pRoot, str, strlen(str), size);
    Inorder(pRoot);
    cout << endl;
    str = "ab#df##g##ce#h";// //bfdgaehc
    size = 0;
    _CreateBinaryTree(pRoot, str, strlen(str), size);
    Inorder(pRoot);
    Inorder(NULL);
}

후순 반복

사고방식 실현

결점 pCur를 정의하여 가장 왼쪽에 있는 결점을 찾고 pPre 저장 전 접근 노드를 정의합니다.창고가 비어 있지 않거나 pCur가 빈 순환을 위해 가장 왼쪽의 결점을 찾지 않으며, 길가의 결점을 창고에 넣습니다. 만약 창고 위에 오른쪽 아이가 없거나 오른쪽 아이가 방금 방문한 적이 있다면, 창고 위에 있는 요소에 방문하고, 오른쪽 아이가 오른쪽 아이에게 값을 부여하여 pCur 순환을 계속합니다.

void postorder(BinaryTreeNode *pRoot)
{
    if (NULL == pRoot)
        return;
    stack s;
    BinaryTreeNode *pCur = pRoot;
    BinaryTreeNode *pPre = NULL;
    while (!s.empty() || pCur)
    {
        while (pCur)
        {
            s.push(pCur);
            pCur = pCur->_pLeftChild;
        }
        BinaryTreeNode *top = s.top();
        if (NULL == top->_pRightChild || pPre == top->_pRightChild)
        {
            cout << top->_data << " ";
            pPre = top;
            s.pop();
        }
        else
            pCur = top->_pRightChild;
    }
}

테스트 용례

void testpost()
{
    BinaryTreeNode *pRoot;
    char *str = "abcd"; //  //dcba
    size_t size = 0;
    _CreateBinaryTree(pRoot, str, strlen(str), size);
    postorder(pRoot);
    cout << endl;
    str = "a#b#c#d";// //dcba
    size = 0;
    _CreateBinaryTree(pRoot, str, strlen(str), size);
    postorder(pRoot);
    cout << endl;
    str = "ab#df##g##ce#h";// //
    size = 0;
    _CreateBinaryTree(pRoot, str, strlen(str), size);
    postorder(pRoot);
    postorder(NULL);
}