非递归遍历二叉树.doc

/*非递归遍历二叉树*/ #include#include#defineStack_Init_Size100#defineStackIncreament10typedefstructBiLnodeintdata;structBiLnode*lchild;structBiLnode*rchild;BiLnode,*BiTree;typedefstructBiTree*top;BiTree*base;intstacksize;SqStack;/定义栈voidInitStack(SqStack&s)s.base=(BiTree*)malloc(Stack_Init_Size*sizeof(BiTree);/栈底地址if(!s.base)printf(errorn);s.top=s.base;s.stacksize=Stack_Init_Size;/构造空栈/初始化栈voidPush(SqStack&s,BiTreee)if(s.top-s.base=s.stacksize)/本满，追加存储空间s.base=(BiTree*)realloc(s.base,(s.stacksize+StackIncreament)*sizeof(BiTree);if(!s.base)printf(errorn);s.top=s.base+s.stacksize;s.stacksize+=StackIncreament;*s.top+=e;/向栈顶插入元素evoidPop(SqStack&s,BiTree&e)if(s.top=s.base)printf(error2n);e=*-s.top;/删除栈顶元素intStackEmpty(SqStacks)if(s.top=s.base)return1;elsereturn0;/判断栈是否为空voidCreateBiTree(BiTree&T)/单个生成结建立二叉树printf(输入7个树结点的值：);T=(BiTree)malloc(sizeof(BiLnode);BiTreep1=T;BiTreep2=(BiTree)malloc(sizeof(BiLnode);BiTreep3=(BiTree)malloc(sizeof(BiLnode);BiTreep4=(BiTree)malloc(sizeof(BiLnode);BiTreep5=(BiTree)malloc(sizeof(BiLnode);BiTreep6=(BiTree)malloc(sizeof(BiLnode);BiTreep7=(BiTree)malloc(sizeof(BiLnode);scanf(%d,&p1-data);p1-lchild=p2;p1-rchild=p6;scanf(%d,&p2-data);p2-lchild=p3;p2-rchild=p5;scanf(%d,&p3-data);p3-lchild=p4;p3-rchild=NULL;scanf(%d,&p4-data);p4-lchild=NULL;p4-rchild=NULL;scanf(%d,&p5-data);p5-lchild=NULL;p5-rchild=NULL;scanf(%d,&p6-data);p6-lchild=NULL;p6-rchild=p7;scanf(%d,&p7-data);p7-lchild=NULL;p7-rchild=NULL;/*voidDLR(BiTreeT)/先序遍历二叉树if(!T)return;elseprintf(%d,T-data);/访问二叉树树根DLR(T-lchild);/访问根的左子树DLR(T-rchild);访问右子树*/voidInOrderTraverse(BiTreeT,SqStacks)InitStack(s);/初始化栈BiTreep=T;Push(s,p);/树根进栈while(!StackEmpty(s)|!p)/当栈空或结点为空时结束if(p)/P非空访问结点，结点进栈，访问该结点左子树printf(%d,p-data);Push(s,p);p=p-lchild;else/P空结点出栈，访问右子树Pop(s,p);p=p-rchild;intma