通过递归的方法构建二叉树.

一、二叉树结点定义以及一些基本函数定义

①二叉树结点：

// 二叉树结点结构体 定义在BinaryTree.h文件中 #pragma once #include<iostream> using namespace std; template <class T> struct BinTNode { T data; BinTNode<T>* lchild, * rchild; BinTNode() :lchild(NULL), rchild(NULL) {} BinTNode(T x, BinTNode<T>* l = NULL, BinTNode<T>* r = NULL) :data(x), lchild(l), rchild(r) {} };

②二叉树类：

//二叉树类 同样定义在BinaryTree.h文件中 template <class T> class BinaryTree { protected: BinTNode<T>* root;//根结点 T tag;//输入终止符 public: BinaryTree() :root(NULL) {} BinaryTree(T x) :tag(x), root(NULL) {} ~BinaryTree() { DestroyTree(root); } BinTNode<T>* GetRoot(BinTNode<T>* p) { p = root; return p; }//取得根节点的地址 void DestroyTree(BinTNode<T>* tree); //删除一颗树 void CreateBinTree1(BinTNode<T>*& tree,char* pre); //根据前序序列建立二叉树 void CreateBinTree2(BinTNode<T>*& tree,char* post); //根据后序序列建立二叉树 void CreateBinTree3(BinTNode<T>*& tree, char* pre, char* in,int n);//根据前序+中序建立二叉树（其中n为序列长度） void CreateBinTree4(BinTNode<T>*& tree, char* in, char* post, int n);//根据中序+后序建立二叉树（其中n为序列长度） void OutputBinTree(BinTNode<T>*& tree); //按照前序序列打印二叉树 };

二、创建二叉树的函数：

①根据前序序列创建二叉树：

递归法建立，根据书上的代码做了一些改变，但是算法不变。

// 根据前序序列创建二叉树 template <class T> //tree是要建立树的结点，pre是前序序列 void BinaryTree<T>::CreateBinTree1(BinTNode<T>*& tree, char* pre) { T tmp; tmp = *pre; for (int i = 0; i < strlen(pre); i++) //读取完字符，就把所有字符前移一位，覆盖掉第一个字符 pre[i] = pre[i + 1]; //以确保后面每次调用第一个字符不与之前重复 if (tmp != tag) //正向写入树中 { tree = new BinTNode<T>(tmp); CreateBinTree1(tree->lchild, pre); CreateBinTree1(tree->rchild, pre); } else tree = NULL; }

②根据后序序列创建二叉树：

错误的方法： 很多人会以为只需要调①中间建立的三步的顺序就行了，但是这样是错误的，因为后序序列为“左右根”，建立第一个一定读取“#”，也就是空结点，程序直接把树置空了，就无法再进行下去了。 正确的方法： 我们把用户输入的后序序列反向读取，这样就由“左右根”的顺序变为了“根右左”，这样就解决了读取的第一个元素直接将树置空的问题。

有了思路后，就可以这样建立：

// 根据后序序列创建二叉树 template <class T> //tree是要建立树的结点，post是后序序列 void BinaryTree<T>::CreateBinTree2(BinTNode<T>*& tree, char* post) { T tmp; int l = strlen(post) - 1; tmp = post[l]; post[l] = '\0'; //用完就封口，使得下一次l的值变为前一位 if (tmp != tag) //反向写入树中 { tree = new BinTNode<T>(tmp); CreateBinTree2(tree->rchild,post); CreateBinTree2(tree->lchild,post); } else tree = NULL; }

③根据前序+中序序列创建二叉树：

前序：根左右 中序：左根右 根据序列的差异我们可以得出以下步骤： 1.找前序序列第一个结点，它是这棵树的根节点。 2.在中序中找这个结点，它左边就是左子树中序序列，右边就是右子树中序序列。 3.计算中序中确定的左子树结点个数n，在前序中除了根节点外的结点中取前n个，就是左子树的前序序列，剩余就是右子树前序序列。 4.由得到的左子树和右子树的前序、中序序列继续递归。当左右子树为空时递归结束。 举个例子： 前序序列：ABDC 中序序列：BDAC 由前序序列知，A为根节点。 在中序序列中查找A，找到它左边BD就是左子树中序序列，右边C就是右子树中序序列。 根据左子树中序序列BD的结点个数2，在前序序列除了根节点外的结点中找到前2个：BD就是左子树的前序序列，剩余C就是右子树的前序序列。 继续递归，左子树前序序列第一个是B，那么B就是左子树根节点。 在左子树中序序列BD中找到B，其左边没有结点，那么B的左子树为空。其右子树中序序列为：D。 在前序序列BD中找，除了根节点B以外的前0个节点是左子树前序序列，此处即左子树为空。剩余D就是右子树前序序列。 A的右子树为C。 这样就解得了二叉树的结构。 接下来我们只需要翻译以上算法即可。 代码如下：

// 根据前序+中序序列创建二叉树 template <class T> //tree是要建立树的结点，pre是前序序列，in是中序序列，n是序列长度 void BinaryTree<T>::CreateBinTree3(BinTNode<T>*& tree, char* pre, char* in, int n) { if (n <= 0) return;//递归结束条件，序列长度小于等于0 T tmp = *pre;//前序第一个节点必为根节点 tree = new BinTNode<T>(tmp); int m = 0; for (; m < n; m++)//找到根节点在中序中的下标 { if (tmp == in[m]) break; } //根据下标m分割序列，得到子树序列 CreateBinTree3(tree->lchild, pre + 1, in, m); CreateBinTree3(tree->rchild, pre + m + 1, in + m + 1, n - m - 1); }

④根据中序+后序序列创建二叉树：

算法同③，只是获取根节点的方式从前序第一个变成了后序最后一个。 代码如下：

// 根据中序+后序序列创建二叉树 template <class T> //tree是要建立树的结点，in是中序序列，post是后序序列，n是序列长度 void BinaryTree<T>::CreateBinTree4(BinTNode<T>*& tree, char* in, char* post, int n) { if (n <= 0) return;//递归结束条件，序列长度小于等于0 T tmp = post[n - 1];//后序最后一个节点必为根节点 tree = new BinTNode<T>(tmp); int m = 0; for (; m < n; m++)//获得根节点在中序的下标 { if (tmp == in[m]) break; } //根据下标m分割序列，得到子树序列 CreateBinTree4(tree->lchild, in, post, m); CreateBinTree4(tree->rchild, in + m + 1, post + m, n - m - 1); }

三、根据前序序列打印二叉树：

// 根据前序序列打印二叉树 template <class T> void BinaryTree<T>::OutputBinTree(BinTNode<T>*& tree) { if (tree != NULL) { cout << tree->data; if (tree->lchild != NULL || tree->rchild != NULL) { cout << "("; OutputBinTree(tree->lchild); cout << ","; OutputBinTree(tree->rchild); cout << ")"; } } }

四、测试程序：

// 在BinaryTree.cpp文件中 #include"BinaryTree.h" #include<string> int main() { int mode = 0; BinaryTree<char> Tree('#');//创建一个以“#”为终止符的树 BinTNode<char>* p = NULL; Tree.GetRoot(p);//获取根节点地址 //只通过前序或后序序列建立二叉树时只用到了list1 //通过结合前序+中序或者中序+后序建立二叉树时用list1和list2分别存储两个序列 char* list1 = new char[100], * list2 = new char[100]; string st1, st2; cout << "请输入选项：" << endl; cout << "【1】根据前序序列建立二叉树" << endl; cout << "【2】根据后序序列建立二叉树" << endl; cout << "【3】根据前序+中序建立二叉树" << endl; cout << "【4】根据中序+后序建立二叉树" << endl; cin >> mode; int n = 0; if (mode == 3 || mode == 4)//选择了同时根据两个序列构建二叉树 { cout << "请输入第一个序列：（无空节点，且每个节点之间无需用空格间隔开)" << endl; cin >> st1; list1 = (char*)st1.data();//将string类型转化为char* cout << "请输入第二个序列：（无空节点，且每个节点之间无需用空格间隔开)" << endl; cin >> st2; list2 = (char*)st2.data(); } else//选择了根据前序或后序建立二叉树 { cout << "请输入序列建立树：（(#)是空节点，且每个节点之间无需用空格间隔开)" << endl; cin >> st1; list1 = (char*)st1.data();//将string类型转化为char* } switch(mode) { case 1: Tree.CreateBinTree1(p, list1); break; case 2: Tree.CreateBinTree2(p, list1); break; case 3: Tree.CreateBinTree3(p, list1, list2, n); break; case 4: Tree.CreateBinTree4(p, list1, list2, n); break; default: cout << "输入参数错误！" << endl; } cout << "建立的树为：" << endl; Tree.OutputBinTree(p); return 0; }

五、结果展示：

界面：

根据后序建立二叉树：

根据前序+中序建立二叉树：（注意：输入的节点值不能相同，只有这样才能满足根据前序+中序或者中序+后序能建立唯一二叉树的要求。）

以上是我本人数据结构课程最近的一次作业所要求实现的功能，希望对大家有所帮助。 本人水平有限，如有出错之处，欢迎指正，谢谢大家。 最后一次修订：2020年10月29日.