初阶数据结构 遍历二叉树问题 （一）

一. 链式二叉树的实现

1. 结构体代码

typedef int BTdate;

typedef struct BinaryTree
{
	struct BinaryTree* left;
	struct BinaryTree* right;
	BTdate date;
}BT;

1
2
3
4
5
6
7
8
9

大概的图形是这样子

2. 增删查改

我们这里要明确的一点的 二叉树的增删查改是没有意义的

为什么呢？

我们来看下图

这颗二叉树的排列没有任何的规律 并且我们要插入也不知道往哪里插入

所以说 单纯的对二叉树curd操作是没有任何意义的

那么我们学习二叉树的意义在哪里呢？

这里就要引出我们后面的搜索二叉树 平衡二叉树 以及红黑二叉树

这些知识我们都会在后面的博客中学习到

二. 二叉树的遍历

1. 二叉树遍历的三种方式

前序遍历

前序遍历的大概解释： 先遍历根 再遍历左数 再遍历右数

还是一样 我们先来看图

如果我们要使用前面序遍历这个图

那么打印的顺序会是什么呢？

画图来看看

首先应该是先打印A

之后来看A的左子树 将根转换到B 打印B

之后来看B的左子树 打印D

之后看B的右子树 打印E

之后看E的右子树 打印H

之后看A的右子树 打印C

之后看C的左边子树 打印F

之后看C的右子树 打印G

中序遍历

中序遍历的大概解释 先遍历左子树 再遍历根 再遍历右子树

这里大家可以试着自己做一下

顺序肯定是

D B E H A FC G

这里其实只要将这个二叉树投影平面上就好

后序遍历

后序遍历的大概解释 先遍历左子树 再遍历根 再遍历右子树

这个大家可以自己试着做一做 这里就不过多赘述了

2. 二叉树遍历的递归实现

我们首先先自己实现如图的一个二叉树出来

要想自己实现一个二叉树其实也很简单

我们先设计一个BuyBTnode函数 用来创建二叉树的节点

之后给每一个节点赋上值 左右节点各自指向如图的位置就可以

代码表示如下

BTnode* BuyBTnode(BTdate x)
{
	BTnode* newnode = (BTnode*)malloc(sizeof(BTnode));
	// assert
	assert(newnode);

	// 赋值 
	newnode->left = newnode->right = NULL;
	newnode->date = x;

	//return
	return newnode;
}



void CreatNewBT()
{

	// 创建
	BTnode* nodeA = BuyBTnode('A');
	BTnode* nodeB = BuyBTnode('B');
	BTnode* nodeC = BuyBTnode('C');
	BTnode * nodeD = BuyBTnode('D');
	BTnode * nodeE = BuyBTnode('E');
	BTnode * nodeF = BuyBTnode('F');
	BTnode * nodeG = BuyBTnode('G');
	BTnode * nodeH = BuyBTnode('H');



	// 连接
	nodeA->left =  nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeB->right = nodeE;
	nodeE->right = nodeH;
	nodeC->left = nodeF;
	nodeC->right = nodeG;
}
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

接下来我们就开始写递归函数了

代码表示如下

BTnode* CreatNewBT()
{

	// 创建
	BTnode* nodeA = BuyBTnode('A');
	BTnode* nodeB = BuyBTnode('B');
	BTnode* nodeC = BuyBTnode('C');
	BTnode * nodeD = BuyBTnode('D');
	BTnode * nodeE = BuyBTnode('E');
	BTnode * nodeF = BuyBTnode('F');
	BTnode * nodeG = BuyBTnode('G');
	BTnode * nodeH = BuyBTnode('H');



	// 连接
	nodeA->left =  nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeB->right = nodeE;
	nodeE->right = nodeH;
	nodeC->left = nodeF;
	nodeC->right = nodeG;



	// return
	return nodeA;
}

void preorder(BTnode* root)
{
	// assert
	//assert(root);

	//main
	if (root==NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->date);
	preorder(root->left);
	preorder(root->right);

	// 这里大概解释下这个递归函数
	// 我们将preorder的功能定义为遍历整个树 
	// 如果说遍历为空的话 那就直接返回 
	// 如果说不为空的话 那就打印这个根 然后遍历它的左树 遍历完左树 遍历右树
}
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

我们可以发现 这里能够可以实现先序打印

那么我们试试看中序打印

（大家想想看 需要改变哪一行代码就可以实现中序打印）

void preorder(BTnode* root)
{
	// assert
	//assert(root);

	//main
	if (root==NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->date);
	preorder(root->left);
	preorder(root->right);

	// 这里大概解释下这个递归函数
	// 我们将preorder的功能定义为遍历整个树 
	// 如果说遍历为空的话 那就直接返回 
	// 如果说不为空的话 那就打印这个根 然后遍历它的左树 遍历完左树 遍历右树
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这个就需要我们理解每一行的功能

这一行代码的功能是实现遍历左子树

preorder(root->left);
1

这一行代码的功能是遍历右子树

preorder(root->right);
1

那么想要先遍历左子树 然后遍历根 然后遍历右子树 需要什么样的顺序呢？

没错 这样子的三行代码就可以了

	preorder(root->left);
	printf("%c ", root->date);
	preorder(root->right);
1
2
3

那么后序打印呢？

	preorder(root->left);
	preorder(root->right);
	printf("%c ", root->date);
1
2
3

很简单是吧

3 二叉树求节点个数

这里有两种实现方式

第一种我们可以传一个count的地址进去 然后再遍历内部结构 如果不是空值就加一

思路大概是这样子

我们来看看函数实现

void BTcount(BTnode* root, int* p)
{
	if (root == NULL)
	{
		return;
	}
	(*p)++;
	BTcount(root->left,p);
	BTcount(root->right,p);
}
1
2
3
4
5
6
7
8
9
10

这里还有另一种解法

我们使用递归实现

代码表示如下

int BTcount2(BTnode* root)
{
	return root == NULL ? 0 : BTcount2(root->left) + BTcount2(root->right)+1;
}
1
2
3
4

我们发现也是可以完美实现

以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏 希望大佬们看到错误之后能够

不吝赐教 在评论区或者私信指正 博主一定及时修正

那么大家下期再见咯