二叉树是规定每个结点至多只有二个孩子的树。
二叉树是最简单的树形结构,所有的一般树都可以转换为二叉树,转换后的二叉树也能按一定规则还原为一般树。
遍历二叉树就是以某种次序来访问二叉树中的每个结点,且每个结点仅被访问一次。
访问就是查询结点数据域的内容、输出结点的数据、修改结点的数据或是执行对结点的其他操作
二叉树的三种遍历次序:
(一) 先根遍历
先根遍历二叉树的递归定义为:若二叉树为空,则空操作否则
先访问根结点
再遍历左子树
然后遍历右子树。
以上面的图为例子遍历的结果是
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