数据结构初阶 遍历二叉树问题(一)

一. 链式二叉树的实现

1. 结构体代码

typedef int BTDateType;
typedef struct BinaryTreeNode
{
	BTDateType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

大概的图形是这样子

2. 增删查改

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

为什么呢？

我们来看下图

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

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

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

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

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

二. 二叉树的遍历

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

前序遍历

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

还是一样 我们先来看图

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

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

画图来看看

打印的顺序如下： 

中序遍历

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

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

后序遍历

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

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

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

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

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

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

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

代码表示如下

//初始化
BTNode* BuyNode(BTDateType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}
//造树
BTNode* CreatTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	BTNode* node7 = BuyNode(7);
	
	//连接
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	node3->right = node7;

	return node1;
}

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

代码表示如下

//前序列
void PreOrder(BTNode* root)
{
	if(root==NULL)
	{
		printf("NULL");
		return;
	}

	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

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

那么我们试试看中序打印

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

//中序列
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

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

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

preorder(root->left);

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

preorder(root->right);

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

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

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

那么后序打印呢？

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

很简单是吧

3 二叉树求节点个数

这里有两种实现方式

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

思路大概是这样子

我们来看看函数实现

void  Treesize(BTNode* root, int* psize)
{
	if (root == NULL)
	{
		return;
	}
	++(*psize);
	Treesize(root->left, psize);
	Treesize(root->right, psize);
}

这里还有另一种解法

我们使用递归实现

代码表示如下

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

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

以上便是本文所有内容了，如有错误请各位大佬不吝赐教，感谢留言