树的前中后序遍历

08 April 2013

分类

个人理解

前中后的意思就是父结点的分别放在前中后,关键就是父结点的遍历先后顺序。

前序是:父--孩子--孩子

中序是:孩子--父--孩子

后序是:孩子--孩子--父

伪代码

前序遍历:

前序遍历(root){
	对root结点操作,做你想做的任何事;
	如果root.left存在,前序遍历(root.left);
	如果root.right存在,前序遍历(root.right);
}

中序遍历:

中序遍历(root){
	如果root.left存在,中序遍历(root.left);
	对root结点操作,做你想做的任何事;
	如果root.right存在,中序遍历(root.right);
}

后序遍历:

后序遍历(root){
	如果root.left存在,后序遍历(root.left);
	如果root.right存在,后序遍历(root.right);
	对root结点操作,做你想做的任何事;
}

广度优先

前中后都是深度优先,这些都是从字面意思上来理解的,而另一种遍历方式就是广度优先,是从上至下的遍历方式,先操作离根结点近的层,再分别操作各个后代。 而深度相对来说是要先接触下层的叶子结点的,这就是两种遍历方法的区别。


tags:    tree   
回到首页