二叉树的知识点

二叉树是规定每个结点至多只有二个孩子的树。

二叉树是最简单的树形结构，所有的一般树都可以转换为二叉树，转换后的二叉树也能按一定规则还原为一般树。

遍历二叉树就是以某种次序来访问二叉树中的每个结点，且每个结点仅被访问一次。

访问就是查询结点数据域的内容、输出结点的数据、修改结点的数据或是执行对结点的其他操作

二叉树的三种遍历次序：

在这里插入图片描述

（一） 先根遍历

先根遍历二叉树的递归定义为：若二叉树为空，则空操作否则

先访问根结点

再遍历左子树

然后遍历右子树。

以上面的图为例子遍历的结果是

A B D E H I J K C F G

（二） 中跟遍历

中根遍历二叉树的递归定义为：若二叉树为空，则空操作；否则

中根遍历左子树；

访问根结点；

中跟遍历由子树；

还是以上面的图为例子遍历的结果是

D B H E J I K A F C G

（三） 后跟遍历

后根遍历二叉树的递归定义为：若二叉树为空，则空操作；否则

后根遍历左子树；

后跟遍历右子树；

访问结点；

还是以上面的图为例子遍历的结果是

D H J K I E B F G C A