数据结构--二叉树初讲（二）

上次文章简单讲了一下二叉树的基本概念包括二叉树的基本原理二叉树的分类特殊的二叉树等等今天来继续来深入的了解下二叉树一.向上调整算法 建堆和向下调整算法建堆的时间复杂度计算首先我们看一下向上调整算法建堆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存储节点数据类型为BTDataTypeleft指向左子节点的指针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.hint 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)这是后续运用堆解决问题的核心前提二是链式二叉树的实现与遍历从节点结构定义、手动创建二叉树到前序、中序、后序三种递归遍历方式清晰梳理了每一步的代码逻辑与遍历规则尤其强调了递归思想在二叉树遍历中的应用理解递归栈帧的执行过程能更深刻地掌握遍历的本质。二叉树与堆作为数据结构中的基础核心内容其思想广泛应用于后续的排序、查找等场景。本次内容既是对前文基础的深化也是为后续更复杂的数据结构学习筑牢根基。后续我们还将继续拓展二叉树与堆的进阶用法解锁更多实用技巧一起在数据结构的学习中逐步进阶夯实每一个核心知识点