題目
輸入某二叉樹的前序遍歷和中序遍歷,請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含有重復的數字。
例如,前序遍歷序列:{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 }