【数据结构 | 二叉树入门】

发布时间:2024年01月09日

二叉树概念:

如下图,是一个二叉树,二叉树是一种特殊的树。
在这里插入图片描述

二叉树特点:

  1. 二叉树的每个节点都最多有棵树,所以二叉树的中不存在度大于2的节点。
  2. 二叉树的左右子树是有顺序的,次序不可颠倒
    在这里插入图片描述
    如图,树1树2 就不是同一颗树。

二叉树的基本形态

二叉树具有以下五种基本形态:
(1)空二叉树
(2)只有一个根结点。
(3)根结点只有左子树
(4)根结点只有右子树
(5)根结点既有左子树又有右子树
在这里插入图片描述

特殊二叉树

满二叉树

在一棵二叉树中,如果所有分支结点都存在左子树和右子树并目所有叶子都在同
一层上,这样的二叉树称为满二叉树。

满二叉树:

在这里插入图片描述

完全二叉树

对于未满的<满二叉树> 并且从左到右连续的满二叉树称为完全二叉树。

在这里插入图片描述

以下均不是完全二叉树:
在这里插入图片描述

二叉树的存储结构

对于二叉树的存储一般采用链式存储

二叉树每个结点最多有两个孩子,所以为它设计一个数据域两个指针域是比较自然的想法,我们称这样的链表叫做二叉链表

在这里插入图片描述

在这里插入图片描述

二叉树的遍历

先序遍历

在这里插入图片描述

算法如下:

在这里插入图片描述

对于一般空的节点我们用N表示:
则这棵树的先序遍历为
在这里插入图片描述

//先序遍历
void PrevOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return 0;
	}
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

递归示意图如下:
在这里插入图片描述

中序遍历

在这里插入图片描述

算法如下:
在这里插入图片描述

则这棵树的中序遍历为
在这里插入图片描述

//中序遍历
void InOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return 0;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

后序遍历

在这里插入图片描述

算法如下

在这里插入图片描述
则这棵树的后序遍历:
在这里插入图片描述

代码:

//后序遍历
void PostOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return 0;
	}
	InOrder(root->left);
	InOrder(root->right);
	printf("%d ", root->data);
}

计算二叉树的节点个数

顾名思义,计算一颗树的节点个数,传入该树的跟节点,采用分治的思路:

在这里插入图片描述
在这里插入图片描述

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

在这里插入图片描述
在这里插入图片描述

计算叶子节点的个数

在这里插入图片描述

递归图如下:

在这里插入图片描述

采用分治的思想,从root开始递归,有叶子节点就返回1,这个二叉树一共三个叶子节点,所以有返回3次1,相加得3.

//叶子节点的个数
int TreeLeafSize(TreeNode* root)
{
	//空 返回0
	if (root == NULL)
	{
		return 0;
	}

	//不是空,是叶子,返回1
	if (root->left == NULL 
		&& root->right == NULL)
		return 1;

	//不是空,也不是叶子,   分治 == 左右子树叶子之和
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

在这里插入图片描述
在这里插入图片描述

树的高度

在这里插入图片描述

递归图如下:

在这里插入图片描述

采用分治的思想:分别计算左数高度右数高度,比较取最大。

代码如下:

//树的高度
int TreeHeight(TreeNode* root)
{
	if (root == NULL)
		return 0;
	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);

	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

在这里插入图片描述
在这里插入图片描述

求第k层节点个数

在这里插入图片描述

递归图如下:

在这里插入图片描述
还是采用分治思想,当k=1时,返回一个节点数。

代码如下:

//第k层个数
int TreeLevelK(TreeNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;

	return TreeLevelK(root->left, k - 1) + TreeLevelK(root->right, k - 1);
}

在这里插入图片描述
在这里插入图片描述

文章来源:https://blog.csdn.net/jokr_/article/details/135383228
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。