C语言二叉树的建立和遍历

tree.h

typedef struct TreeNode_s {
	char val;//数据域
	struct TreeNode_s *pLeft;//左结点
	struct TreeNode_s *pRight;//右边结点
} TreeNode_t, *pTreeNode_t;

//辅助队列建立二叉树
typedef struct QueueNode_s {
	pTreeNode_t NodeAddr; //数据域存储一个二叉树结点的地址 
	struct QueueNode_s *pNext;
} QueueNode_t, *pQueueNode_t;

void preOrder(pTreeNode_t pRoot);
void inOrder(pTreeNode_t pRoot);
void postOrder(pTreeNode_t pRoot);
void buildBinaryTree(pTreeNode_t *ppRoot, pQueueNode_t *ppQueueFront, pQueueNode_t *ppQueueRear, char val);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

main.c

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
#include "tree.h"
#define N 10
int main() {
	
    //char c[] = "ABCDEFGHIJ";
	//pTreeNode_t arr[N] = { NULL };//索引数组
	//for (int i = 0; i < N; ++i) {
	//	arr[i] = (pTreeNode_t)calloc(1, sizeof(TreeNode_t));
	//	arr[i]->val = c[i];
	//}
	//pTreeNode_t pRoot = arr[0];
	//for (int i = 0, j = 1; j < N; ++j) {
	//	if (arr[i]->pLeft == NULL) {
	//		arr[i]->pLeft = arr[j];
	//	}
	//	else {
	//		arr[i]->pRight = arr[j];
	//		++i;
	//	}
	//}
    
	pTreeNode_t pRoot = NULL;
	pQueueNode_t pQueueFront = NULL;
	pQueueNode_t pQueueRear = NULL;
	char val;
	while (scanf("%c", &val) != EOF) {
		if (val == '\n') {
			break;
		}
		buildBinaryTree(&pRoot, &pQueueFront, &pQueueRear, val);
	}
	preOrder(pRoot);
	printf("\n");
	inOrder(pRoot);
	printf("\n");
	postOrder(pRoot);
	printf("\n");
}

//三种树的遍历方式
void preOrder(pTreeNode_t pRoot) {
	if (pRoot) {
		printf("%c", pRoot->val);
		preOrder(pRoot->pLeft);
		preOrder(pRoot->pRight);
	}
}
void inOrder(pTreeNode_t pRoot) {
	if (pRoot) {
		inOrder(pRoot->pLeft);
		printf("%c", pRoot->val);
		inOrder(pRoot->pRight);
	}
}
void postOrder(pTreeNode_t pRoot) {
	if (pRoot) {
		postOrder(pRoot->pLeft);
		postOrder(pRoot->pRight);
		printf("%c", pRoot->val);
	}
}

//利用辅助队列层次建立二叉树
void buildBinaryTree(pTreeNode_t *ppRoot, pQueueNode_t *ppQueueFront, pQueueNode_t *ppQueueRear, char val) {
	pTreeNode_t pTreeNode = (pTreeNode_t)calloc(1, sizeof(TreeNode_t));
	pTreeNode->val = val;
	pQueueNode_t pQueueNode = (pQueueNode_t)calloc(1, sizeof(QueueNode_t));
	pQueueNode->NodeAddr = pTreeNode;
	if (*ppRoot == NULL) {//给二叉树和队列插入第一个结点
		*ppRoot = pTreeNode;
		*ppQueueFront = pQueueNode;
		*ppQueueRear = pQueueNode;
	}
	else {
		//用尾插法入队
		(*ppQueueRear)->pNext = pQueueNode;
		*ppQueueRear = pQueueNode;
		pQueueNode_t pQueueCur = *ppQueueFront;//队首
		if (pQueueCur->NodeAddr->pLeft == NULL) {
			//把新结点插入到队首所指的二叉树结点的左孩子
			pQueueCur->NodeAddr->pLeft = pTreeNode;
		}
		else {
			pQueueCur->NodeAddr->pRight = pTreeNode;
			//放好右孩子之后，要出队
			*ppQueueFront = pQueueCur->pNext;
			free(pQueueCur);
			pQueueCur = NULL;
		}
	}
}
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