前序中序后序指的是节点的访问顺序, 前序就是先访问节点, 再用前序遍历访问节点的左子树, 最后用前序遍历访问节点的右子树.
中序遍历就是先用中序遍历访问节点的左子树, 再访问节点, 最后用中序遍历访问节点的右子树.
后序遍历是先用后序遍历访问节点的左子树, 再用后序遍历访问节点的右子树, 最后访问节点.
所以这个访问你也能看出, 相当于一个递归.
对于你的图, 可以这样拆解
前序遍历是 0节点 ( 0的左子树) ( 0的右子树) = 0节点 ( 1节点 (1的左子树) (1的右子树)) ( 2节点 (2的左子树)(2的右子树)) 以此类推, 最后得出前序遍历 : 0 1 3 7 8 4 9 10 2 5 11 12 6 13 14.
中序遍历同样, 只是拆解的方式改成节点在中间 (0的左子树) 0节点 ( 0的右子树) = ( (1的左子树) 1节点 (1的右子树)) 0节点 ( (2的左子树) 2节点 (2的右子树))
= ( ((3的左子树) 3节点 (3的右子树)) 1节点 ((4的左子树) 4节点 (4的右子树)) ) 0节点 ( ((5的左子树) 5节点 (5的右子树)) 2节点 ((6的左子树) 6节点 (6的右子树)) )
所以, 得出中序遍历 7 3 8 1 9 4 10 0 11 5 12 2 13 6 14
同样的, 后序遍历你就按照 ( 0的左子树) (0的右子树) 0节点 = ( (1的左子树) (1的右子树) 1节点 ) ( (2的左子树)(2的右子树) 2节点) 0节点 这样去拆解就可以了.
最后可以得出后序遍历为 7 8 3 9 10 4 1 11 12 5 13 14 6 2 0 |
转播
