前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >二叉树

二叉树

作者头像
code-child
发布2023-05-30 11:25:43
2070
发布2023-05-30 11:25:43
举报
文章被收录于专栏:codechild

什么是树

树是一种非线性结构。树有一个特殊的节点,叫做根节点。根节点是一个树的起点,除根节点外,它下面的节点被分为很多的分支。以每个分支节点为起点又可以构成一个树,称为子树。由根节点及子树构成的结构称为树

树的相关概念

节点的度:该节点直接相连了几个节点,就是几度。 叶子节点:度为0的节点 分支节点:度不为0的节点 父亲节点:该节点有连接下一层的节点 ,该节点即为父节点 子节点:父节点连的节点为子节点 兄弟节点:有共同父节点的节点,互称为兄弟节点。 树的度:节点中度最大的,就是树的度。 节点的层次:如果定义根节点为第 1层,那么根的子节点为第二层,依次类推。 树的的高度(深度):节点的最大层数为树的深度。 堂兄弟节点:处于同一层的节点。 节点的祖先:从根到该节点所经分支的全部节点。 子孙:以某节点为根的子树中任意一个节点都称为该节点的子孙 森林:多颗树构成的集合称为森林。

什么是二叉树

一个二叉树是节点的集合,该集合可以为空,也可以由根节点连接左右子树构成。 二叉树的特点: 1.每个节点的度最大为2。 2.二叉树有左右子树,因此是有序的,左右不能颠倒

特殊的二叉树

满二叉树:每一层的节点数都达到最大。 完全二叉树:除最后一层外,每一层的节点数都达到最大,且最后一层的节点都位于左部。

二叉树的性质

若根节点为第一层,那么二叉树的第i层最多有2(i-1)个节点,总节点数最多有2h-1。 对于任意一个二叉树,如果度为0的节点有n0,那么度为2的节点n2=n0-1。 对一个完全二叉树进行编号,编号的规则:自上而下,自左而右。 那么,第i个节点对应的左节点为2i+1,右节点为2i+2,对应的父节点为(i-1)/2。

链式二叉树

二叉树类型的创建

代码语言:javascript
复制
ctypedef int BTDataType;

typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;

二叉树的遍历

前序遍历:

先访问根节点,再访问左子树,最后访问右子树;每个子树又可以分为根,左树,右树。不断的递归,直到每个子树的根为空。

代码语言:javascript
复制
cvoid BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
		
	printf("%d ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);

}

中序遍历:

先访问左子树,再访问根节点,最后访问右子树

代码语言:javascript
复制
cvoid BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	BinaryTreeInOrder(root->left);
	printf("%d ", root->data);
	
	BinaryTreeInOrder(root->right);
	
	
}

后序遍历:

先访问右子树,再访问左子树,最后访问根节点

代码语言:javascript
复制
cvoid BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%d ", root->data);
}

二叉树节点的个数

先访问根,不为空就加1,然后访问左右子树。为空就返回0

代码语言:javascript
复制
cint BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	else
		return 1+ BinaryTreeSize(root->left)+ BinaryTreeSize(root->right);

}

查找数据为X的节点

先查找根节点,然后再分别查找左右子树,当为空的时候返回空,当节点的数据为x时,则返回该节点的地址。然后把左右子树按上面的方式继续查找。

代码语言:javascript
复制
cBTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{

	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* ret1=BinaryTreeFind(root->left,x);

	if (ret1)
		return ret1;

	BTNode* ret2 = BinaryTreeFind(root->right, x);

	if (ret2)
		return ret2;

	return NULL;
}

查找叶子节点的个数

出度为0的节点为叶子节点,那我们就查找左右孩子为空的节点。

代码语言:javascript
复制
cint BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	if (root->left == NULL && root->right == NULL)
		return 1;

	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

第k层节点的个数

我们把根看成第k层,那么实际上的第k层就是第一层。 如果节点为空就返回0,如果k为1就是到了第k层了,返回1。 上述是归的条件。递就是按这个逻辑继续查找左,右子树。

代码语言:javascript
复制
cint BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

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

}

二叉树的高度

要求树的高度就是求路径最大的。 我们可以先比较左右子树的高度,然后最大的子树的高度加1就是树的高度。这个就是不断递归的过程。

代码语言:javascript
复制
cint TreeDepth(BTNode* root)
{
	if (root == NULL)
		return 0;

	int ret1 = TreeDepth(root->left);
	int ret2 = TreeDepth(root->right);

	if (ret1 > ret2)
		return ret1+1;
	else
		return ret2+1;

}

二叉树的层序遍历

用一个队列储存节点,当一个节点出队时,它的孩子节点入队。这样就实现了层序遍历。

代码语言:javascript
复制
cvoid BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* cur = QueueFront(&q);
		QueuePop(&q);
		if (cur == NULL)
			printf("# ");
		else
		{
			printf("%d ", cur->data);
			QueuePush(&q, cur->left);
			QueuePush(&q, cur->right);
		}
	}
	QueueDestroy(&q);
	printf("\n");
}

判断二叉树是不是完全二叉树

按照层序遍历,如果是完全二叉树,当出队列的节点为空的时候,后面所有的节点都是空,反之不是完全二叉树。

代码语言:javascript
复制
cbool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* cur = QueueFront(&q);
		QueuePop(&q);
		if (cur == NULL)
			break;
		else
		{
			QueuePush(&q, cur->left);
			QueuePush(&q, cur->right);
		}
	}
	while (!QueueEmpty(&q))
	{
		BTNode* cur = QueueFront(&q);
		QueuePop(&q);
		if (cur != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}

	QueueDestroy(&q);
	return true;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2023-05-26,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 什么是树
    • 树的相关概念
    • 什么是二叉树
      • 特殊的二叉树
      • 二叉树的性质
      • 链式二叉树
        • 二叉树类型的创建
          • 二叉树的遍历
            • 前序遍历:
            • 中序遍历:
            • 后序遍历:
          • 二叉树节点的个数
            • 查找数据为X的节点
              • 查找叶子节点的个数
                • 第k层节点的个数
                  • 二叉树的高度
                    • 二叉树的层序遍历
                      • 判断二叉树是不是完全二叉树
                      领券
                      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档