数据结构课程设计之-树与二叉树的转换(4)

5先序遍历树的非递归算法

若二叉树为空，则空操作；否则（1）先将根节点进栈，在栈不为空时循环；(2)出栈p，访问*p若其右孩子节点不空将右孩子节点进栈若其左孩子节点不空时再将其左孩子节点进栈。

6后序遍历树的非递归算法

采用一个栈保存需要返回的指针，先扫描根节点所有的左孩子节点并一一进栈，出栈一个节点*b作为当前节点，然后扫描该节点的右子树。当一个节点的左右孩子节点均访问后再访问该节点，如此重复操作，直到栈空为止。 7层次序的非递归遍历

按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。void LevelOrder(BiNode root)。

三．详细设计

1树的建立：

PTree CreatTree(PTree T) {

int i=1; int fa,ch; PTNode p;

for(i=1;ch!=-1;i++) {

printf("输入第%d结点:\n",i); scanf("%d,%d",&fa,&ch); printf("\n"); p.data=ch; p.parent=fa; T.count++;

T.node[T.count].data = p.data; T.node[T.count].parent = p.parent; }

printf("\n");

printf("创建的树具体情况如下:\n"); print_ptree(T); return T;

2一般树转换成二叉树

BTNode *change(PTree T) { int i,j=0; BTNode p[MAX_TREE_SIZE]; BTNode *ip,*is,*ir,*Tree; ip=(BTNode *)malloc(sizeof(BTNode)); is=(BTNode *)malloc(sizeof(BTNode)); ir=(BTNode *)malloc(sizeof(BTNode)); Tree=(BTNode *)malloc(sizeof(BTNode)); for(i=0;i<T.count;i++) { p[i]=GetTreeNode(T.node[i].data); } for(i=1;i<T.count;i++) { ip=&p[i]; is=&p[j]; while(T.node[i].parent!=is->data)