来源:NanShan 今天主要介绍前序遍历(Perorder traversal)
即时通讯软件的客户端界面需要用到链表,链表是个比较深的学问,NanShan 今天主要介绍前序遍历(Perorder traversal)
前序遍历从当前节点(节点 c)开始访问,然后访问其左孩子,再访问右孩子。开始时,节点 c 为 BST 的根节点。算法如下:
1.访问节点 c;
2.对节点 c 的左孩子重复第 1 步;
3.对节点 c 的右孩子重复第 1 步;
则上图中树的遍历结果为:90, 50, 20, 5, 25, 75, 66, 80, 150, 95, 92, 111, 175, 166, 200。
中序遍历(Inorder traversal)
中序遍历是从当前节点(节点 c)的左孩子开始访问,再访问当前节点,最后是其右节点。开始时,节点 c 为 BST 的根节点。算法如下:
1.访问节点 c 的左孩子;
2.对节点 c 重复第 1 步;
3.对节点 c 的右孩子重复第 1 步。
则上图中树的遍历结果为:5, 20, 25, 50, 66, 75, 80, 90, 92, 95, 111, 150, 166, 175, 200。
后序遍历(Postorder traversal)
后序遍历首先从当前节点(节点 c)的左孩子开始访问,然后是右孩子,最后才是当前节点本身。开始时,节点 c 为 BST 的根节点。算法如下:
1.访问节点 c 的左孩子;
2.对节点 c 的右孩子重复第1 步;
3.对节点 c 重复第 1 步;
则上图中树的遍历结果为:5, 25, 20, 66, 80, 75, 50, 92, 111, 95, 166, 200, 175, 150, 90。