二叉树链式结构的遍历访问——前中后序

最开始接触树的时候，因为并不是二叉树，所以我们并不知道一个节点最多有几个度，所以我们要用链表来实现树的话就需要用孩子兄弟法

然后我们认识了完全二叉树，因为它是从左到右都满的二叉树，所以我们可以用顺序表（数组）来存储

但是如果不是完全二叉树的话，用顺序表储存的话就不好，那么又因为他是二叉树了，一个节点做多只有两个度，所以可以用一个结构体（里面包含两个结构体指针，和储存在节点的数）来表示二叉树中的每个节点

上述代码并不是创建二叉树的方式，现在我们只是手动弄出一个二叉树，方便之后对他结构实现的运用
我们可以把二叉树的每一个子，够看成有，根左子树，右子树。所以二叉树的遍历是递归的

现在我们用代码来实现这三中二叉树的遍历（递归）
前序遍历：

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->val);
	PreOrder(root->left);
	PreOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12

同样的原理——中序遍历：

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11

同样的原理——后序遍历：

void PostOrder(BTNode* root)
{

	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);

}
1
2
3
4
5
6
7
8
9
10
11
12
13

前
中
后
打印的结果：

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType val;
}BTNode;


BTNode* BuyNode(BTDataType x)//为每个节点开辟空间
{
	BTNode* tmp = (BTNode*)malloc(sizeof(BTNode));
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	tmp->left = tmp->right = NULL;
	tmp->val = x;
}

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->val);
	PreOrder(root->left);
	PreOrder(root->right);
}
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}

void PostOrder(BTNode* root)
{

	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);

}
int main()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

	node1->left = node2;
	node2->left = node3;
	node1->right = node4;
	node4->left = node5;
	node4->right = node6;

	// 二叉树前序遍历
	PreOrder(node1);
	// 二叉树中序遍历
	printf("\n");
	InOrder(node1);
	printf("\n");

	// 二叉树后序遍历
	 PostOrder(node1);

}
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

前中后序遍历的OJ题
前序：

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

这里不仅是要前序遍历，还要把遍历的值存储到数组中，返回去打印

所以我们首先要自己创建一个动态变量数组
但是开多少空间呢？——所以我们还需要写一个函数来把树的节点个数算出来

开辟：

有了数组之后我们就要前序遍历树，在把每次遍历到的值都存入到数组a中

代码：

int TreeSize(struct TreeNode* root)
 {
     return root==NULL?0: TreeSize(root->left)+ TreeSize(root->right)+1;
 }

   void preorder(struct TreeNode* root,int* a,int* pi)
    {
        if(root==NULL)
        {
            return;
        }
        a[(*pi)++]=root->val;
        preorder(root->left,a,pi);
        preorder(root->right,a,pi);
    }
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    int n=TreeSize(root);
    int*a=(int*)malloc(sizeof(int)*n);
    int i=0;
    preorder(root,a,&i);
    *returnSize=n;
    return a;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

中后的代码和思路基本和这个一样的，只需要改变遍历的顺序就行

//中：
preorder(root->left,a,pi);
        a[(*pi)++]=root->val;
        preorder(root->right,a,pi);
//后：
preorder(root->left,a,pi);
        preorder(root->right,a,pi);
        a[(*pi)++]=root->val;
1
2
3
4
5
6
7
8