数据结构-树(三)

如何储存二叉树

储存二叉树有俩种方法，一是基于指针和引用的二叉链式储存法，一种是基于数组的顺序储存法

1 二叉链式储存法
这个比较简单，我们从图中可以看出，每个节点除了储存数据，还储存了左右子节点的指针，我们只要拿到根节点，就可以把整个树串起来
2 顺序储存法
我们把根节点储存在下标i=1的位置，那么左子节点储存在下标2 * i = 2的位置，右子节点储存在下标2 * i + 1 = 3的位置，由此类推，B的左子节点储存在2 * i = 2 * 2 = 4的位置，B的右子节点储存在2 * i + 1 = 2 * 2 + 1 = 5的位置
总结一下 ，如果X储存在i位置，那么左子节点储存在i 2的位置，右子节点储存在2i+1的位置，反过来i/2就是他父节点的位置，这种情况我们只要知道根节点的位置（一般根节点储存在下标1的位置，方便计算），就可以串起整个树

二叉树的遍历

二叉树有三种遍历方式， 前序遍历， 中序遍历， 后续遍历

前序遍历：对于树中任意节点来说，先打印这个节点，然后打印他的左子节点，最后打印他的右子节点

中序遍历：对于树中任 意节点来说，先打印他的左子节点，然后打印他本身，最后打印他的右子节点

后序遍历：对于树中的任意节点来说，先打印他的左子节点，然后打印他的右子节点，最后打印它本身

参考：  https://blog.csdn.net/qq_34760508/article/details/8659642

https://blog.csdn.net/qq_32065823/article/details/82715491

https://blog.csdn.net/wj8987922/article/details/52227390