二叉树非递归遍历.rar

#include <stdio.h> #include <stdlib.h> #include <conio.h> #define MS 50 struct BTreeNode { char date; struct BTreeNode *lchild; struct BTreeNode *rchild; }; typedef struct BTreeNode TNODE; TNODE *creat(int n) { int i,j; char x; TNODE *narr[100],*p,*t; for(j=1;j<=n;j++) { printf("input i,x:\n"); scanf("%d,%c",&i,&x); p=(TNODE*)malloc(sizeof(TNODE)); p->date=x; p->lchild=NULL; p->rchild=NULL; narr[i]=p; if(i==1) t=p; else { if(i%2==0) narr[i/2]->lchild=p; else narr[i/2]->rchild=p; } } return(t); } void Preorder(struct BTreeNode *BT) { if(BT!=NULL) { printf("%5c", BT->date); Preorder(BT->lchild); Preorder(BT->rchild); } } void Inorder(struct BTreeNode *BT) { if(BT!=NULL) { Inorder(BT->lchild); printf("%5c", BT->date); Inorder(BT->rchild); } } void Postorder(struct BTreeNode *BT) { if(BT!=NULL) { Postorder(BT->lchild); Postorder(BT->rchild); printf("%5c", BT->date); } } void PreorderN(struct BTreeNode *BT) { struct BTreeNode *s[20]; int top=-1; struct BTreeNode *p=BT; while(top!=-1||p!=NULL) { while(p!=NULL) { top++; s[top]=p; printf("%5c",p->date); p=p->lchild; } if(top!=-1) { p=s[top]; top--; p=p->rchild; } } } void InorderN(struct BTreeNode *BT) { struct BTreeNode *s[20]; int top=-1; struct BTreeNode *p=BT; while(top!=-1||p!=NULL) { while(p!=NULL) { top++; s[top]=p; p=p->lchild; } if(top!=-1) { p=s[top]; top--; printf("%5c",p->date); p=p->rchild; } } } void PostorderN(struct BTreeNode *BT) { struct BTreeNode *s[20]; int top=-1,flag=1; struct BTreeNode *p=BT,*q; do{ while(p!=NULL) { top++; s[top]=p; p=p->lchild; } q=NULL; flag=1; while(top!=-1&&flag) { p=s[top]; if(p->rchild==q) { printf("%5c",p->date); top--; q=p; } else { p=p->rchild; flag=0; } } }while(top!=-1); } void main() { TNODE *t; int a; printf("input the number of BTreeNode\n"); scanf("%d",&a); t=creat(a); printf("中序遍历:"); Inorder(t); printf("\n"); InorderN(t); printf("\n"); printf("先序遍历:"); Preorder(t); printf("\n"); PreorderN(t); printf("\n"); printf("后序遍历:"); Postorder(t); printf("\n"); PostorderN(t); printf("\n"); }