输入某二叉树的前序遍历和中序遍历的结果,重建出这棵二叉树,假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如,输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出这棵满足前序遍历和中序遍历的二叉树并输出它的头结点。
对一棵二叉树前序遍历的顺序是“根结点->左结点->右结点”,而中序遍历的顺序是“左结点->根节点->右结点”,因此,一般的思路都是酱紫的:
前序遍历列表中,第一个数据肯定是根节点,而中序遍历列表中,第一个数据肯定是树的最左结点,这样就可以得知,在前序遍历中,从根结点到最左结点一定是树的最左分支,也就是“1->2->4”;
接下来,在中序遍历中,访问完最左结点4之后因为其左结点为NULL要访问的就是4的右分支的最左结点了,为7,而在前序遍历中访问到最左结点之后就要访问右结点,发现也为7,说明7就是最左结点4的右分支上的最左结点,也就是只有7一个右结点;
然后,在中序遍历中访问完最左结点也就是以4为根节点子树之后,就要回到4结点的父节点了,也就是2,再往下访问是根节点1,也就是2并没有右结点;
至此会发现1为根节点的左子树已经全部访问完了;
上面没有再继续往下分析,是因为会发现,上面说的一堆虽然能把树给重建出来,但是很繁琐,逻辑上有关联却难以疏通个条理出来,因此要想转换为代码来实现想必又是要大费周折;
为什么分析到第四点就停下了,是因为第四点的式转换新思路的一个起点:
首先前面第一点中加粗的字体肯定是没有问题的,前序遍历中第一个数据一定是树的根结点;
再结合第四点,在中序遍历中找到这个根结点,会发现以1为根结点前面的数据都是1的左子树,有三个结点,那么在前序遍历中1后面的三个结点都是属于左子树的;因此,在1后面的数据肯定也都是在1的右子树上,有四个结点;
接下来看在前序遍历中跟在1后面的数据2是在1的左边还是右边,在左边就是1的左结点,在右边就是1的右结点;
然后按照前序遍历列表中的顺序将2看为新的根结点,那么在它左边的数据就是它左子树上的,右边的数据就是右子树上的,当然是截止到前一个根结点1为止;然后就再次循环从上一步开始;
可画图如下:
是不是会发现第二次的分析比第一次要简单明了多了?而且逻辑上有重复性,这样的分析用代码实现起来会比较容易,可以用递归来实现:
#include <iostream> #include <assert.h> using namespace std; typedef int data_type; //首先定义一个树结点的结构体并实现构造函数 struct BinaryTreeNode { data_type _data; BinaryTreeNode* _Lnode; BinaryTreeNode* _Rnode; BinaryTreeNode(data_type data) :_data(data) ,_Lnode(NULL) ,_Rnode(NULL) {} }; //重建二叉树,参数为两个遍历列表,树结点的个数,还有递归所需要知道子树的范围 BinaryTreeNode* RebuildBinaryTree(const data_type* prevlist, const data_type *inlist, const size_t num, size_t head, size_t tail) { assert(prevlist && inlist && num); //判断参数有效性 //前序遍历列表中第一个结点一定是树的根结点 BinaryTreeNode *root = new BinaryTreeNode(*prevlist); size_t root_index; //在中序遍历列表中找出根结点 for(root_index = 0; root_index < num; ++root_index) { if(inlist[root_index] == *prevlist) break; } if(inlist[root_index] != *prevlist) //检查给出的序列是否为有效的遍历序列 { cout<<"Invalid parameter..."<<endl; exit(0); } //当结点个数大于0的时候才表示会有子结点,否则为已经初始化过的NULL //传递首尾范围的时候,是不包括根结点的,因此要注意 size_t left_node_num = root_index - head;//根结点左边的结点个数 if(left_node_num > 0) root->_Lnode = RebuildBinaryTree(prevlist+1, inlist, num, head, root_index-1); size_t right_node_num = tail - root_index;//根结点右边的结点个数 if(right_node_num > 0) root->_Rnode = RebuildBinaryTree(prevlist+left_node_num+1, inlist, num, root_index+1, tail); return root; } //前序遍历检查二叉树是否正确重建 void PreOrder(BinaryTreeNode *root) { if(root != NULL) { cout<<root->_data<<"->"; PreOrder(root->_Lnode); PreOrder(root->_Rnode); } } int main() { data_type PrevOrderList[] = {1, 2, 4, 7, 3, 5, 6, 8}; data_type InOrderList[] = {4, 7, 2, 1, 5, 3, 8, 6}; size_t node_num = sizeof(PrevOrderList)/sizeof(PrevOrderList[0]); //这里的首部和尾部的表示范围都是在中序遍历中 size_t head = 0; size_t tail = node_num-1; BinaryTreeNode* root = RebuildBinaryTree(PrevOrderList, InOrderList, node_num, head, tail); cout<<"the root data: "<<root->_data<<endl; PreOrder(root); cout<<"NULL"<<endl; return 0; }
运行程序:
因为只是检查书是否重建好,用递归写树的先序遍历,输出发现和给定的先序遍历序列一样,则树重建完成。
《完》
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。