[数据结构与算法]树与树算法

树的每一个结点都有子节点，二叉树的每一个结点有0-2个子节点。于是二叉树的形状如下图所示：

完全二叉树：除了最底层之外，其它层全部是满的。若最底层也补充满了，则叫做满二叉树

二叉树结点实现：

它自身就是父节点，因此需要有两个子节点。

二叉树添加元素的实现：

?

?添加元素需要对结点进行挨个判定是否为空，如果父节点为空，就要判定子节点。按照广度遍历的顺序依次判断。使用循环实现。

为什么用队列呢？--因为不知道树有多少个结点，因此无法指定长度，也就不容易指定结束条件。但使用队列的话，可以把判断完毕的结点直接拿出去，不再存放在队列中，只把子节点放进来。于是当队列为空的时候就说明结束了。

?

广度遍历和先序遍历实现：

代码中问题解决：

1.使用递归的时候，调用自身函数，需要加上self，不然有语法错误

2.先序中序后序遍历，在代码上的区别就是打印结点的位置不同，注意各自递归调用的时候，是调用的自身，注意名字不要写成了其他函数。

?

由中序和后序遍历所得的排序，可以倒推出树的形状从而也可得出先序遍历。

中序和先序同理。

但若只有先序和后序则无法倒推。