二叉树
- 二叉树顺序储存
如果二叉树不是满二叉树，那么先补一些虚节点使其称为满二叉树，虚节点存储0或#，再按从根到叶的顺序一度一度地依次存储在内存空间中。
如果二叉树不是满二叉树，使用顺序存储会浪费一定的内存空间。
- 二叉树的链式储存
1.二叉树中的节点单独申请空间，通过节点的地址来建立逻辑关系。
2.具体就是通过节点的父子关系来建立。
3.二叉树的除叶子外，每个节点都有两个子节点。
1.二叉树的创建
节点若没有子树指向NULL
2.依次创建子树
3.二叉树的遍历
遍历的原则每个节点必须且仅能访问一次。
二叉树的遍历：每个节点经过了三次，这三次中只能访问一次，到底哪一次访问节点，所以三种不同的访问时刻会出现三种遍历的结果。
先序序列：第一次经过节点访问节点。访问顺序：ABCDEFGHK
中序序列：第二次经过节点访问节点。访问顺序：BDCAEHGKF
后序序列：第三次经过节点访问节点。访问顺序：DCBHKGFEA
- 创建二叉树顺序：AB#CD###E#FGH##K###
递归函数调用的知识扩展：
递归函数：在某种条件下函数本身调用函数本身称为递归函数调用。
递归三要素：
1.递归函数必须有结束条件，函数在某中情况下停止调用函数本身。
2.递归函数必须要在递归过程中要不断往停止调用自己的条件上靠。
3.递归函数必须要有个返回值也就是递归调用要得到一个结果，或者是对递归过程中的过程输出遍历某个东西的作用。
尽量少使用递归函数：1.递归函数如果有创建局部变量，那么每次递归调用都会再栈上创建一次局部变量，如果递归函数被调用了很多次将会消耗大量的栈空间可能导致栈溢出。
2.函数调用本身也会有栈的消耗，调用函数之前要将当前的PC指针，存到LR寄存器中以便函数返回时跳转回来，而当前LR寄存器的内容就必须保存到栈上。
小结：
二叉树和线性表作用不同：
1.线性表主要用来操作数据，对数据插入、删除、查询等操作。
2.二叉树主要用来分析数据，按照一定顺序创建好二叉树，然后遍历二叉树访问二叉树的节点数据，从而分析二叉树中的数据。
- 二叉树按层遍历
访问完节点时，将节点的子树保存到队列，判断队列是否非空，将t指针指向队列节点的取地址内容。在访问新的t指针，重复以上步骤，直到队列为空。
代码仓库：http://gitea.880755.xyz/private/binary_tree.git
- 本文作者： 龙兄嵌入式
- 本文链接： https://hexo.880755.xyz/1970/01/01/zblog/download/85.二叉树/