打印二叉树中根到所有叶子结点的路径

题目

输入一批数据，以999作为结束数据，建立一颗二叉排序树，通过遍历输出递增排序结果，给出此二叉树中根到所有叶子结点的路径。 分析可参照==== 关键非递归的后序遍历算法

代码

#include "stdio.h"
#include "malloc.h"
#define LEN sizeof(bitnode)
#define max 20
typedef struct node {
          
   
	int data;
	struct node *lchild;
	struct node *rchild;
}*bitree,bitnode;
//创建二叉排序树
void creat(bitree *root,int data) {
          
   
	if(*root==NULL) {
          
   
		(*root)=(bitree)malloc(LEN);
		(*root)->data = data;
		(*root)->lchild = NULL;
		(*root)->rchild = NULL;
	} else if(data<(*root)->data)	creat(&((*root)->lchild),data);
	else if(data>=(*root)->data)	creat(&((*root)->rchild),data);
}
//打印二叉排序树，递增有序
void print(bitree root) {
          
   
	if(root!=NULL) {
          
   
		print(root->lchild);
		printf("%d ",root->data);
		print(root->rchild);
	}
}
//打印根节点到叶子节点的路径
void path(bitree root) {
          
   
	bitree p,q;
	int i,top=0;
	bitree s[max];
//	使用q保存刚遍历过的节点，初始为空
	q=NULL;
	p=root;
	while(p!=NULL||top!=0) {
          
   
		if(p!=NULL) {
          
   
			s[++top] = p;
			p=p->lchild;
		} else if(top>0) {
          
   
			p=s[top];
			if(p->rchild==NULL||p->rchild==q) {
          
   
//				如果p为叶子节点，则打印路径
				if(p->lchild==NULL&&p->rchild==NULL) {
          
   
					for(i=1; i<=top; i++)
						printf("%d ",s[i]->data);
					printf("
");
				}
//				使用q保存刚访问过的节点
				q=p;
				top--;
//				跳过刚才的左遍历，继续退栈
				p=NULL;
			}
//			否则遍历右子树
			else p=p->rchild;
		}

	}
}

void main() {
          
   
	bitree root=NULL;
	int ch;
	scanf("%d",&ch);
	while(ch!=999) {
          
   
		creat(&root,ch);
		scanf("%d",&ch);
	}
	printf("打印递增有序序列：
");
	print(root);
	printf("
打印根节点到叶子节点的路径：
");
	path(root);
}