您所在位置：主题：[讨论]中序法构造二叉树
pjjoe
[专家分：180] 发布于 2007-08-14 22:19:00
请教各位，如何用修改中序遍历二叉树法来构造二叉树？如输入：（（a+b）*(a-b)），建立下图的二叉树：
[img]http://116.img.pp.sohu.com/images/blog/2007/8/14/22/13/114fe9d4a83.jpg[/img]
中序遍历算法为：
void Inorder(tree *t, int first)
{
tree *current;
if (first)
{
current=head; //初始时current应指向当前二叉树的根
first=0;
}
else current=t;
if (current != Null)
{
Inorder(current->lchild,first); //遍历左子树
cout<<current->data; //访问根
Inorder（current->rchild,first）; //遍历右子树
}
}
我们通常是修改先序遍历法来生成二叉树.现在我想用中序法（如上所示），使得可以将一个算术式子转化成为一个二叉树。我想修改上述的中序法，可是遇到很多困难，如不知道如何处理叶子，如何利用递归（我估计用递归会无法实现，因为它不像先序法）。现在几乎毫无头绪，请教大家，谢谢！
[img]http://116.img.pp.sohu.com/images/blog/2007/8/14/22/13/114fe9d4a83.jpg[/img]
中序遍历算法为：
void Inorder(tree *t, int first)
{
tree *current;
if (first)
{
current=head; //初始时current应指向当前二叉树的根
first=0;
}
else current=t;
if (current != Null)
{
Inorder(current->lchild,first); //遍历左子树
cout<<current->data; //访问根
Inorder（current->rchild,first）; //遍历右子树
}
}
我们通常是修改先序遍历法来生成二叉树.现在我想用中序法（如上所示），使得可以将一个算术式子转化成为一个二叉树。我想修改上述的中序法，可是遇到很多困难，如不知道如何处理叶子，如何利用递归（我估计用递归会无法实现，因为它不像先序法）。现在几乎毫无头绪，请教大家，谢谢！
