拿捏数据结构- 链式二叉树

链式二叉树的概念:

链式二叉树解决的是非完全二叉树解决不了的问题

什么意思呢,简单的说就是,链式二叉树

可以是下面三种二叉树

但是非链式二叉树只能是前两种

链式二叉树的存储

节点结构:首先定义一个结构体或类来表示二叉树的节点。每个节点通常包含三个部分:

  • 存储数据的成员变量(例如,_data)。
  • 指向其左子节点的指针(例如,_left)。
  • 指向其右子节点的指针(例如,_right)。

链式二叉树的存储方式提供了很高的灵活性,可以轻松地添加和删除节点,同时也使得树结构的实现更加直观和易于操作。

前序/中序/后序遍历

讲解链式二叉树之前我们需要先了解一下,前序/中序/后序,因为在初阶数据结构里,链式二叉树我们是用递归的方式来实现的,非递归的方式,在后续篇章会进行讲解。

这里我们上图,假设是这一张图

前序遍历

前序遍历的顺序是:首先访问根节点,然后递归地进行左子树的前序遍历,最后递归地进行右子树的前序遍历。

遍历顺序:根-左-右

步骤

  1. 访问当前节点。
  2. 遍历左子树。
  3. 遍历右子树。

示例: 假设有如下的二叉树:

关于前序遍历,我们需要把空节点也看出来

如图

所以根据遍历顺便,我们应该是

1  2  3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL

中序遍历

中序遍历的顺序是:首先递归地进行左子树的中序遍历,然后访问根节点,最后递归地进行右子树的中序遍历。

遍历顺序:左-根-右

步骤

  1. 遍历左子树。
  2. 访问当前节点。
  3. 遍历右子树。

正确的是

后序遍历

后序遍历的顺序是:首先递归地进行左子树的后序遍历,然后递归地进行右子树的后序遍历,最后访问根节点。

遍历顺序:左-右-根

步骤

  1. 遍历左子树。
  2. 遍历右子树。
  3. 访问当前节点。

正确的是

总结

链式二叉树的实现

创建文件

定义链式二叉树结构

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

解释:

  1. typedef int BTDataType; 这行代码使用 typedef 关键字定义了一个新的别名 BTDataType,它是 int 类型的别名。这意味着在代码中,你可以使用 BTDataType 作为 int 类型数据的一个更有意义的别名。

  2. typedef struct BinaryTreeNode 这行代码开始定义一个名为 BinaryTreeNode 的新结构体类型。struct BinaryTreeNode 是结构体的名称,它将用于表示二叉树中的节点。

  3. BTDataType _data; struct BinaryTreeNode* _left; struct BinaryTreeNode* _right; } 这个大括号内的代码定义了 BinaryTreeNode 结构体的具体内容:

    • BTDataType _data; 定义了一个名为 _data 的成员变量,它用于存储节点中的数据。由于使用了之前定义的 BTDataType,所以这个成员变量是 int 类型的。
    • struct BinaryTreeNode* _left; 定义了一个名为 _left 的成员变量,它是一个指向 BinaryTreeNode 类型的指针,用于指向当前节点的左子节点。
    • struct BinaryTreeNode* _right; 定义了一个名为 _right 的成员变量,它也是一个指向 BinaryTreeNode 类型的指针,用于指向当前节点的右子节点。
  4. BTNode; 这行代码为 BinaryTreeNode 结构体定义了一个易记的别名 BTNode。这样,在代码中就可以使用 BTNode 来声明二叉树的节点。

总结来说,这段代码定义了一个用于表示链式二叉树节点的结构体 BTNode,其中包含一个整型数据 _data 和两个指向相同结构体类型的指针 _left_right,分别用于存储节点的数据和链接到左右子节点。通过这种定义,可以方便地创建和管理二叉树数据结构。

二叉树的初始化

//二叉树的初始化
BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("BinaryTreeInit:newnode:");
		exit(1);
	}
	newnode->_data = x;
	newnode->_left = NULL;
	newnode->_right = NULL;
	return newnode;
}

解释:

  1. BTNode* BuyNode(BTDataType x)

    • 这是函数的声明行,定义了一个名为 BuyNode 的函数,它接收一个类型为 BTDataType(之前定义的 int 类型别名)的参数 x,并返回一个指向 BTNode 类型的指针。
  2. BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));

    • 这行代码使用 malloc 函数为新的二叉树节点分配内存。sizeof(BTNode) 计算 BTNode 类型的大小,确保分配足够的内存。分配成功后,newnode 指针将指向这块新分配的内存。
  3. if (newnode == NULL)

    • 这行代码检查 malloc 是否成功分配了内存。如果 newnode 为 NULL,表示内存分配失败。
  4. perror("BinaryTreeInit:newnode:");

    • 如果内存分配失败,使用 perror 函数输出错误信息到标准错误。"BinaryTreeInit:newnode:" 是自定义的错误前缀,后跟系统定义的错误信息。
  5. exit(1);

    • 紧接着,使用 exit 函数以状态码 1 退出程序。状态码 1 通常表示程序因错误而终止。
  6. newnode->_data = x;

    • 如果内存分配成功,这行代码将参数 x 的值赋给新节点的 _data 成员变量,从而初始化节点存储的数据。
  7. newnode->_left = NULL;

    • 这行代码将新节点的 _left 指针设置为 NULL,表示当前没有左子节点。
  8. newnode->_right = NULL;

    • 类似地,这行代码将新节点的 _right 指针设置为 NULL,表示当前没有右子节点。
  9. return newnode;

    • 最后,函数返回指向新创建并初始化的 BTNode 节点的指针。

总结来说,BuyNode 函数负责创建一个新的二叉树节点,初始化其数据和子节点指针,如果内存分配失败,则输出错误信息并终止程序。这个函数是构建二叉树时用于生成节点的基本工具。

这里的关键点是认识到 ,左右节点的存在

二叉树的销毁

这里就采取了递归,开始上难度了,这里我先不做讲解,模拟创建二叉树之后我们进行讲解递归

// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeDestory(root->_left);
	BinaryTreeDestory(root->_right);
	free(root);
}

解释:

  1. void BinaryTreeDestory(BTNode* root)

    • 这是函数的声明行,定义了一个名为 BinaryTreeDestory 的函数,它接收一个指向 BTNode 类型的指针 root 作为参数。该函数没有返回值(void 类型)。
  2. if (root == NULL)

    • 这行代码检查传入的 root 指针是否为 NULL。如果是 NULL,表示二叉树为空或已经被销毁,因此函数直接返回。
  3. BinaryTreeDestory(root->_left);

    • 如果 root 不是 NULL,这行代码首先递归调用 BinaryTreeDestory 函数,传入当前节点的左子节点 root->_left 作为参数。这样做会先销毁左子树。
  4. BinaryTreeDestory(root->_right);

    • 接着,这行代码递归调用 BinaryTreeDestory 函数,传入当前节点的右子节点 root->_right 作为参数。这会销毁右子树。
  5. free(root);

    • 在左子树和右子树都被销毁之后,这行代码使用 free 函数释放当前节点 root 所占用的内存。

总结来说,BinaryTreeDestory 函数通过递归的方式,先销毁二叉树的左子树和右子树,然后释放根节点的内存。这种销毁方式确保了二叉树中的所有节点都会被释放,避免了内存泄漏。需要注意的是,在使用这种销毁方式时,确保在销毁二叉树后不再使用任何指向该树的指针,因为整个树的内存已经被释放。

模拟简易链式二叉树

//构建二叉树
void teer()
{
	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;
	node2->_left = node3;
	node1->_right = node4;
	node4->_left = node5;
	node4->_right = node6;
	//node2->_right = node7;

	
}
int main()
{
	//构建二叉树
	teer();
	return 0;
}

这里我们模拟实现一个二叉树

就是这样

前序遍历实现

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}

解释:

  1. void BinaryTreePrevOrder(BTNode* root)

    • 这是函数的声明行,定义了一个名为 BinaryTreePrevOrder 的函数,它接收一个指向 BTNode 类型的指针 root 作为参数。该函数没有返回值(void 类型)。
  2. if (root == NULL)

    • 这行代码检查传入的 root 指针是否为 NULL。如果是 NULL,表示当前节点为空,不需要遍历。
  3. printf("NULL ");

    • 如果当前节点为空,打印字符串 "NULL " 到标准输出。这是一种表示空节点的常见做法,但在实际应用中,通常会省略这一步,或者用其他方式处理空节点。
  4. printf("%d ", root->_data);

    • 如果当前节点不为空,这行代码会打印当前节点的 _data 成员变量的值。%d 是格式化输出的占位符,表示后面跟着的参数是一个整数。
  5. BinaryTreePrevOrder(root->_left);

    • 这行代码递归调用 BinaryTreePrevOrder 函数,传入当前节点的左子节点 root->_left 作为参数。这将执行左子树的前序遍历。
  6. BinaryTreePrevOrder(root->_right);

    • 最后,这行代码递归调用 BinaryTreePrevOrder 函数,传入当前节点的右子节点 root->_right 作为参数。这将执行右子树的前序遍历。

总结来说,BinaryTreePrevOrder 函数通过递归的方式实现了二叉树的前序遍历。它首先打印当前节点的值,然后递归地遍历左子树,最后递归地遍历右子树。这种遍历方式在树的遍历、搜索、复制等操作中非常有用。

图解:

  

中序遍历实现

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreeInOrder(root->_left);
	printf("%d ", root->_data);
	BinaryTreeInOrder(root->_right);
}

解释:

  1. void BinaryTreeInOrder(BTNode* root)

    • 这是函数的声明行,定义了一个名为 BinaryTreeInOrder 的函数,它接收一个指向 BTNode 类型的指针 root 作为参数。该函数没有返回值(void 类型)。
  2. if (root == NULL)

    • 这行代码检查传入的 root 指针是否为 NULL。如果是 NULL,表示当前节点为空,不需要遍历。
  3. printf("NULL ");

    • 如果当前节点为空,打印字符串 "NULL " 到标准输出。这通常用于表示空节点,但在实际的中序遍历中,通常会忽略空节点而不是打印它们。
  4. BinaryTreeInOrder(root->_left);

    • 这行代码递归调用 BinaryTreeInOrder 函数,传入当前节点的左子节点 root->_left 作为参数。这将执行左子树的中序遍历。
  5. printf("%d ", root->_data);

    • 在左子树遍历之后,这行代码打印当前节点的 _data 成员变量的值。因为在左子树遍历之后访问根节点,所以对于二叉搜索树来说,这会保证按升序打印节点值。
  6. BinaryTreeInOrder(root->_right);

    • 最后,这行代码递归调用 BinaryTreeInOrder 函数,传入当前节点的右子节点 root->_right 作为参数。这将执行右子树的中序遍历。

后序遍历实现

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%d ", root->_data);
}

解释:

  1. void BinaryTreePostOrder(BTNode* root)

    • 这是函数的声明行,定义了一个名为 BinaryTreePostOrder 的函数,它接收一个指向 BTNode 类型的指针 root 作为参数。该函数没有返回值(void 类型)。
  2. if (root == NULL)

    • 这行代码检查传入的 root 指针是否为 NULL。如果是 NULL,表示当前节点为空,不需要遍历。
  3. printf("NULL ");

    • 如果当前节点为空,打印字符串 "NULL " 到标准输出。这通常用于表示空节点,但在实际的后序遍历中,通常会忽略空节点而不是打印它们。
  4. BinaryTreePostOrder(root->_left);

    • 这行代码递归调用 BinaryTreePostOrder 函数,传入当前节点的左子节点 root->_left 作为参数。这将执行左子树的后序遍历。
  5. BinaryTreePostOrder(root->_right);

    • 在左子树遍历之后,这行代码递归调用 BinaryTreePostOrder 函数,传入当前节点的右子节点 root->_right 作为参数。这将执行右子树的后序遍历。
  6. printf("%d ", root->_data);

    • 在左子树和右子树都遍历之后,这行代码打印当前节点的 _data 成员变量的值。因为这是在访问完左右子树之后的操作,所以它是后序遍历的一部分。

二叉树节点个数

什么是节点个数,也就是,全部节点个数

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

解释:

  1. int BinaryTreeSize(BTNode* root)

    • 这是函数的声明行,定义了一个名为 BinaryTreeSize 的函数,它接收一个指向 BTNode 类型的指针 root 作为参数。函数返回一个整数值,表示树中的节点总数。
  2. if (root == NULL)

    • 这行代码检查传入的 root 指针是否为 NULL。如果是 NULL,表示当前节点为空,不计入节点总数。
  3. return 0;

    • 如果当前节点为空,函数返回 0。这是递归的基本情况,表示空树的节点数为 0
  4. return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;

    • 如果当前节点不为空,这行代码递归调用自身两次:一次计算左子树的节点数 BinaryTreeSize(root->_left),一次计算右子树的节点数 BinaryTreeSize(root->_right)。然后将这两个调用的结果相加,并加上 1 来表示当前节点本身。这样,你就得到了整棵树的节点总数。

图解

二叉树叶子节点个数

什么是叶子结点个数

也就是:

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (BinaryTreeLeafSize(root->_left) == 0 && BinaryTreeLeafSize(root->_right) == 0)
		return 1;
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

解释:

  1. int BinaryTreeLeafSize(BTNode* root)

    • 这是函数的声明行,定义了一个名为 BinaryTreeLeafSize 的函数,接收一个指向 BTNode 类型的指针 root 作为参数。函数返回一个整数值,表示树中叶子节点的总数。
  2. if (root == NULL)

    • 这行代码检查传入的 root 指针是否为 NULL。如果是 NULL,表示当前节点为空,不计入叶子节点的总数。
  3. return 0;

    • 如果当前节点为空,函数返回 0。这是递归的基本情况之一,表示空树的叶子节点数为 0
  4. if (BinaryTreeLeafSize(root->_left) == 0 && BinaryTreeLeafSize(root->_right) == 0)

    • 这行代码是一个条件语句,用于检查当前节点的左子节点和右子节点是否都为空。如果两者都为空,那么当前节点就是一个叶子节点。
  5. return 1;

    • 如果当前节点是叶子节点,即它的左右子节点都为空,那么返回 1,表示叶子节点数为 1
  6. return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);

    • 如果当前节点不是叶子节点,这行代码递归调用自身两次:一次计算左子树的叶子节点数 BinaryTreeLeafSize(root->_left),一次计算右子树的叶子节点数 BinaryTreeLeafSize(root->_right)。然后将这两个调用的结果相加,得到当前子树的叶子节点总数。

总结来说,BinaryTreeLeafSize 函数通过递归的方式遍历二叉树,计算叶子节点的个数。它首先检查当前节点是否为空,如果不是空,再检查当前节点是否为叶子节点(左右子节点都为空),如果是叶子节点则计数 1,否则递归地计算左右子树的叶子节点数并相加。这种方法可以正确地计算出任意二叉树的叶子节点总数。

图解

二叉树高度

高度也就是二叉树的层数

// 二叉树高度
int BinaryTreeHeight(BTNode* root)
{ 
	if (root == NULL)
	{
		return 0;
	}
	int heightleft = BinaryTreeHeight(root->_left);
	int heightright = BinaryTreeHeight(root->_right);
	return heightleft >= heightright ? heightleft + 1 : heightright + 1;
}

这里的关键是理解如何递归地计算左子树和右子树的高度。

  1. int heightleft = BinaryTreeHeight(root->_left);

    • 这行代码是对 BinaryTreeHeight 函数的递归调用,目的是计算当前节点的左子树的高度。root->_left 是对当前节点左子节点的引用,如果左子节点存在,就对它调用 BinaryTreeHeight 函数,否则返回 0(如果左子节点为空)。
  2. int heightright = BinaryTreeHeight(root->_right);

    • 类似于上面的调用,这行代码计算当前节点的右子树的高度。root->_right 是对当前节点右子节点的引用,同样地,如果右子节点存在,就对它调用 BinaryTreeHeight 函数,否则返回 0(如果右子节点为空)。

这里的关键点在于    

int heightleft = BinaryTreeHeight(root->_left);
int heightright = BinaryTreeHeight(root->_right);

这两行代码是递归过程中的关键步骤,它们分别独立地计算左子树和右子树的高度。由于树的高度是递归定义的,即树的高度是其左子树和右子树高度的最大值加 1(当前节点),所以需要分别计算左右子树的高度。

一旦得到 heightleftheightright,函数就会决定:

  • 如果 heightleft 大于或等于 heightright,则当前节点的左子树高度是决定整棵树高度的关键,因此返回 heightleft + 1
  • 如果 heightright 大于 heightleft,则右子树的高度决定了整棵树的高度,因此返回 heightright + 1

这种递归方法确保了能够找到从根节点到任意叶子节点的最长路径,从而得到二叉树的准确高度。

否则会产生栈溢出的现象

下面有一题题解,我们会进行图解,因为一样,所以这里不进行图解,

先上图

二叉树查找值为x的节点

这里还是有点难度的

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->_data == x)
		return root;

	
	BTNode* ret1 = BinaryTreeFind(root->_left, x);
	if (ret1 != NULL)
	{
		return ret1;
	}
	BTNode* ret2 = BinaryTreeFind(root->_right, x);
	if (ret2 != NULL)
	{
		return ret2;
	}
	return NULL;

}

解释:

  1. BTNode* BinaryTreeFind(BTNode* root, BTDataType x)

    • 这是函数的声明行,定义了一个名为 BinaryTreeFind 的函数。它接收两个参数:一个指向 BTNode 类型的指针 root,表示二叉树的根节点;一个 BTDataType 类型的值 x,表示要查找的值。函数返回一个指向 BTNode 类型的指针,如果找到匹配的节点,则返回该节点的地址;如果没有找到,则返回 NULL
  2. if (root == NULL)

    • 这行代码检查传入的 root 指针是否为 NULL。如果是 NULL,表示当前节点为空,无法找到匹配的值,因此返回 NULL
  3. if (root->_data == x)

    • 如果当前节点不为空,这行代码比较当前节点的 _data 成员变量与给定值 x 是否相等。
  4. return root;

    • 如果找到匹配的值,即当前节点的 _data 等于 x,则返回当前节点的指针。
  5. BTNode* ret1 = BinaryTreeFind(root->_left, x);

    • 如果当前节点的值不匹配,这行代码递归调用 BinaryTreeFind 函数,搜索左子树。递归调用的结果(一个节点指针)被存储在 ret1 变量中。
  6. if (ret1 != NULL)

    • 接着,检查 ret1 是否不为空。如果不为空,表示在左子树中找到了匹配的节点,因此返回 ret1
  7. BTNode* ret2 = BinaryTreeFind(root->_right, x);

    • 如果左子树中没有找到匹配的节点,这行代码递归调用 BinaryTreeFind 函数,搜索右子树。递归调用的结果(一个节点指针)被存储在 ret2 变量中。
  8. if (ret2 != NULL)

    • 然后,检查 ret2 是否不为空。如果不为空,表示在右子树中找到了匹配的节点,因此返回 ret2
  9. return NULL;

    • 如果在当前节点的左子树和右子树中都没有找到匹配的节点,则返回 NULL

图解

二叉树第k层节点个数

// 二叉树第k层节点个数
int 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. int BinaryTreeLevelKSize(BTNode* root, int k)

    • 这是函数的声明行,定义了一个名为 BinaryTreeLevelKSize 的函数。它接收两个参数:一个指向 BTNode 类型的指针 root,表示当前的节点(可以是任意层的节点,包括根节点);一个整型变量 k,表示要查找的目标层级。函数返回一个整数值,表示在第 k 层上的节点总数。
  2. if (root == NULL)

    • 这行代码检查传入的 root 指针是否为 NULL。如果是 NULL,表示当前节点为空,无法计算节点个数,因此返回 0
  3. if (k == 1)

    • 这行代码检查目标层级 k 是否为 1。如果是 1,表示当前节点位于第 1 层,因此返回 1,表示第 1 层有一个节点。
  4. return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);

    • 如果当前节点不为空且目标层级不是第 1 层,这行代码递归地调用自身两次,分别计算左子树和右子树在第 k-1 层的节点个数。然后,将这两个调用的结果相加,得到第 k 层的节点总数。

总结来说,BinaryTreeLevelKSize 函数通过递归的方式遍历二叉树,计算并返回第 k 层上的节点个数。它首先检查当前节点是否为空,如果不为空且目标层级为第 1 层,则返回 1。如果不是第 1 层,则递归地计算左子树和右子树在降低一层后的节点个数,并将它们相加得到结果。这种方法可以正确地计算出任意二叉树在指定层级的节点总数。

图解

层序遍历

什么是层序遍历

也就是:顾名思义,一层一层的输出

这里的关键点在于,怎么样一层一层进入,输出

那么此时我们可以采取队列的形式来进行使用,同时进队列,同时出队列

所以,这里我们是直接调用队列

队列的讲解-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/Jason_from_China/article/details/138730053

#include"Queue.h"
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	// 按照顺序,放入队列里面,先进先出,后进后出的原则
	// 1,创建队列,初始化
	// 2,如果不为空,根节点入队列
	// 3,取栈顶,打印,出队列

	Queue ps;
	QueueInit(&ps);
	if (root)
		QueuePush(&ps, root);

	while (!QueueEmpty(&ps))
	{
		BTNode* ret = QueueFront(&ps);
		QueuePop(&ps);

		printf("%d ", ret->_data);

		if (ret->_left)
			QueuePush(&ps, ret->_left);
		if (ret->_right)
			QueuePush(&ps, ret->_right);
	}
	//队列的销毁
	QueueDestroy(&ps);
}

解释:

  1. #include"Queue.h"

    • 这行代码包含了队列数据结构的头文件,该文件中定义了队列操作的相关函数和数据结构。
  2. void BinaryTreeLevelOrder(BTNode* root)

    • 这是函数的声明行,定义了一个名为 BinaryTreeLevelOrder 的函数,它接收一个指向 BTNode 类型的指针 root 作为参数,表示二叉树的根节点。
  3. Queue ps;

    • 这行代码声明了一个名为 ps 的队列变量。然而,这可能不足以正确地在某些语言中创建队列,因为队列可能需要动态分配(取决于其实现)。
  4. QueueInit(&ps);

    • 这行代码调用 QueueInit 函数来初始化队列 ps
  5. if (root) QueuePush(&ps, root);

    • 如果根节点 root 不为空,这行代码调用 QueuePush 函数将根节点入队。
  6. while (!QueueEmpty(&ps))

    • 这行代码开始一个循环,它会一直执行,直到队列变空。QueueEmpty 函数检查队列是否为空。
  7. BTNode* ret = QueueFront(&ps);

    • 这行代码调用 QueueFront 函数获取队列前端的节点,但不从队列中移除它。
  8. QueuePop(&ps);

    • 这行代码调用 QueuePop 函数从队列中移除前端的节点。
  9. printf("%d ", ret->_data);

    • 这行代码打印当前节点 ret 的数据。
  10. if (ret->_left) QueuePush(&ps, ret->_left);

    • 如果当前节点 ret 的左子节点存在,这行代码将其入队。
  11. if (ret->_right) QueuePush(&ps, ret->_right);

    • 如果当前节点 ret 的右子节点存在,这行代码将其入队。
  12. QueueDestroy(&ps);

    • 最后,这行代码调用 QueueDestroy 函数销毁队列,释放所有分配的内存。

总结来说,BinaryTreeLevelOrder 函数使用队列来实现二叉树的层序遍历。它首先初始化一个队列,然后将根节点入队。在循环中,它取出队列前端的节点,打印其数据,然后将其左右子节点(如果存在)依次入队。这个过程一直重复,直到队列为空。

这里的关键在于我们要认识到出去一个节点,进去两个节点

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

这里的逻辑也是采取队列的形式来进行判断,只是我们需要入空,当最后入的数值为空的时候,我们需要跳出循环,然后进行判断

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue ps;
	QueueInit(&ps);
	if (root)
		QueuePush(&ps, root);

	while (!QueueEmpty(&ps))
	{
		BTNode* ret = QueueFront(&ps);
		QueuePop(&ps);

		if (ret == NULL)
		{
			break;
		}
		if (ret->_left)
			QueuePush(&ps, ret->_left);
		if (ret->_right)
			QueuePush(&ps, ret->_right);
	}
	while (!QueueEmpty(&ps))
	{
		BTNode* ret = QueueFront(&ps);
		QueuePop(&ps);
		if (ret != NULL)
		{
			QueueDestroy(&ps);
			return false;
		}
	}
	//队列的销毁
	QueueDestroy(&ps);
	return true;
}
  1. #include"Queue.h"

    • 包含队列操作的头文件。
  2. bool BinaryTreeComplete(BTNode* root)

    • 函数声明,返回类型为 bool,表示最终的布尔结果(是或不是完全二叉树)。
  3. Queue ps;

    • 声明一个队列 ps。注意:这可能不足以在某些语言中创建队列,因为队列可能需要动态分配。
  4. QueueInit(&ps);

    • 初始化队列。
  5. if (root) QueuePush(&ps, root);

    • 如果根节点不为空,则将其入队。
  6. 第一个 while 循环:

    • 使用队列进行层序遍历,访问所有节点。
  7. BTNode* ret = QueueFront(&ps);

    • 获取队列前端的节点。
  8. QueuePop(&ps);

    • 将队列前端的节点出队。
  9. if (ret == NULL) { break; }

    • 如果节点为 NULL,则退出循环。这个条件永远不会满足,因为 NULL 节点不会被入队。
  10. if (ret->_left) QueuePush(&ps, ret->_left);

    • 如果存在左子节点,则将其入队。
  11. if (ret->_right) QueuePush(&ps, ret->_right);

    • 如果存在右子节点,则将其入队。
  12. 第二个 while 循环:

    • 这个循环的目的是检查队列中是否还有非 NULL 节点。
  13. BTNode* ret = QueueFront(&ps);

    • 再次获取队列前端的节点。
  14. QueuePop(&ps);

    • 再次将队列前端的节点出队。
  15. if (ret != NULL) { QueueDestroy(&ps); return false; }

    • 如果节点不为 NULL,销毁队列并返回 false。这部分逻辑是错误的,因为按照完全二叉树的定义,队列中应该只有 NULL 节点。
  16. QueueDestroy(&ps);

    • 销毁队列。
  17. return true;

    • 返回 true 表示树是完全二叉树。

链式二叉树代码总结

Link_Teer.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;
//二叉树的初始化
BTNode* BuyNode(BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树高度
int BinaryTreeHeight(BTNode* root);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树销毁
void BinaryTreeDestory(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);

Link_Teer.c

#include"Link_Teer.h"
//二叉树的初始化
BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("BinaryTreeInit:newnode:");
		exit(1);
	}
	newnode->_data = x;
	newnode->_left = NULL;
	newnode->_right = NULL;
	return newnode;
}
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreeInOrder(root->_left);
	printf("%d ", root->_data);
	BinaryTreeInOrder(root->_right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%d ", root->_data);
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (BinaryTreeLeafSize(root->_left) == 0 && BinaryTreeLeafSize(root->_right) == 0)
		return 1;
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}
// 二叉树高度
int BinaryTreeHeight(BTNode* root)
{ 
	if (root == NULL)
	{
		return 0;
	}
	int heightleft = BinaryTreeHeight(root->_left);
	int heightright = BinaryTreeHeight(root->_right);
	return heightleft >= heightright ? heightleft + 1 : heightright + 1;
}
// 二叉树第k层节点个数
int 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);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->_data == x)
		return root;

	
	BTNode* ret1 = BinaryTreeFind(root->_left, x);
	if (ret1 != NULL)
	{
		return ret1;
	}
	BTNode* ret2 = BinaryTreeFind(root->_right, x);
	if (ret2 != NULL)
	{
		return ret2;
	}
	return NULL;

}
// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeDestory(root->_left);
	BinaryTreeDestory(root->_right);
	free(root);
}

#include"Queue.h"
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	// 按照顺序,放入队列里面,先进先出,后进后出的原则
	// 1,创建队列,初始化
	// 2,如果不为空,根节点入队列
	// 3,取栈顶,打印,出队列

	Queue ps;
	QueueInit(&ps);
	if (root)
		QueuePush(&ps, root);

	while (!QueueEmpty(&ps))
	{
		BTNode* ret = QueueFront(&ps);
		QueuePop(&ps);

		printf("%d ", ret->_data);

		if (ret->_left)
			QueuePush(&ps, ret->_left);
		if (ret->_right)
			QueuePush(&ps, ret->_right);
	}
	//队列的销毁
	QueueDestroy(&ps);
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue ps;
	QueueInit(&ps);
	if (root)
		QueuePush(&ps, root);

	while (!QueueEmpty(&ps))
	{
		BTNode* ret = QueueFront(&ps);
		QueuePop(&ps);

		if (ret == NULL)
		{
			break;
		}
		if (ret->_left)
			QueuePush(&ps, ret->_left);
		if (ret->_right)
			QueuePush(&ps, ret->_right);
	}
	while (!QueueEmpty(&ps))
	{
		BTNode* ret = QueueFront(&ps);
		QueuePop(&ps);
		if (ret != NULL)
		{
			QueueDestroy(&ps);
			return false;
		}
	}
	//队列的销毁
	QueueDestroy(&ps);
	return true;
}

test.c

#include"Link_Teer.h"
//构建二叉树
void teer()
{
	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;
	node2->_left = node3;
	node1->_right = node4;
	node4->_left = node5;
	node4->_right = node6;
	//node2->_right = node7;
	printf(" 二叉树前序遍历测试:\n");
	BinaryTreePrevOrder(node1);

	printf("\n\n\n");
	printf("二叉树中序遍历测试:\n");
	BinaryTreeInOrder(node1);

	printf("\n\n\n");
	printf("二叉树后序遍历测试:\n");
	BinaryTreePostOrder(node1);

	printf("\n\n\n");
	printf("二叉树节点个数测试:\n");
	int ret1 = BinaryTreeSize(node1);
	printf("%d", ret1);

	printf("\n\n\n");
	printf("二叉树叶子节点个数测试:\n");
	int ret2 = BinaryTreeLeafSize(node1);
	printf("%d", ret2);

	printf("\n\n\n");
	printf("二叉树高度测试:\n");
	int ret3 = BinaryTreeHeight(node1);
	printf("%d", ret3);

	printf("\n\n\n");
	printf("二叉树第k层节点个数测试:\n");
	int ret4 = BinaryTreeLevelKSize(node1, 3);
	printf("%d", ret4);

	printf("\n\n\n");
	printf("二叉树查找值为x的节点测试:\n");
	BTNode* ret5 = BinaryTreeFind(node1, 6);
	printf("%d", ret5->_data);

	printf("\n\n\n");
	printf("层序遍历测试:\n");
	BinaryTreeLevelOrder(node1);

	printf("\n\n\n");
	printf("判断二叉树是否是完全二叉树测试:\n");
	bool ret6 = BinaryTreeComplete(node1);
	printf("%d", ret6);
	
}
int main()
{
	//构建二叉树
	teer();
	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/651734.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Java跨Docker容器备份数据库数据

Java跨Docker容器备份数据库数据 前置背景思路整理编写备份脚本容器启动检验效果Java容器MySQL容器 Java代码执行备份 我的个人博客&#xff1a;Lichg&#xff0c;欢迎大家访问。 前置背景 在我们的开发部署场景中&#xff0c;通常多数使用Docker进行部署。当你的数据库和项目…

Ubuntu22.04之扩展并挂载4T硬盘(二百三十三)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…

Java | Leetcode Java题解之第115题不同的子序列

题目&#xff1a; 题解&#xff1a; class Solution {public int numDistinct(String s, String t) {int m s.length(), n t.length();if (m < n) {return 0;}int[][] dp new int[m 1][n 1];for (int i 0; i < m; i) {dp[i][n] 1;}for (int i m - 1; i > 0; …

文刻创作ai工具官网免费工具

文刻创作ai工具官网免费工具 Docshttps://iimenvrieak.feishu.cn/docx/O0UedptjbonN4UxyEy7cPlZknYc 文刻是一种可以帮助用户进行创作的AI工具。 它使用自然语言处理和机器学习技术&#xff0c;可以生成文章、故事、诗歌等文本内容。 用户可以通过输入一些关键词或指定一定的…

MobaXterm连接eNSP设备

1、开启一台交换机 2、右键设置查看交换机串口号&#xff08;2000&#xff09; 3、打开MBX&#xff0c;点击session。 4、配置MBX 5、右键点击 6、配置为force off&#xff0c;点击回车就可以看到效果了

Golang | Leetcode Golang题解之第116题填充每个节点的下一个右侧节点指针

题目&#xff1a; 题解&#xff1a; func connect(root *Node) *Node {if root nil {return root}// 每次循环从该层的最左侧节点开始for leftmost : root; leftmost.Left ! nil; leftmost leftmost.Left {// 通过 Next 遍历这一层节点&#xff0c;为下一层的节点更新 Next …

损失函数篇 | YOLOv8更换损失函数之Inner-IoU | 通过辅助边界框计算IoU损失

前言:Hello大家好,我是小哥谈。损失函数是机器学习中用来衡量模型预测值与真实值之间差异的函数。在训练模型时,我们希望通过不断调整模型参数,使得损失函数的值最小化,从而使得模型的预测值更加接近真实值。为弥补现有IoU损失函数在不同的检测任务中的泛化能力较弱且收敛…

HTTPS加密过程

今天我们说https具体工作原理。 HTTPS概念 HTTPS是一种网络协议&#xff0c;传统的HTTP是明文传输&#xff0c;非常 不安全&#xff0c;所以HTTPS是基于HTTP基础上进行加密传输内容。 HTTPS使用加密传输方式 第一种是非对称加密&#xff0c;是前期建立连接时候使用的数据加密…

Golang | Leetcode Golang题解之第115题不同的子序列

题目&#xff1a; 题解&#xff1a; func numDistinct(s, t string) int {m, n : len(s), len(t)if m < n {return 0}dp : make([][]int, m1)for i : range dp {dp[i] make([]int, n1)dp[i][n] 1}for i : m - 1; i > 0; i-- {for j : n - 1; j > 0; j-- {if s[i] …

R实验 正交试验设计与一元线性回归分析

实验目的&#xff1a; 掌握正交试验设计记号的意义&#xff1b;掌握正交试验设计的直观分析和方差分析&#xff1b;掌握一元线性回归模型的相关概念&#xff1b;掌握最小二乘法的思想&#xff1b;掌握一元线性回归方程的显著性检验和预测。 实验内容&#xff1a; &#xff11;…

Python | Leetcode Python题解之第116题填充每个节点的下一个右侧节点指针

题目&#xff1a; 题解&#xff1a; class Solution:def connect(self, root: Node) -> Node:if not root:return root# 从根节点开始leftmost rootwhile leftmost.left:# 遍历这一层节点组织成的链表&#xff0c;为下一层的节点更新 next 指针head leftmostwhile head:#…

mumu 模拟器安装

1.下载安装 下载地址 Win 历史版本&#xff1a;http://mumu.163.com/update/win/Mac 历史 版本&#xff1a;http://mumu.163.com/20200515/25905_880858.html 2.设置为竖屏 在设置中心--界面设置页面设置宽720&#xff0c;高1280&#xff0c;DPI为240&#xff0c;如下图所示。…

Go语言之GORM框架(三)——Hook(钩子)与Gorm的高级查询

Hook(钩子) 和我们在gin框架中讲解的Hook函数一样&#xff0c;我们也可以在定义Hook结构体&#xff0c;完成一些操作&#xff0c;相关接口声明如下&#xff1a; type CreateUser interface { //创建对象时使用的HookBeforeCreate() errorBeforeSave() errorAfterCreate() …

C++习题(1)

一、题目描述&#xff1a; 二、代码展示&#xff1a; #include <iostream> #include <iomanip> using namespace std; struct Student{char name[20];int id;int age;float score; }; int main() {int n;cin>>n;Student student[n];float sum0.0;for(int i0…

小易大数据:大数据报告查询领域的黑马,这些优势让你无法忽视!

随着大数据技术被运用到各行各业&#xff0c;风控领域也不例外&#xff0c;形成了基于大数据技术的大数据信用&#xff0c;也就是我们常说的大数据报告或者网贷大数据&#xff0c;在众多的查询平台中&#xff0c;小易大数据平台在市面上是比较受欢迎的&#xff0c;那在小易平台…

JAVASE2

封装的步骤&#xff1a; 1、所有属性私有化&#xff0c;使用private关键字进行修饰&#xff0c;private表示私有的&#xff0c;修饰的所有数据只能在本类中访问 2、对外提供简单入口&#xff1a;比如说被private修饰的成员变量&#xff0c;在其他类中只能通过getXxx/setXxx方法…

Linux之多进程

c程序获取进程pid和ppid 在 Linux 系统中管理进程使用树型管理方式每个进程都需要与其他某一个进程建立 父子关系, 对应的进程则叫做 父进程 Linux 系统会为每个进程分配 id , 这个 id 作为当前进程的唯一标识, 当进程结束, 则会回收 进程的 id 与 父进程的 id 分别通过 getpi…

马斯克:AI时代人人高收入,不需要工作,商品服务不再短缺,可能性80%

当前人工智能现状和未来如何&#xff1f;AI时代下&#xff0c;人类未来会发生哪些变化&#xff1f; 埃隆马斯克&#xff08;Elon Musk&#xff09;在2024 VivaTech大会上分享了关于地球未来的诸多愿景。 投资作业本课代表摘录了其中的要点&#xff0c;分享给大家&#xff1a…

c语言基础:数组的运用以及在内存中的地址的理解

目录 目录&#xff1a; 1.数组作为函数参数 2.数组在内存中的存储 2.1数组名是什么&#xff1f; 2.2下面我们来探讨二维数组的各个名字表示什么 二维数组的首元素地址是什么呢&#xff1f; *arr表示的是什么呢 &#xff1f;&#xff08;arr是二维数组&#xff09; 1.数组作…

C语言 | Leetcode C语言题解之第116题填充每个节点的下一个右侧节点指针

题目&#xff1a; 题解&#xff1a; struct Node* connect(struct Node* root) {if (root NULL) {return root;}// 从根节点开始struct Node* leftmost root;while (leftmost->left ! NULL) {// 遍历这一层节点组织成的链表&#xff0c;为下一层的节点更新 next 指针stru…