Ｃ++利用先序和中序（或中序和有序)创建二叉树

  1 #include <iostream>
  2 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