【数据结构】二叉树链式存储及遍历

二叉树链式存储及遍历

前言

本文章中的内容参考于王道数据结构考研书，如果你对该部分的内容的记忆有所模糊，可以阅读我的文章再加深印象

实现过程

1.定义二叉树结构体
2.初始化二叉树的根结点
3.实现二叉树链式存储的插入操作
4.实现二叉树的先序遍历、中序遍历、后序遍历

代码实现

• 定义二叉树链式存储的结构体

typedef struct BiTNode {
	int data; //数据域
	BiTNode* lchild;//左指针
	BiTNode* rchild;//右指针
}BiTNode,*BiTree;
1
2
3
4
5

• 初始化二叉树的根结点

void InitTree(BiTree &root)
{
	//创建一个根结点
	root = (BiTree)malloc(sizeof(BiTNode));
	//初始化根结点数据
	root->data = { 1 };
	root->lchild = NULL;
	root->rchild = NULL;
}
1
2
3
4
5
6
7
8
9

• 定义插入操作的函数，对插入操作的实习

void InsertNode(BiTree& root)
{
	BiTNode* p = (BiTNode*)malloc(sizeof(BiTNode));
	//将新创建的结点初始化
	p->data = { 2 };
	p->lchild = NULL;
	p->rchild = NULL;
	//将新结点变为root的左孩子
	root->lchild = p;
}
1
2
3
4
5
6
7
8
9
10

• 先序遍历

void PreOrder(BiTree root)
{
	if(root!=NULL)
	{
		visit(root);
		PreOrder(root->lchild);
		PreOrder(root->rchild);
	}
}
1
2
3
4
5
6
7
8
9

• 中序遍历

void InOrder(BiTree& root)
{
	if (root != NULL)
	{
		InOrder(root->lchild);
		visit(root);
		InOrder(root->rchild);
	}
}
1
2
3
4
5
6
7
8
9

• 后序遍历

void PostOrder(BiTree& root)
{
	if (root != NULL)
	{
		PostOrder(root->lchild);
		PostOrder(root->rchild);
		visit(root);
	}
}
1
2
3
4
5
6
7
8
9

• 对遍历visit函数的定义（这里遍历就直接将其打印即可）

void visit(BiTNode* node)
{
	printf("%d", node->data);
}
1
2
3
4

源代码

#define _CRT_SECURE_NO_WARNINGS
#include
#include

typedef struct BiTNode {
	int data;
	BiTNode* lchild;
	BiTNode* rchild;
}BiTNode,*BiTree;

void InitTree(BiTree &root)
{
	//创建一个根结点
	root = (BiTree)malloc(sizeof(BiTNode));
	//初始化根结点数据
	root->data = { 1 };
	root->lchild = NULL;
	root->rchild = NULL;
}

void InsertNode(BiTree& root)
{
	BiTNode* p = (BiTNode*)malloc(sizeof(BiTNode));
	//将新创建的结点初始化
	p->data = { 2 };
	p->lchild = NULL;
	p->rchild = NULL;
	//将新结点变为root的左孩子
	root->lchild = p;
}

void visit(BiTNode* node)
{
	printf("%d", node->data);
}

void PreOrder(BiTree root)
{
	if(root!=NULL)
	{
		visit(root);
		PreOrder(root->lchild);
		PreOrder(root->rchild);
	}
}

void InOrder(BiTree& root)
{
	if (root != NULL)
	{
		InOrder(root->lchild);
		visit(root);
		InOrder(root->rchild);
	}
}

void PostOrder(BiTree& root)
{
	if (root != NULL)
	{
		PostOrder(root->lchild);
		PostOrder(root->rchild);
		visit(root);
	}
}

int main()
{
	//定义一个空树
	BiTree root=NULL;
	//初始化根结点
	InitTree(root);
	//插入新结点
	InsertNode(root);
	//先序遍历
	PreOrder(root);
	//中序遍历
	InOrder(root);
	//后序遍历
	PostOrder(root);
	

	return 0;
}
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

总结

如果本篇文章对你有所帮助，那么可以给我点个关注，我们一起进步！