扩充二叉树

扩充二叉树是二叉树中的一种，是指在二叉树中出现空子树的位置增加空树叶，所形成的二叉树。

详解扩充二叉树是二叉树中的一种，是指在二叉树中出现空子树的位置增加空树叶，所形成的二叉树。1

在二叉树中出现空的子树（包括树叶）上增加空的树叶，使子树成为满二叉树（国际定义）的二叉树称之为扩充二叉树。

从扩充的二叉树的根到每个外部结点的路径长度之和称为外部路径长度（E），扩充的二叉树里从根到每个内部结点的路径长度之和称为内部路径长度（I），它们之间的关系满足E=I+2N（N为内部结点数）。

代码实现由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树，所以对二叉树做如下处理，将二叉树的空结点用·补齐，如图所示。我们把这样处理后的二叉树称为原二叉树的扩展二叉树，扩展二叉树的先序和后序序列能唯一确定其二叉树。

现给出扩展二叉树的先序序列，要求输出其中序和后序序列。

输入扩展二叉树的先序序列。

输出输出其中序和后序序列。

输入样例ABD..EF..G..C..

输出样例DBFEGACDFGEBCA

代码#include#include#include#includeusing namespace std;typedef struct node;typedef node *tree;//tree相当于nodestruct node{//一个节点包括数据域，左右孩子 char data; treelchild,rchild;};tree bt;int i;string s;void build(tree &bt)//建树{ if(s[++i]!='.') { bt=new node; bt->data=s[i]; build(bt->lchild); build(bt->rchild); } else bt=NULL;}void printzx(tree &bt)//输出中序序列{ if(bt) { printzx(bt->lchild); coutrchild); } }void printhx(tree &bt)//输出后序序列{ if(bt) { printhx(bt->lchild); printhx(bt->rchild); cout>s; i=-1; build(bt); printzx(bt);//中序 cout