검지 Offer 시리즈 - 면접 문제 6: 이 진 트 리 재건

제목: 이 진 트 리 의 앞 순 서 를 입력 하고 중간 순 서 를 옮 겨 다 니 는 결 과 를 입력 하 십시오. 이 이 진 트 리 를 다시 만 드 십시오.입력 한 앞 순서 와 중간 순 서 를 옮 겨 다 니 는 결과 에 중복 되 는 숫자 가 없다 고 가정 합 니 다.예 를 들 어 입력 전 순서 옮 겨 다 니 기 시퀀스 {1, 2, 4, 7, 3, 5, 6, 8} 과 중 순서 옮 겨 다 니 기 시퀀스 {4, 7, 2, 1, 5, 3, 8, 6} 을 입력 하면 이 진 트 리 를 재 구축 하고 머리 결 점 을 출력 합 니 다.
코드 는 다시 쓰 지 않 았 으 며 15 년 가을 데이터 구조의 OJ 문제 로 맨손으로 쓴 대기 열 과 이 진 트 리 류 입 니 다.

#include 

using namespace std;
/***********************************Queue******************************/
template
struct LinkNode
{
    T data;
    LinkNode *next;
    LinkNode(LinkNode *top = NULL)
    {
        next = top;
    }
    LinkNode(T elem,LinkNode *top = NULL)
    {
        data = elem;
        next = top;
    }
};

template
class Queue
{
private:
    LinkNode *first,*rear;
public:
    Queue()
    {
        rear = first = new LinkNode;
    }

    ~Queue()
    {
        makeEmpty();
    }

    bool EnQueue(const T& elem)
    {
        LinkNode* newNode = new LinkNode(elem);
        if(!newNode)
            return false;
        if(IsEmpty())
            first->next = rear = newNode;
        rear->next=newNode;
        rear=rear->next;
        return true;
    }

    bool DeQueue(T& elem)
    {
        LinkNode* del;
        if(first==rear)
            return false;
        del=first->next;
        elem=del->data;
        first->next=del->next;
        if(first->next==NULL)
            rear=first;
        delete del;
        return true;
    }

    bool IsEmpty()
    {
        return (first == rear)? true:false;
    }

    void makeEmpty()
    {
        LinkNode *p = first->next;
        if(!p)
            return;
        while(first->next)
        {
            first = p->next;
            delete p;
            p = first->next;
        }
    }

};
/*********************************BinaryTree***************************/
template
struct BinTreeNode
{
    T data;
    BinTreeNode *lchild, *rchild;
    BinTreeNode()
    {
        lchild = NULL;
        rchild = NULL;
    }
    BinTreeNode(T x, BinTreeNode* l = NULL, BinTreeNode* r = NULL)
    {
        data = x;
        lchild = l;
        rchild = r;
    }
};

template
class BinaryTree
{
private:
    BinTreeNode* root;
    void destroy(BinTreeNode* root)
    {
        if(root)
        {
            destroy(root->lchild);
            destroy(root->rchild);
            delete root;
        }
    }
public:
    BinaryTree()
    {
        root = NULL;
    }
    BinaryTree(BinTreeNode* p)
    {
        root = p;
    }
    BinaryTree(T *elems, int n)         ///    ，    ，      
    {
        root = new BinTreeNode [n];
        for(int i=0; i& a);
    ~BinaryTree()
    {
    }
    BinTreeNode *visitRoot()
    {
        return root;
    }
    bool isEmpty()
    {
        return (root == NULL)?true:false;
    }
    BinTreeNode *Parent(BinTreeNode* current)
    {
        return (root == NULL || root == current)?NULL:Parent(root,current);
    }
    BinTreeNode *LeftChild(BinTreeNode* current)
    {
        return (current != NULL)?current->lchild:NULL;
    }
    BinTreeNode *RightChild(BinTreeNode* current)
    {
        return (current != NULL)?current->rightChild:NULL;
    }
    void PreOrder(BinTreeNode* p = visitRoot())   ///      
    {
        if(p)
        {
            cout << p->data << " ";
            PreOrder(p->lchild);
            PreOrder(p->rchild);
        }
    }
    void InOrder(BinTreeNode* p = visitRoot())   ///      
    {
        if(p)
        {
            InOrder(p->lchild);
            cout << p->data << " ";
            InOrder(p->rchild);
        }
    }
    void PostOrder(BinTreeNode* p = visitRoot())   ///      
    {
        if(p)
        {
            PostOrder(p->lchild);
            PostOrder(p->rchild);
            cout << p->data << " ";
        }
    }
    void LevelOrder(BinTreeNode* p) ///       
    {
        Queue*> q;
        BinTreeNode* pre = root;
        q.EnQueue(pre);
        cout << pre->data << " ";
        while(!q.IsEmpty())
        {
            q.DeQueue(pre);
            if(pre->lchild != NULL)
            {
                q.EnQueue(pre->lchild);
                cout << pre->lchild->data << " ";
            }
            if(pre->rchild != NULL)
            {
                q.EnQueue(pre->rchild);
                cout << pre->rchild->data << " ";
            }
        }
    }


};

template 
BinTreeNode *CreateBinTree(T* VLR, T* LVR, int n)   ///              
{
    if(n == 0)
        return NULL;
    int k = 0;
    while(VLR[0] != LVR[k])
        k++;
    BinTreeNode *t = new BinTreeNode(VLR[0]);
    t->lchild = CreateBinTree(VLR+1,LVR,k);
    t->rchild = CreateBinTree(VLR+k+1,LVR+k+1,n-k-1);
    return t;
}

int main()
{
    int n = 8;
    int a[8] = {1,2,4,7,3,5,6,8};   ///    
    int b[8] = {4,7,2,1,5,3,8,6};   ///    

    BinTreeNode *p = CreateBinTree(a,b,n);
    BinaryTree tree(p);
    tree.LevelOrder(p);     ///    
    cout << endl;
    tree.PostOrder(p);      ///    

    return 0;
}