根据二叉树的后续遍历序列和中序遍历序列，输出层次遍历序列
【问题描述】
l 需要基于二叉链表来实现二叉树ADT
l 需要实现二叉树的各个基本操作
l 假设二叉树中每个结点的关键字为不相同的正整数。给定二叉树的后序和中序遍历序列，基于二叉树的基本操作，实现二叉树的构建以及输出该二叉树的层次遍历序列。
【输入形式】
每个输入文件的第一行为一个正整数N（≤30），即二叉树中结点的总数。第二行给出了后续遍历序列，而第三行给出中序遍历序列。
注意：每一行中的所有数字都用一个空格隔开。
【输出形式】
相应二叉树的层次遍历序列输出在一行中。一行中的所有数字必须由一个空格隔开，并且行首和行尾不得有多余的空格。
【样例输入】
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
【样例输出】
4 1 6 3 5 7 2
代码如下：
Bintree.h
#include<iostream>
using namespace std;
template<typename E>
class BinNode//结点类
{
private:
BinNode*lc;//左孩子
BinNode*rc;//右孩子
E elem;
public:
BinNode()//默认构造函数，设置左右孩子为空
{
lc = rc = NULL;
}
BinNode(E tmp, BinNode*l=NULL, BinNode*r=NULL)//带参构造函数
{
elem = tmp;
lc = l;
rc = r;
}
BinNode*left()//返回左孩子
{
return lc;
}
BinNode*right()//返回右孩子
{
return rc;
}
void setLeft(BinNode*l)//设置左孩子
{
lc = (BinNode*)l;
}
void setRight(BinNode*r)//设置右孩子
{
rc = (BinNode*)r;
}
void setValue(E tmp)//设置当前结点的值
{
elem = tmp;
}
E getValue()//获得当前结点的值
{
return elem;
}
bool isLeaf()//判断当前结点是否为叶子结点
{
return (lc == NULL) && (rc == NULL);
}
};
template <typename E> class binTree
{
private:
void clear(BinNode<E>*r){}
void preOrder(BinNode<E>*tmp,void(*visit)(BinNode<E>*node)){}
void inOrder( BinNode<E>*tmp,void(*visit)(BinNode<E>*node)){}
void postOrder(BinNode<E>*tmp,void(*visit)(BinNode<E>*node)){}
void LevelOrderTranverse( BinNode<E>*tmp,void(*visit)(BinNode<E>*node)){}
int BinTreeDepth(BinNode<E>*tmp){}
int BinTreeNodes(BinNode<E>*tmp){}
int BinTreeHeight(BinNode<E>*tmp){}
int BinTreeLeafs(BinNode<E>*tmp){}
bool find(BinNode<E>*tmp, E e){}
public:
binTree(){}
~binTree(){}
virtual bool BinTreeEmpty()=0;
virtual BinNode<E>*getRoot()=0;
virtual void setRoot(BinNode<E>*r)=0;
virtual void clear()=0;
virtual void preOrder(void(*visit)(BinNode<E>*node))=0;
virtual void inOrder(void(*visit)(BinNode<E>*node))=0;
virtual void postOrder(void(*visit)(BinNode<E>*node))=0;
virtual void LevelOrderTranverse(void(*visit)(BinNode<E>*node))=0;
virtual int BinTreeDepth()=0;
virtual int BinTreeNodes()=0;
virtual int BinTreeHeight()=0;
virtual int BinTreeLeafs()=0;
virtual bool find(E e)=0;
};
BBintree.h
#include<iostream>
#include<queue>
#include "Bintree.h"
#include"string"
using namespace std;
template<typename E> class BinTree:public binTree<E>//二叉树类
{
private:
BinNode<E>*root;//根结点
void clear(BinNode<E>*r)//清空二叉树
{
if(r == NULL) return;
clear(r->left());
clear(r->right());
delete r;
}
void preOrder(BinNode<E>*tmp,void(*visit)(BinNode<E>*node))//先序遍历，void(*visit)(BinNode<E>*node)为一个函数指针参数，用visit代替传进来的函数，在遍历函数中使用传进来的函数功能
{
if(tmp == NULL) return;
visit(tmp);
preOrder(tmp->left(),visit);
preOrder(tmp->right(),visit);
}
void inOrder( BinNode<E>*tmp,void(*visit)(BinNode<E>*node))//中序遍历，void(*visit)(BinNode<E>*node)为一个函数指针参数，用visit代替传进来的函数，在遍历函数中使用传进来的函数功能
{
if(tmp == NULL) return;
inOrder(tmp->left(),visit);
visit(tmp);
inOrder(tmp->right(),visit);
}
void postOrder(BinNode<E>*tmp,void(*visit)(BinNode<E>*node))//后序遍历，void(*visit)(BinNode<E>*node)为一个函数指针参数，用visit代替传进来的函数，在遍历函数中使用传进来的函数功能
{
if(tmp == NULL) return;
postOrder(tmp->left(),visit);
postOrder(tmp->right(),visit);
visit(tmp);
}
void LevelOrderTranverse( BinNode<E>*tmp,void(*visit)(BinNode<E>*node))//层次遍历，void(*visit)(BinNode<E>*node)为一个函数指针参数，用visit代替传进来的函数，在遍历函数中使用传进来的函数功能
{
queue<BinNode<E>*> q ;
if(tmp == NULL) return;
if(tmp != NULL) {
q.push(tmp);
}
while(!q.empty()) {
BinNode<E>* t = q.front();
visit(t);
q.pop();
if(t->left() != NULL) q.push(t->left());
if(t->right() != NULL) q.push(t->right());
}
}
int BinTreeDepth(BinNode<E>*tmp)//获得二叉树的深度
{
if(BinTreeHeight(tmp)>0) return BinTreeHeight(tmp)-1;
else return 0;
}
int BinTreeNodes(BinNode<E>*tmp)//获得二叉树的结点数
{
if(tmp == NULL) return 0;
return 1 + BinTreeNodes(tmp->left())
+ BinTreeNodes(tmp->right());
}
int BinTreeHeight(BinNode<E>*tmp)//获得二叉树的高度
{
if(tmp == NULL) return 0;
else {
int lefth , righth;
lefth = BinTreeHeight(tmp->left());
righth = BinTreeHeight(tmp->right());
if(lefth > righth) return (lefth + 1);
else return (righth + 1);
}
}
int BinTreeLeafs(BinNode<E>*tmp)//获得二叉树的叶子结点数
{
if(tmp == NULL) return 0;
if(tmp->isLeaf()) return 1;
return (BinTreeLeafs(tmp->left())+BinTreeLeafs(tmp->right()));
}
bool find(BinNode<E>*tmp, E e)//查找二叉树中是否含有某个名为e的结点
{
if(tmp == NULL) return false;
if(tmp->getValue() == e) return true;
bool lresult = find(tmp->left(),e);
bool rresult = find(tmp->right(),e);
if(lresult || rresult) return true;
else return false;
}
public:
BinTree()//默认构造函数
{
root=new BinNode<E>;
}
~BinTree()//析构函数
{
clear(root);
}
bool BinTreeEmpty()//判断二叉树是否为空
{
if (root == NULL)
return true;
else
return false;
}
BinNode<E>*getRoot()//获得根节点
{
return root;
}
void setRoot(BinNode<E>*r)//设置根节点
{
root = r;
}
//下面的函数是对外的函数，所以内部还会有一些同名的函数，但是参数列表不一样，实现数据的封装，外部的调用不会涉及到内部的数据对象
void clear()//清空二叉树
{
clear(root);
root = NULL;
}
void preOrder(void(*visit)(BinNode<E>*node))//先序遍历，传入相对应的访问函数即可对该当前结点实现不同功能的访问（本程序为输出）
{
preOrder(root,visit);
}
void inOrder(void(*visit)(BinNode<E>*node)) //先序遍历，传入相对应的访问函数即可对该当前结点实现不同功能的访问（本程序为输出）
{
inOrder(root,visit);
}
void postOrder(void(*visit)(BinNode<E>*node))//先序遍历，传入相对应的访问函数即可对该当前结点实现不同功能的访问（本程序为输出）
{
postOrder(root,visit);
}
void LevelOrderTranverse(void(*visit)(BinNode<E>*node))//先序遍历，传入相对应的访问函数即可对该当前结点实现不同功能的访问（本程序为输出）
{
LevelOrderTranverse(root,visit);
}
int BinTreeDepth()//获得二叉树深度
{
return BinTreeDepth(root);
}
int BinTreeNodes()//获得二叉树结点数
{
return BinTreeNodes(root);
}
int BinTreeHeight()//获得二叉树高度
{
return BinTreeHeight(root);
}
int BinTreeLeafs()//获得二叉树叶子结点数
{
return BinTreeLeafs(root);
}
bool find(E e)//查找二叉树中是否存在名为e的结点
{
return find(root, e);
}
};
template<typename E>
void printNode(BinNode<E>*tmp)//打印结点的值的函数
{
cout << tmp->getValue() << " ";
}
template<typename E>
BinNode<E>* creatBinaryTree(E post[] , E in[] , int n)
{
if(n == 0) {
return NULL;
}
BinNode<E>*node = new BinNode<E>;
E root_elem = post[n];
node->setValue(root_elem);
int pos;
for(pos=0 ; pos<n ; pos++)
{
if(in[pos] == root_elem) break;
}
node->setLeft( creatBinaryTree(post , in , pos-1) );
node->setRight( creatBinaryTree(post+pos-1 , in+pos , n-pos) );
return node;
}
template<typename E>
void creatBinaryTree(BinTree<E>*BT)//构建二叉树的函数，包含了上面的构建二叉树的主函数，仅仅起到了在主函数中简洁一些的作用
{
int n = 0;
cin >> n;
E* a = new E[n+1];
E* b = new E[n+1];
for (int i = 1; i < n+1; i++)
{
cin >> a[i];
}
for (int i = 1; i < n+1; i++)
{
cin >> b[i];
}
BT->setRoot( creatBinaryTree<E>(a, b, n) );
}
main.cpp
#include "BBintree.h"
using namespace std;
/*void creatBinaryTree(BinTree<int>*BT)//构建二叉树的函数，包含了上面的构建二叉树的主函数，仅仅起到了在主函数中简洁一些的作用
{
int num = 0;
cin >> num;
int* a = new int[num+1];
int* b = new int[num+1];
for (int i = 1; i < num+1; i++)
{
cin >> a[i];
}
for (int i = 1; i < num+1; i++)
{
cin >> b[i];
}
BT->setRoot( creatBinaryTree<int>( a , b , num ) );
} */
int main()
{
BinTree<int>*BT = new BinTree<int>;
creatBinaryTree(BT);
BT->LevelOrderTranverse(printNode);
return 0;
}
使用了类模板，可以应对不同输入类型。
版权声明：本文为m0_52184277原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。