如何储存二叉树
储存二叉树有俩种方法,一是基于指针和引用的二叉链式储存法,一种是基于数组的顺序储存法
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