二叉树的遍历

二叉树的遍历

先序遍历

先遇见哪个就先输出哪个

:red_circle:对二叉树结点从1开始连续编号:树中任一结点,其编号等于的左子树上的最小编号减一,而的右子树的最小编号等于v的左子树上的最大编号加一,说明该二叉树是按照先序遍历

中序遍历

找不到左子树或者从左子树回来,就输出该节点或者按压,将二维的树向下按压

后序遍历

:red_circle:最后一次遇见才想着去输出,(为了孩子 奉献自己)适合链表的删除(),因为都已经无依无靠了,删除也不影响其他

:red_circle:对二叉树的结点从1开始连续编号,要求每个结点的编号大于其左右孩子的编号,同一结点的左右孩子中,其左孩子编号小于其右孩子编号,可以用 后序遍历来实现编号()

层次遍历

利用队列来进行层次遍历

总结遍历的规律

1. 在二叉树的前序,中序,后序序列中,所有叶子节点的先后顺序是完全相同的()