Binary.h
```cpp 在这里插入代码片 ```#include<iostream> #include<vector> using namespace std; //二叉树结点的定义 struct BinTreeNode { char data;//数据部分 //指针部分 BinTreeNode *leftChild;//左孩子结点指针 BinTreeNode *rightChild;//右孩子结点指针 //结构体二叉树结点的构造函数 BinTreeNode(char x, BinTreeNode *l = NULL, BinTreeNode *r = NULL) { data = x; leftChild = l; rightChild = r;//数据部分与孩子结点指针的初始化 } }; //访问结点函数的定义 void visit(BinTreeNode *t); //二叉树类的定义 class BinaryTree { public: //构造函数 BinaryTree(char* a, char* b, int n, int choice) : root(NULL)//: root(NULL)是对根节点root进行初始化 { if (choice == 1) root = CreateBinTree1(a, b, n); else if (choice == 2) root = CreateBinTree2(a, b, n); } //析构函数 ~BinaryTree() { Destroy(root);//删除结点函数 } //整个二叉树前序遍历函数 void PreOrder() { PreOrder(root);//调用二叉子树前序遍历函数，参数为根结点root } //整个二叉树中序遍历函数 void InOrder() { InOrder(root);//调用二叉子树中序遍历函数，参数为根结点root } //整个二叉树后序遍历函数 void PostOrder() { PostOrder(root);//调用二叉子树后序遍历函数，参数为根结点root } //输出整个二叉树函数 void PrintBinTree() { int level = 1; PrintBinTree(root, level); } /*看q里是否有p没有的元素或者反过来*/ /*bool Examie(char *p, char *q);*/ protected: /*二叉树的根指针*/ BinTreeNode *root; /*删除子树函数*/ void Destroy(BinTreeNode* subTree); /*已知前序序列与中序序列构造二叉子树函数*/ BinTreeNode* CreateBinTree1(char* VLR, char* LVR, int n); /*已知中序序列与后序序列构造二叉子树函数*/ BinTreeNode* CreateBinTree2(char* LVR, char* LRV, int n); /*二叉子树前序遍历函数*/ void PreOrder(BinTreeNode* subTree); /*二叉子树中序遍历函数*/ void InOrder(BinTreeNode* subTree); /*二叉子树后序遍历函数*/ void PostOrder(BinTreeNode* subTree); /*输出子树函数*/ void PrintBinTree(BinTreeNode* t, int level); }; Binary.cpp ```cpp #include"BinaryTree.h" #include<iostream> #include<vector> using namespace std; //访问结点函数 void visit(BinTreeNode *t) { cout << t->data; return; } //删除子树函数 void BinaryTree::Destroy(BinTreeNode* subTree) { if (subTree != NULL) { Destroy(subTree->leftChild);//对左孩子子树进行删除 Destroy(subTree->rightChild);//对右孩子子树进行删除 delete subTree;//释放当前结点内存 } return; } //已知前序序列与中序序列构造二叉树函数 BinTreeNode* BinaryTree::CreateBinTree1(char* VLR, char* LVR, int n) { if (n == 0)//结点数为0 return NULL; int k = 0; while (VLR[0]!= LVR[k])//找到左子树的结点个数 k++; BinTreeNode *tree = new BinTreeNode(VLR[0]);//创建根结点 tree->leftChild = CreateBinTree1(VLR + 1, LVR, k);//左子树部分进行构造 tree->rightChild = CreateBinTree1(VLR + k + 1, LVR + k + 1, n - k - 1);//右子树部分进行构造 return tree; } //已知中序序列与后序序列构造二叉树函数 BinTreeNode* BinaryTree::CreateBinTree2(char* LVR, char* LRV, int n) { if (n == 0) return NULL; int k = 0; while (LRV[n - 1] != LVR[k])//找到左子树的结点个数 k++; BinTreeNode *tree = new BinTreeNode(LRV[n - 1]);//创建根结点 tree->leftChild = CreateBinTree2(LVR, LRV, k);//左子树部分进行构造 tree->rightChild = CreateBinTree2(LVR + k + 1, LRV + k, n - k - 1);//右子树部分进行构造 return tree; } //前序遍历函数 void BinaryTree::PreOrder(BinTreeNode* subTree) { if (subTree != NULL) { visit(subTree);//访问根结点 PreOrder(subTree->leftChild);//前序遍历左子树 PreOrder(subTree->rightChild);//前序遍历右子树 } return; } //中序遍历函数 void BinaryTree::InOrder(BinTreeNode* subTree) { if (subTree != NULL) { InOrder(subTree->leftChild);//中序遍历左子树 visit(subTree);//访问根结点 InOrder(subTree->rightChild);//中序遍历右子树 } return; } //后序遍历函数 void BinaryTree::PostOrder(BinTreeNode* subTree) { if (subTree != NULL) { PostOrder(subTree->leftChild);//后序遍历右子树 PostOrder(subTree->rightChild);//后序遍历左子树 visit(subTree);//访问根结点 } return; } //输出子树函数 逆时针旋转90度 void BinaryTree::PrintBinTree(BinTreeNode* t, int level) { if (t == NULL)//如果二叉树为空则直接返回 return; PrintBinTree(t->rightChild, level + 1);//输出t的右子树部分 if (level != 1)//除了第一层结点外，其他层均需要输出空格与横线 { for (int i = 0; i < level - 2; i++) cout << "\t";//输出空格 cout << "----";//输出横线 } cout << t->data << endl;//输出当前结点数据 getchar();//所谓的动态输出，程序暂停，用户按任意键后，进行后续操作 PrintBinTree(t->leftChild, level + 1);//输出t的左子树部分 } 主函数（包括核心的检测函数） ```cpp #include"BinaryTree.h" #include<string> #include<iostream> #include<vector> using namespace std; //在字符串str1里寻找字符ch int GetP(string str, char ch) { int i; for (i = 0; i <= str.size() - 1; i++) { if (str[i] == ch)return i; } return -1; } //检测前序和中序能否构成二叉树，包括长度是否一致以及能够构成二叉树 int Examie1(string str1, string str2) { if (str1[0] != NULL && str2[0] != NULL)//判断序列是否遍历完毕 { int i, j; int p = GetP(str2, str1[0]);//在中序里找根节点在前序中所在的位置，返回下标 if (p == -1)return 0;//如果未找到根节点，GetP函数返回-1，则终止检查函数，返回0，不能构建为二叉树 if (p >= 0) { i = Examie1(str1.substr(1, p), str2.substr(0, p));//找到了根节点，则分别截取中序里根节点左侧元素 //从第一个元素开始截取，截取p个元素 }//同时截取前序序列里等长的p个元素序列，从第二个元素开始，构成新的前序序列，进行递归操作 //截取中序序列的右子树和前序序列的剩下部分 if (p < str1.size()) { j = Examie1(str1.substr(p + 1, (str1.size() - 1 - p)), str2.substr(p + 1, (str2.size() - 1 - p))); } //当二者都检测不出错误时，最后返回1，表示可以打印出二叉树 return (i + j == 2) ? 1 : 0;//必须i=j=1,才表示能够构建为二叉树 } //如果遍历完毕，则返回1,即检查过程中没有问题， else return 1; } int Examie2(string str1, string str2) { if (str1[0] != NULL && str2[0]!=NULL) { int i, j; int p = GetP(str1,str2[str2.size() - 1]);//在中序内找后续最后一个元素，即根节点 if (p == -1)return 0; if (p >= 0) { i = Examie2(str1.substr(0,p), str2.substr(0, p)); } if (p < str1.size()) { j = Examie2(str1.substr(p + 1, (str1.size() - 1 - p)), str2.substr(p , (str2.size() - 1 - p))); } return (i + j == 2) ? 1 : 0; } else return 1; } int main() { char a[100]; char b[100]; int choice = 0; while (1) { cout << "选择构造二叉树的方式：" << endl; cout << "1.前序序列与中序序列" << endl; cout << "2.中序序列与后序序列" << endl; cout << "0.结束" << endl; cin >> choice;//选择构造方式 if (choice == 0)//结束循环 { break; } else if (choice == 1)//前序序列与中序序列构造二叉树 { cout << "输入前序序列：" << endl; cin >> a; cout << "输入中序序列：" << endl; cin >> b; //计算两个序列的长度 int a_length = 0; int b_length = 0; for (int i = 0; a[i] != '\0'; i++) a_length++; for (int i = 0; b[i] != '\0'; i++) b_length++; if (a_length != b_length) { cout << "输入序列长度不一致" << endl; break; } for (int i = 0; i < a_length; i++) { for (int j = i + 1; j < a_length; j++) { if (a[i] == a[j]) { cout << "输入序列内有重复元素" << endl; exit(1); } } } for (int i = 0; i < b_length; i++) { for (int j = i + 1; j < b_length; j++) { if (b[i] == b[j]) { cout << "输入序列内有重复元素" << endl; exit(1); } } } string str1, str2;//将数组ab赋值给str1,str2 str1 = a; str2 = b; //两个序列不能构成二叉树时时 if (Examie1(str1,str2)==0) { cout << "输入错误！" << endl; cout << "请重新输入！" << endl; cout << endl; cout << endl; continue; } //构造二叉树,创建一个test类对象 BinaryTree Test(a, b, a_length,1); cout << "此二叉树为：" << endl; cout << "二叉树输出：" << endl; Test.PrintBinTree(); cout << endl; //分别输出前序、中序、后序序列 cout << "前序序列为：" << endl; Test.PreOrder(); cout << endl; cout << "\n中序序列为：" << endl; Test.InOrder(); cout << endl; cout << "\n后序序列为：" << endl; Test.PostOrder(); cout << endl; system("pause"); } else if (choice == 2)//中序序列与后序序列构造二叉树 { cout << "输入中序序列：" << endl; cin >> a; cout << "输入后序序列：" << endl; cin >> b; //计算两个序列的长度 int a_length = 0; int b_length = 0; for (int i = 0; a[i] != '\0'; i++) a_length++; for (int i = 0; b[i] != '\0'; i++) b_length++; if (a_length != b_length) { cout << "输入序列长度不一致" << endl; break; } for (int i = 0; i < a_length; i++) { for (int j = i + 1; j < a_length; j++) { if (a[i] == a[j]) { cout << "输入序列内有重复元素" << endl; exit(1); } } } for (int i = 0; i < b_length; i++) { for (int j = i+1; j < b_length; j++) { if (b[i] == b[j]) { cout << "输入序列内有重复元素" << endl; exit(1); } } } string str1, str2;//将数组ab赋值给str1,str2 str1 = a; str2 = b; //两个序列不能构成二叉树时时 if (Examie2(str1, str2) == 0) { cout << "输入错误！" << endl; cout << "请重新输入！" << endl; cout << endl; cout << endl; continue; } //构造二叉树 BinaryTree Test(a, b, a_length, 2); cout << "此二叉树为：" << endl; //旋转90度输出 cout << "二叉树输出：" << endl; Test.PrintBinTree(); cout << endl; //分别输出前序、中序、后序序列 cout << "前序序列为：" << endl; Test.PreOrder(); cout << endl; cout << "\n中序序列为：" << endl; Test.InOrder(); cout << endl; cout << "\n后序序列为：" << endl; Test.PostOrder(); cout << endl; system("pause"); } //输入错误 else if (choice != 1 && choice != 2 && choice != 0) { cout << "输入错误！请重新输入" << endl; cout << endl; cin >> choice; } } return 0; }