数据结构 二叉树 已知前序中序遍历求后续遍历的递归实现
来源：程序员人生 发布时间：2015-08-03 09:03:31 阅读次数：2476次
代码很短，实现起来也很简单，下面是代码：
//
// main.cpp
// PreMidgetPost
//
// Created by xin wang on 4/29/15.
// Copyright (c) 2015 xin wang. All rights reserved.
//
#include <iostream>
//链表2叉树的节点类
template <class T>
class BinaryTreeNode{
public:
BinaryTreeNode(){LeftChild = RightChild=0;}
BinaryTreeNode(const T& e){
data=e;
LeftChild=RightChild =0;
}
BinaryTreeNode(const T& e,BinaryTreeNode *l,BinaryTreeNode *r){
data = e;
LeftChild =l;
RightChild =r;
}
T data;
BinaryTreeNode<T> *LeftChild,*RightChild;
};
//定义1个数组，分别装前序遍历和中序遍历的数组
int pre_order[100];
int mid_order[100];
BinaryTreeNode<int> *translate(int pre_l,int pre_r,int mid_l,int mid_r){
if (pre_r-pre_l<0) {//
return 0;
}
BinaryTreeNode<int> *root;//new1个root节点
root= new BinaryTreeNode<int>;
root->data=pre_order[pre_l];//前序遍历的第1个节点是跟节点
std::cout<<root->data<<"root"<<std::endl;
if (pre_r==pre_l) {//如果二者相等，说明只有1个树节点
root->LeftChild=NULL;
root->RightChild=NULL;
return root;
}
int index;//找到中序遍历中跟节点所在的位置
for (index = mid_l; index<=mid_r; index++) {
if (mid_order[index] == pre_order[pre_l]) {
break;
}
}
root->LeftChild = translate(pre_l+1, pre_l+(index-mid_l), mid_l, index⑴);//递归找到跟节点的左孩子的值
root->RightChild= translate(pre_l+(index-mid_l)+1,pre_r , index+1, mid_r);//递归找到根节点右孩子的值
return root;
}
//将后序遍历打印出来
void post_Order(BinaryTreeNode<int> *root){
if(root){
post_Order(root->LeftChild);
post_Order(root->RightChild);
std::cout<<"值"<<root->data<<std::endl;
}
}
int main(int argc, const char * argv[]) {
int in=0;
std::cout<<"请输入数组的长度："<<std::endl;
std::cin>>in;
std::cout<<"请输入数组前序"<<std::endl;
int zu;
int bb=0;
int num=0;
while (bb<in) {
std::cin>>zu;
pre_order[num]=zu;
num++;
bb=bb+1;
}
std::cout<<"请输入数组的中序"<<std::endl;
int zuzhong;
int numzhong=0;
int aa=0;
while(aa<in){
std::cin>>zuzhong;
mid_order[numzhong]=zuzhong;
numzhong++;
aa=aa+1;
}
BinaryTreeNode<int> *root = translate(0, in⑴, 0, in⑴);
std::cout<<"后序遍历"<<std::endl;
post_Order(root);
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
