实验要求

\1. 建立二叉树后，利用相应遍历算法求出该二叉树的高度并显示；

\2. 查找该树的叶子结点，从第一个叶子结点开始，将所有叶子结点输出。

\3. 采用非递归算法实现二叉树的先序和后序遍历。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<stdio.h>
#include<stdlib.h>

typedef struct BitNode{
	char data;
	BitNode *lchild,*rchild;
}bitnode,*bitree;

void CreatBitree(bitree *t) {
	char data;
	scanf("%c",&data);
	getchar();  //接收空字符 
	if(data=='0'){
		*t=NULL;
	}else{
		*t=(bitnode*)malloc(sizeof(bitnode));
		(*t)->data=data;
		printf("请输入%c的左子树:\n",data);
		CreatBitree(&(*t)->lchild);
		printf("请输入%c的右子树:\n",data);
		CreatBitree(&(*t)->rchild);
	}
}

//递归法遍历
void PreOrder(bitree t) {
	if(t){
		printf("%c",t->data);
		PreOrder(t->lchild);
		PreOrder(t->rchild);
	}
}

void InOrder(bitree t) {
	if(t){
		InOrder(t->lchild);
		printf("%c",t->data);
		InOrder(t->rchild);
	}
}

void BackOrder(bitree t) {  //左子树为空，访问右子树，右子树为空，再退回根节点 
	if(t){
		BackOrder(t->lchild);
		BackOrder(t->rchild);
		printf("%c",t->data);
	}
}

//非递归遍历
void Npreorder(bitree t){
	bitree stack[100];
	bitree s=t;
	int a=-1;
	printf("非递归先序遍历："); 
	while(a!=-1||s!=NULL){
		while(s!=NULL){
			a++;
			stack[a]=s;
			printf("%c",s->data);
			s=s->lchild;
		}
		s=stack[a];
		a--;
		s=s->rchild;
	}
	printf("\n"); 
} 

void Ninorder(bitree t){
	bitree stack[100];
	bitree s=t;
	int a=-1;
	printf("非递归中序遍历："); 
	while(a!=-1||s!=NULL){
		while(s!=NULL){
			a++;
			stack[a]=s;
			s=s->lchild;
		}
		s=stack[a];
		printf("%c",s->data);
		a--;
		s=s->rchild;
	}
} 




int main(){
	bitree t=NULL;
	printf("请输入树根（若为空，请输入'0'）:\n");
	CreatBitree(&t);  //创建二叉树
	printf("递归先序遍历：");
	PreOrder(t);
	printf("\n");
	printf("递归中序遍历：");
	InOrder(t);
	printf("\n"); 
	printf("递归后序遍历：");
	BackOrder(t);
	printf("\n"); 
	//非递归 
	Npreorder(t);
	Ninorder(t);
}