二叉树的概念&结构
二叉树是：
- 空树
- 非空：根节点，根节点的左子树、根节点的右子树组成的
- 二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。
二叉树的遍历概念
学习二叉树结构，最简单的方式就是遍历。
二叉树遍历(Traversal)：是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历。
- 前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发生在遍历其左右子树之前。
- 中序遍历(Inorder Traversal）：访问根结点的操作发生在遍历其左右子树之中（间）。
- 后序遍历(Postorder Traversal)：访问根结点的操作发生在遍历其左右子树之后。
- 由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。
- NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
- ❗注意：遍历到NULL才不往下走（而不是到叶子节点就停住）
- 前序遍历：根 左 右
- 中序遍历：左 根 右
- 后续遍历：左 右 根
请写出下面二叉树的前/中/后的遍历顺序！
手写二叉树测试
在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入，为了降低大家学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。
注意：下述代码并不是创建二叉树的方式，真正创建二叉树方式后序详解重点讲解。
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<assert.h> //二叉树节点结构体 typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; //手动建造一个二叉树 //放入数据，左右置为NULL BTNode* BuyNode(int x) { BTNode* tmp = (BTNode*)malloc(sizeof(BTNode)); assert(tmp); if (tmp == NULL) { perror("malloc fail"); return; } tmp->data = x; tmp->left = NULL; tmp->right = NULL; return tmp; } //放入数据链接成树 BTNode* CreatBinaryTree() { 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(1); node1->left = node2; node1->right = node4; node2->left = node3; node4->left = node5; node4->right = node6; return node1; }
二叉树遍历实现代码
// 二叉树前序遍历 void PreOrder(BTNode* root) { if (root == NULL) { printf("N "); return; } printf("%d ", root->data);//根 PreOrder(root->left);//左 PreOrder(root->right);//右 } //中序 void InOrder(BTNode* root) { if (root == NULL) { printf("N "); return; } InOrder(root->left);//左 printf("%d ", root->data);//根 InOrder(root->right);//右 } //后序 void PostOrder(BTNode* root) { if (root == NULL) { printf("N "); return; } PostOrder(root->left);//左 PostOrder(root->right);//右 printf("%d ", root->data);//根 } int main() { BTNode* node = CreatBinaryTree(); // 二叉树前序遍历 PreOrder(node); printf("\n"); // 二叉树中序遍历 InOrder(node); printf("\n"); // 二叉树后序遍历 PostOrder(node); }
- 前序遍历结果：1 2 3 4 5 6
- 中序遍历结果：3 2 1 5 4 6
- 后序遍历结果：3 2 5 6 4 1
递归图解
- 结合函数栈帧理解（更好的理解函数调用的过程）函数栈帧的创建与销毁-CSDN博客
- 函数递归回顾。C语言之函数递归篇_c语言递归写法-CSDN博客
- 画图理解！！
- 递归同时证明了内存空间的重复利用。只要一个函数栈帧调用结束空间就归还给操作系统，操作系统在下次创建函数栈帧的时候还可以重复利用这块空间。（空间复杂度）
前序遍历递归图解
中序序遍历递归图解
后续遍历递归图解
🙂感谢大家的阅读，若有错误和不足，欢迎指正
