二叉树遍历
一、 问题需求分析
编写一个程序实现二叉树的先根、中根、后根遍历。
二、抽象数据类型的设计
先定义一个树的结构体，里面包含数据类型 int data，左指针*left,右指针
*right。然后创建二叉树，定义结点下标为：int pos,数据指针变量：*data。根
据二叉树左右孩子与结点下标的关系，利用一个指针把数组的值附到二叉树中。
二叉树的先，中，后根遍历，调用递归算法，然后输出结果。Main 函数中定
义一个数组，输入想输入的值，然后调用创建函数，把值附给二叉树。
三、算法与数据结构的设计
要遍历的二叉树，如图所视：
由图形可知，此二叉树的前序遍历为：5，4，2，7，9，8，6，1，3；
中序遍历为：7，2，9，4，8，5，1，6，3；
后序遍历为：7，9，2，8，4，1，3，6，5；
所以，先进性前序遍历，定义一个指针 p,把根结点附给 p,p 非空时，向屏幕
输出数据。然后往左移，遍历完左子树，再遍历右子树，至 p 为空。中序遍历时，
指针左移，查找数据，然后输出，遍历完左子树后，再右移，输出。后序遍历时，
指针左移，遍历完左子树，再遍历右子树，然后输出。
四、算法的精化与程序的实现
评论0