二叉树的遍历是指从根结点出发,沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。
先序(前序)遍历(Preorder Traversal)、中序遍历(Inorder Traversal)、后序遍历(Postorder Traveral)、层序遍历
先访问根结点,然后遍历其左右子树(简写:根左右)
先访问根结点的左子树,然后访问根结点,最后遍历右子树(简写:左根右)
先从左到右按照左右结点、父节点的方式遍历左右子树,最后访问根结点(简写:左右根)
从根结点由上而下逐层遍历,在同一层按从左到右的顺序对结点逐个访问。
N(Node)、L(Left subtree)和R(Right subtree)又认为是根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
1.根据二叉树写出对应的前序/中序/后序/层序遍历。
2.根据一棵树的前序遍历与中序遍历构造二叉树。