二叉树测试用例:
preOrder: ABDGCEFH inOrder: DGBAECHF postOrder: GDBEHFCA
已知二叉树前序遍历序列和中序遍历序列可以确定一颗二叉树。
已知二叉树中序遍历序列和后序遍历序列可以确定一颗二叉树。
已知二叉树前序遍历序列和后序遍历序列不能确定一颗二叉树。
已知二叉树前序和中序遍历序列,构造二叉树,C++实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 #include <iostream> #include <stack> #include <cstring> using namespace std ;struct node { char value; node *lchild; node *rchild; node(char ch) { value = ch; lchild = NULL ; rchild = NULL ; } }; void preOrder (node *root) { if (root) { cout << root->value; preOrder(root->lchild); preOrder(root->rchild); } } void inOrder (node *root) { if (root) { inOrder(root->lchild); cout << root->value; inOrder(root->rchild); } } void postOrder (node *root) { if (root) { postOrder(root->lchild); postOrder(root->rchild); cout << root->value; } } node *buildBitree (string pre, string in) { int len = pre.length(); if (len <= 0 ) { return NULL ; } node *root = new node(pre[0 ]); int n = in.find (pre[0 ]); root->lchild = buildBitree(pre.substr(1 , n), in.substr(0 , n)); root->rchild = buildBitree(pre.substr(n + 1 , len - n - 1 ), in.substr(n + 1 , len - n - 1 )); return root; } int main () { char pre[100 ], in[100 ]; while (cin >> pre >> in) { node *root = buildBitree(pre, in); postOrder(root); cout << endl ; } return 0 ; }
已知二叉树中序和后序遍历序列,构造二叉树,C++实现: 1 2 3 4 5 6 7 8 9 10 11 12 13 node *buildBitree (string post, string in) { int len = post.length(); if (len <= 0 ) { return NULL ; } node *root = new node(post[len - 1 ]); int n = in.find (post[len - 1 ]); root->lchild = buildBitree(post.substr(0 , n), in.substr(0 , n)); root->rchild = buildBitree(post.substr(n, len - n - 1 ), in.substr(n + 1 , len - n - 1 )); return root; }
Notes:
str.length()、str.size()均用来求取字符串的长度。