重建二叉樹

題目

　　輸入某二叉樹的前序遍歷和中序遍歷，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含有重覆的數字。

　　例如，前序遍歷序列：｛1，2，3，7，3，5，6，8｝，中序遍歷序列：｛4，7，2，1，5，3，8，6｝

答案

　　前序遍歷：

　　　　前序遍歷首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。

　　中序遍歷：

　　　　中序遍歷首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。在遍歷左、右子樹時，仍然先遍歷左子樹，再訪問根結點，最後遍歷右子樹。

  1 #include "stdafx.h"
  2 #include<deque>
  3 #include<iostream>
  4 #define TREElEN 6
  5 
  6 struct BinaryTreeNode
  7 {
  8     int                   m_nValue;
  9     BinaryTreeNode*       m_pLeft;
 10     BinaryTreeNode*       m_pRight;
 11 };
 12 
 13 void PrintTreeNode(BinaryTreeNode* pNode)
 14 {
 15     if(pNode != NULL)
 16     {
 17         printf("value of this node is: %c\n", pNode->m_nValue);
 18 
 19         if(pNode->m_pLeft != NULL)
 20             printf("value of its left child is: %c.\n", pNode->m_pLeft->m_nValue);
 21         else
 22             printf("left child is null.\n");
 23 
 24         if(pNode->m_pRight != NULL)
 25             printf("value of its right child is: %c\n", pNode->m_pRight->m_nValue);
 26         else
 27             printf("right child is null\n");
 28     }
 29     printf("\n");
 30 }
 31 
 32 void PrintTree(BinaryTreeNode* pRoot)
 33 {
 34     PrintTreeNode(pRoot);
 35 
 36     if(pRoot != NULL)
 37     {
 38         if(pRoot->m_pLeft != NULL)
 39             PrintTree(pRoot->m_pLeft);
 40 
 41         if(pRoot->m_pRight != NULL)
 42             PrintTree(pRoot->m_pRight);
 43     }
 44 }
 45 
 46 BinaryTreeNode* rebuild(char *preOrder, char* inOrder, int length)
 47 {
 48     if(preOrder == NULL || inOrder == NULL || length <= 0)
 49         return NULL;
 50 
 51     char c = preOrder[0];
 52 
 53     BinaryTreeNode* root = new BinaryTreeNode();
 54     root->m_nValue = c;
 55     root->m_pRight = root->m_pLeft = NULL;
 56 
 57     int i ;
 58     for(i = 0 ; i < length && inOrder[i] != c ; i++);
 59     int leftLength = i;
 60     int rightLength = length - i - 1;
 61 
 62     if(leftLength > 0)
 63             root->m_pLeft = rebuild(&preOrder[1],&inOrder[0],leftLength);
 64 
 65     if(rightLength>0)
 66             root->m_pRight = rebuild(&preOrder[leftLength + 1], &inOrder[leftLength+1], rightLength);
 67     return root;
 68 }
 69 
 70 void PrintFromTopToBottom(BinaryTreeNode* pRoot)
 71 {
 72     if(pRoot == NULL)
 73         return;
 74 
 75     std::deque<BinaryTreeNode *> dequeTreeNode;
 76 
 77     dequeTreeNode.push_back(pRoot);
 78 
 79     while(dequeTreeNode.size())
 80     {
 81         BinaryTreeNode *pNode = dequeTreeNode.front();
 82         dequeTreeNode.pop_front();
 83 
 84         printf("%c ", pNode->m_nValue);
 85 
 86         if(pNode->m_pLeft)
 87             dequeTreeNode.push_back(pNode->m_pLeft);
 88 
 89         if(pNode->m_pRight)
 90             dequeTreeNode.push_back(pNode->m_pRight);
 91     }
 92 }
 93 // 普通二叉樹
 94 //              a
 95 //           /     \
 96 //          b       c  
 97 //         /       / \
 98 //        d       e   f
 99 int main()
100 {
101     char PreOrder[TREElEN] = {'a', 'b', 'd', 'c', 'e', 'f'};
102     char InOrder[TREElEN] =  {'d', 'b', 'a', 'e', 'c', 'f'};
103     BinaryTreeNode* result = rebuild(PreOrder, InOrder, 6);
104     PrintFromTopToBottom(result);
105     printf("\n\n");
106     PrintTree(result);
107 }