当前位置：首页 > news >正文

【初阶数据结构篇】链式结构二叉树（续）

news 2024/11/5 21:50:49

文章目录

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！

👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++感兴趣的朋友，让我们一起进步！

接上篇：【初阶数据结构篇】链式结构二叉树（二叉链）的实现（感受递归暴力美学）-CSDN博客

2.6 二叉树查找位置x的节点

分为左右子树查找，依次递推即可
结束条件为空：说明在这一路径上没有找到
进入第二个if，说明找到了直接返回结点指针

2.6.1 示例代码：

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftFind = BinaryTreeFind(root->left, x);if (leftFind){return leftFind;}BTNode* rightFind = BinaryTreeFind(root->right, x);if (rightFind){return rightFind;}return NULL;
}

2.7 二叉树的销毁

2.7.1示例代码：

void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}

图解：

2.8 二叉树的层序遍历

层序遍历：对于树型结构，层序遍历就是按层从上到下，每层按一定顺序对树的节点进行遍历。我们通过如图所示的二叉树进行说明：对于左边的二叉树，按层划分后可得到右边的分层结构。

简单来说就是从上到下从左往右打印节点中的数据。

实现层序遍历需要借助数据结构队列（先进先出）

先将根节点入队列，出队列前打印根节点的数据，同时将根节点的左右孩子入队列，重复该过程，直至队列为空。

2.8.1 示例代码：

//层序遍历
//借助数据结构---队列
void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){//取队头，打印BTNode* front = QueueFront(&q);printf("%d ", front->data);QueuePop(&q);//队头节点的左右孩子入队列if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}//队列为空QueueDestroy(&q);
}

2.9 完全二叉树的判断

取队头，左右节点全入队列，当取出对头为空，跳出循环。

进入第二个循环判断剩下的队列是否有非空节点

有则为非完全二叉树，反之亦然。

2.9.1 示例代码：

//判断二叉树是否为完全二叉树
//---队列
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL){break;}QueuePush(&q, front->left);QueuePush(&q, front->right);}//队列不一定为空while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}