二叉树递归遍历.docx

文档介绍：题目：假设二叉树采用二叉链表结构。设计并实现如下算法：先序递归建树， 中序非递归遍历该树，输出各个结点的值，并求该树中单分支结点的个数。
一、 需求分析
用户可以根据自己的需求分别输入任意的一个二叉树，并且能够实现中序非递归遍历该 树输ck *s)
{ if(s->top==s->base) return 1;
else return 0;
}
/*入栈*/
stack *push(stack *s,struct bitnode *t)
{ if(s->top-s->base==s->size)
{ s->base=(struct node *)realloc(s->base,(s->size+10)*sizeof(node)); if(!s->base) exit(0);
s->top=s->base+s->size;
s->size+=10;
}
(*s->top).p=t;
s->top++;
return s;
}
/*出栈*/
struct bitnode *pop(stack *s)
{ if(s->top==s->base)
{ prin tf("这是一个空栈\n");
return 0;
}
else
{ s->top--;
return ((*s->top).p);
}
}
/*取栈顶的元素*/ struct bitnode *getpop(stack *s)
{ if(s->top==s->base)
{ printf("这是一个的空栈！ \n");
return NULL;
}
else return (*(s->top-1)).p;
}
/*先序递归构建二叉树*/
struct bitnode *creatbitree(struct bitnode *r)
{ char a; scanf("%c",&a);
if(a==' ') return r=NULL; else
{ r=(struct bitnode*)malloc(sizeof(bitnode)); r->data=a;
r->lchild=creatbitree(r->lchild); r->rchild=creatbitree(r->rchild);
} return r;
}
/*中序非递归遍历二叉树*/
void inorder(struct bitnode *T)
{ struct bitnode *p,*q;
p=T; s=initstack();
if(p)
{ while(p)
{ push(s,p); p=p->lchild;
} while(!stackempty(s))
{ p=pop(s); visit(p->data);
if(p->rchild!=NULL)
{ q=p->rchild; while(q)
{ push(s,q); q=q->lchild;
}
}
}
}
}
/*求二叉树的结点总数*/
int counter(struct bitnode *T)
{ int num1,num2,num;
if(T==NULL) return 0;
else
{ num1=counter(T->lchild); num2=counter(T->rchild);
num=num1+num2+1;
return num;
}
}
/*求二叉树的单分支的结点数*/
int onecount(struct bitnode *T)
{ int s1,s2;
if(T==NULL) return(0);
else
{ s1=onecount(T->lchild); s2=onecount(T->rchild);
if((T->lchild!=NULL&&T->rchild==NULL)||(T->rchild!=NULL&&T->lchild==NULL)) return (s1+s2+1);
else return (s1+s2);
}
}
主函数和其他函数的伪码算法
main()
{ int sum;
printf("xian xu shu ru bitree:\n");
T=creatbitree(T); /*创建二叉树*/
a=counter(T); /*求结点总数*/
printf("\na=%d\n",a);
printf("\nxian xu bian li bitree:\n");
inorder(T); /*中序遍历二叉树*/
sum=onecount(T); /*求单分支的结点数*/
printf("\n\nthe bitr