企业官网建设流程全解析

上次文章简单讲了一下二叉树的基本概念，包括二叉树的基本原理，二叉树的分类，特殊的二叉树等等，今天来继续来深入的了解下二叉树

一.向上调整算法 建堆和向下调整算法建堆的时间复杂度计算

首先我们看一下向上调整算法建堆

void AdjustUp(int arr[], int child) { int parent = (child - 1) / 2; while (child > 0) { if (arr[child] > arr[parent]) { // 大顶堆条件 swap(arr[child], arr[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } void BuildHeap(int arr[], int n) { for (int i = 1; i < n; i++) { // 从第二个元素开始调整 AdjustUp(arr, i); } }

那向上和向下调整算法都可以建堆，那我们使用哪个呢？当然是哪个“好”用哪个，那这里的“好”，显然易见要算时间复杂度啦

二.向上调整算法建堆和向下调整算法建堆的时间复杂度对比以及堆排序的时间复杂度

为什么向上调整算法和向下调整算法时间复杂度一样，但是他们建堆的时间复杂度会有区别呢？

我们从图中可以看出,建堆的复杂度由节点调整次数和节点个数决定，向上调整算法建堆越往下节点个数越多，调整次数也越多，自然时间复杂度是没有向下调整算法低的。

堆排序的时间复杂度： O(n*logn)

三.创建链式结构二叉树

用链表来表示⼀棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 ，其结构如下：

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

该代码定义了一个二叉树节点的数据结构：

• 使用typedef将字符类型char重命名为BTDataType，便于后续修改数据类型
• 结构体BinaryTreeNode包含三个成员：
  • data：存储节点数据（类型为BTDataType）
  • left：指向左子节点的指针
  • right：指向右子节点的指针
• 最后通过typedef将struct BinaryTreeNode重命名为BTNode，简化后续使用

我们为了方便后续的使用，先手动创建一颗链式二叉树:

BTNode* buyNode(char x) { BTNode* newnode = (BTNode*)malloc(sizeof(BTNode)); if (newnode == NULL) { perror("malloc fail!"); exit(1); } newnode->data = x; newnode->left = newnode->right = NULL; return newnode; } BTNode* CreateTree() { BTNode* nodeA = buyNode('A'); BTNode* nodeB = buyNode('B'); BTNode* nodeC = buyNode('C'); BTNode* nodeD = buyNode('D'); BTNode* nodeE = buyNode('E'); BTNode* nodeF = buyNode('F'); nodeA->left = nodeB; nodeA->right = nodeC; nodeB->left = nodeD; nodeC->left = nodeE; nodeC->right = nodeF; return nodeA; }

四.前中后序遍历

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发生在遍历其左右子树之前。访问顺序为：根结点、左子树、右子树
中序遍历(Inorder Traversal)：访问根结点的操作发生在遍历其左右子树之中（间）。
访问顺序为：左子树、根结点、右子树
后序遍历(Postorder Traversal)：访问根结点的操作发生在遍历其左右子树之后。
访问顺序为：左子树、右子树、根结点

前序遍历：

• 访问顺序：根节点，左子树，右子树

void PreOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%c ", root->data); PreOrder(root->left); PreOrder(root->right); }

这部分代码是不是看起来很简单，这就利用了递归的暴力美学，为空就打印NULL并返回。大家一定要去仔细体会一下递归的过程，最好把函数递归的栈帧图给画出来理解。

中序遍历：

• 访问顺序：左子树，根节点，右子树

// 中序遍历--左根右 void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%c ", root->data); InOrder(root->right); }

后序遍历：

• 访问顺序：左子树，右子树，根节点

void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%c ", root->data); }

五、代码展现：

Tree.h：

int main() { // 构建示例二叉树 BTNode* A = (BTNode*)malloc(sizeof(BTNode)); A->data = 'A'; BTNode* B = (BTNode*)malloc(sizeof(BTNode)); B->data = 'B'; BTNode* C = (BTNode*)malloc(sizeof(BTNode)); C->data = 'C'; A->left = B; A->right = C; B->left = B->right = NULL; C->left = C->right = NULL; printf("PreOrder: "); PreOrder(A); // 输出：A B C printf("\nInOrder: "); InOrder(A); // 输出：B A C printf("\nPostOrder: "); PostOrder(A);// 输出：B C A return 0; }

Tree.c：

#include "Tree.h" // 前序遍历 void PreOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%c ", root->data); PreOrder(root->left); PreOrder(root->right); } // 中序遍历 void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%c ", root->data); InOrder(root->right); } // 后序遍历 void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%c ", root->data); }

以上就是本次关于二叉树与堆的核心知识点拓展，在前文基础概念的铺垫下，我们重点拆解了两大核心内容：一是堆的构建算法，明确了向上调整与向下调整建堆的本质区别——二者虽调整逻辑不同，但最终印证了向下调整建堆（O(n)）比向上调整建堆（O(n log n)）更高效，同时也牢记堆排序的时间复杂度始终为O(n log n)，这是后续运用堆解决问题的核心前提；二是链式二叉树的实现与遍历，从节点结构定义、手动创建二叉树，到前序、中序、后序三种递归遍历方式，清晰梳理了每一步的代码逻辑与遍历规则，尤其强调了递归思想在二叉树遍历中的应用，理解递归栈帧的执行过程，能更深刻地掌握遍历的本质。

二叉树与堆作为数据结构中的基础核心内容，其思想广泛应用于后续的排序、查找等场景。本次内容既是对前文基础的深化，也是为后续更复杂的数据结构学习筑牢根基。后续我们还将继续拓展二叉树与堆的进阶用法，解锁更多实用技巧，一起在数据结构的学习中逐步进阶，夯实每一个核心知识点