Ｃ++利用先序和中序（或中序和有序)创建二叉树
对于二叉树，存在两个基本的性质。
１、已知先序和中序遍历的序列，可以唯一确定一颗二叉树。
２、已知中序和后续遍历的序列，可以唯一确定一个二叉树。
下面给出其C++的具体实现：
1 #include2 using namespace std; 3 4 typedef char ElemType; 5 6 //二叉树链式结构实现 7 typedef struct BinaryTreeNode 8 { 9 ElemType data; 10 BinaryTreeNode *left; 11 BinaryTreeNode *right; 12 }BinaryTreeNode, *tree; 13 14 /*先序遍历二叉树的节点*/ 15 void PreOrderTraverse (const tree &T); 16 /*中序遍历二叉树的节点*/ 17 void InOrderTraverse (const tree &T); 18 /*后续遍历二叉树的节点*/ 19 void PostOrderTraverse (const tree &T); 20 /*按照先序创建二叉树，本例中我们将每个二叉树的节点的空指针引出一个虚节点（代表该节点后面不会再有新的节点， 21 * 即该子书生长结束），其值为一特值，此处使用'#'。因此我们在创建子树时输入的先序序列为AB#D##C##，其只有四个节点 22 * 如下所示： 23 * A Ａ 24 * / \ / \ 25 * 普通二叉树： B C 扩展二叉树： B C 26 * \ / \ / \ 27 * D # D # # 28 * / \ 29 * # # 30 */ 31 /*根据二叉树的先序和中序遍历序列，创建二叉树。 32 * 核心思想：根据先序序列的第一个记录为跟节点，在中序序列中查找其跟节点的位置， 33 * 中序序列中的根节点左边的为中序左子树，右边的为中序右子树，由于左子树（或者右子树） 34 * 在先序和中序中的长度相同，因此可以获得先序左子树和先序右子树，根据该根节点创建二 35 * 叉树的节点，并将新获取的先序（中序）左右子树递归的创建二叉树。 Ａ 36 * 实例中先序序列:ABCDEF 二叉树结构： / \ 37 * 中序序列:CBAEDF B D 38 * 后序序列:CBEFDA / / \ 39 * presequence:先序序列 C E F 40 * insequence:中序序列*/ 41 void CreateTreeByPI (tree &T, std::string presequence, std::string insequence); 42 /*与根据先序和中序遍历序列创建二叉树相似*/ 43 void CreateTreeByIP (tree &T, std::string insequence, std::string postsequence); 44 void CreateTree (tree &T); 45 46 void PreOrderTraverse (const tree &T) 47 { 48 if (!T)//空树 49 { 50 return; 51 } 52 cout << T->data << " "; 53 PreOrderTraverse (T->left); 54 PreOrderTraverse (T->right); 55 } 56 57 void InOrderTraverse (const tree &T) 58 { 59 if (!T)//空树 60 { 61 return; 62 } 63 InOrderTraverse (T->left); 64 cout << T->data << " "; 65 InOrderTraverse (T->right); 66 } 67 68 void PostOrderTraverse (const tree &T) 69 { 70 if (!T)//空树 71 { 72 return; 73 } 74 PostOrderTraverse (T->left); 75 PostOrderTraverse (T->right); 76 cout << T->data << " "; 77 } 78 79 void CreateTree (tree &T) 80 { 81 char input; 82 cout << "Please input a char: "; 83 cin >> input; 84 if ('#' == input)//默认'#'为结束标示 85 { 86 return; 87 } 88 else 89 { 90 T = new BinaryTreeNode; 91 T->data = input; 92 if (!T)//new failed 93 { 94 return; 95 } 96 CreateTree (T->left); 97 CreateTree (T->right); 98 } 99 }100 101 102 void CreateTreeByPI (tree &T, std::string presequence, std::string insequence)103 {104 if (0 == presequence.length () ||105 (presequence.length () != insequence.length ()))106 {107 return;108 }109 char rootNode = presequence[0];110 int index = insequence.find (rootNode);111 std::string lchild_insequence = insequence.substr (0, index);112 std::string rchild_insequence = insequence.substr (index + 1, insequence.length () - index);113 int lchild_length = index;114 int rchild_length = rchild_insequence.length ();115 std::string lchild_presequence = presequence.substr (1, lchild_length);116 std::string rchild_presequence = presequence.substr (1 + lchild_length, rchild_length);117 118 T = new BinaryTreeNode;119 if (T)120 {121 T->data = rootNode;122 CreateTreeByPI (T->left, lchild_presequence, lchild_insequence);123 CreateTreeByPI (T->right, rchild_presequence, rchild_insequence);124 }125 }126 127 128 void CreateTreeByIP (tree &T, std::string insequence, std::string postsequence)129 {130 if (0 == insequence.length () ||131 insequence.length () != postsequence.length ())132 {133 return;134 }135 char rootNode = postsequence[postsequence.length () - 1];136 int index = insequence.find (rootNode);137 std::string lchild_insequence = insequence.substr (0, index);138 std::string rchild_insequence = insequence.substr (index + 1, insequence.length () - index);139 int lchild_length = index;140 int rchild_length = rchild_insequence.length ();141 std::string lchild_postsequence = postsequence.substr (0, lchild_length);142 std::string rchild_postsequence = postsequence.substr (lchild_length, rchild_length);143 144 T = new BinaryTreeNode;145 if (T)146 {147 T->data = rootNode;148 CreateTreeByIP (T->left,lchild_insequence, lchild_postsequence);149 CreateTreeByIP (T->right, rchild_insequence, rchild_postsequence);150 }151 }152 153 int main ()154 {155 tree T1;156 string pre = "ABCDEF";157 string in = "CBAEDF";158 string post = "CBEFDA";159 CreateTreeByPI (T1, pre, in);160 cout << "树T1的后序遍历为： ";161 PostOrderTraverse (T1);162 163 tree T2;164 CreateTreeByIP (T2, in, post);165 cout << "\n";166 cout << "树T2的前序遍历为： ";167 PreOrderTraverse (T2);168 return 0;169 }
运行结果如下：
树T1的后序遍历为： C B E F D A 树T2的前序遍历为： A B C D E F