2024-11-30 二叉树的存储结构
一、顺序存储
1.定义一个结构体数组，每一个数组结点包含一个存储元素和一个bool指针来判断节点是否为空。首先利用循环初始化所有结点，使其标记为空，再按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点。（其中数组为静态数组，包含数量有限）
所需实现的基本操作：
几个重要常考的基本操作:
i的左孩子 --2i
i的右孩子 --2i+1
i的父节点 --li/2]
i所在的层次--「logz(n+1)或Llogzn]+ 1
若完全二叉树中共有n个结点，则
判断i是否有左孩子? --2i ≤n?
判断i是否有右孩子? --2i+1 ≤n?
判断i是否是叶子/分支结点?--i>ln/2]?
2.如果不是完全二叉树，则无法用顺序存储来反映结点的关系。
结论：二叉树的顺序存储结构，知识和存储完全二叉树。
二、链式存储
1.创建结构体结点，包含一个数据域和左右孩子指针，分别指向左孩子和右孩子，如果不存在孩子则指向null。（共有2n个指针，有n+1个指针指向null）（可构造线索二叉树）。
2. （假设每一个数据只包含一个int型的变量）首先定义一个指针指向null（空树），再用malloc函数申请一个根节点。根节点存入数字1，使根节点的左右指针指向null。再有malloc申请一个新空间存放2，接下来使根节点的左孩子指针指向该节点的p，这样他就变成根节点的左孩子，以此类推。
3.思考：这样找到左右孩子结点非常容易，但找父节点只能从根节点开始遍历。（如果需要经常需要寻找父节点，可以在结构体指针中多设置一个父节点---三叉链表）
总结：
