數據結構 二叉樹 已知前序中序遍歷求后續遍歷的遞歸實現
來源：程序員人生 發布時間：2015-08-03 09:03:31 閱讀次數：2652次
代碼很短，實現起來也很簡單，下面是代碼：
//
// 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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
