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

一. 链式二叉树的实现

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

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

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

最近更新

  1. 什么是 MLPerf?

    2024-07-10 23:54:04       0 阅读
  2. Docker

    2024-07-10 23:54:04       0 阅读
  3. 代码改进,模型优化,强化深度学习

    2024-07-10 23:54:04       0 阅读
  4. python 基础知识点(一)

    2024-07-10 23:54:04       0 阅读
  5. Python利用psutil库进行监控进程和资源

    2024-07-10 23:54:04       0 阅读
  6. SpringBoot RestHighLevelClient 按版本更新

    2024-07-10 23:54:04       0 阅读
  7. 跨域问题几种解决方法

    2024-07-10 23:54:04       0 阅读
  8. Python面试整理-文件处理

    2024-07-10 23:54:04       0 阅读
  9. 分式

    2024-07-10 23:54:04       0 阅读

热门阅读

  1. yolov5中训练长条型目标召回率低问题

    2024-07-10 23:54:04       8 阅读
  2. openssl error:0A000126:SSL routines:ssl3_read_n:unexpected eof

    2024-07-10 23:54:04       9 阅读
  3. 各种软件启动方式

    2024-07-10 23:54:04       6 阅读
  4. 【创作纪念日】我的三周年创作纪念日

    2024-07-10 23:54:04       7 阅读
  5. Github 2024-07-07 开源项目日报 Top10

    2024-07-10 23:54:04       8 阅读
  6. 部署LVS-DR群集

    2024-07-10 23:54:04       5 阅读
  7. python的列表推导式

    2024-07-10 23:54:04       8 阅读