考试网 >> IT认证 >> 水平 >> 软件指导 >> 软件设计师试题疑难解答之四

发布时间：2006-06-28 05:10     点击：

问题1:关于二叉树的排序,有这样一个程序:

 由二叉树的前序遍历和中序遍历两个遍历序列能唯一确定一棵二叉树.

 如前序遍历:A,B,D,E,C,F,G;    中序遍历:D,B,E,A,,C,G,F;如以下事例;

A

                  B       C

D     E           F

              G

本程序实现已知某二叉树的前序遍历和中序遍历序列,生成一棵连接表示的二叉树.

 构造二叉树的算法要点是:由前序遍历序列,该序列的第一元素是根接点元素(例中A).该元素将中序遍历序列分成左右两部分,那些位于该元素之前的元素是它的左子树上的元素(如D,B,E);位于该元素之后的元素是它右子树上的元素(如C,G,F);对于左右子树,由他们的前序遍历序列的第一个元素可确定左,右子树的根接点,参照中序遍历序列又可进一步确定子树的左右子树元素.如此递归参照两个遍历序列,最终构造出二叉树

   两个遍历序列作为主函数main()的参数.为简单起见,程序假定两个遍历序列是相容的.主函数调用函数restore()建立的二叉树.函数restore()以树(子树)的前序遍历和中序遍历两序列及序列长为参数,采用递归方法建立树(子树).

函数postorder()实现二叉树的后续遍历输出,用来验证函数restore()建立的二叉树.

#include <stadio.h>

#include<stdlib.h>

#define MAX 100

typedef struct node{

          char info;

          struct node *llink,*rlink;

}TNODE;

char pred[MAX],inod[MAX];

TNODE restore(char*,char *,int);

Main(int argc,char **argv)

发表评论： 匿名发表 用户名: 查看评论

您将承担一切因您的行为、言论而直接或间接导致的民事或刑事法律责任 留言板管理人员有权保留或删除其管辖留言中的任意内容 本站提醒：不要进行人身攻击。谢谢配合。