二叉树的遍历:

D:访问根结点,L:遍历根结点的左子树,R:遍历根结点的右子树。

给定一棵二叉树的前序遍历序列和中序遍历序列可以惟一确定一棵二叉树。

二叉树的深度优先遍历的非递归的通用做法是采用,广度优先遍历的非递归的通用做法是采用队列

深度优先遍历二叉树

1. 中序遍历(LDR)的递归算法:
若二叉树为空,则算法结束;否则:
中序遍历根结点的左子树;
访问根结点;
中序遍历根结点的右子树。

2. 前序遍历(DLR)的递归算法:
若二叉树为空,则算法结束,否则:
访问根结点;
前序遍历根结点的左子树;
前序遍历根结点的右子树。

3. 后序遍历(LRD)的递归算法:
若二叉树为空,则算法结束,否则:
后序遍历根结点的左子树;
后序遍历根结点的右子树;
访问根结点。

广度优先遍历二叉树
广度优先周游二叉树(层序遍历)是用队列来实现的,从二叉树的第一层(根结点)开始,自上至下逐层遍历;在同一层中,按照从左到右的顺序对结点逐一访问。
按照从根结点至叶结点、从左子树至右子树的次序访问二叉树的结点。算法:
1初始化一个队列,并把根结点入列队;
2当队列为非空时,循环执行步骤3到步骤5,否则执行6;
3出队列取得一个结点,访问该结点;
4若该结点的左子树为非空,则将该结点的左子树入队列;
5若该结点的右子树为非空,则将该结点的右子树入队列;
6结束。

非递归深度优先遍历二叉树
栈是实现递归的最常用的结构,利用一个栈来记下尚待遍历的结点或子树,以备以后访问,可以将递归的深度优先遍历改为非递归的算法。

参考链接:http://blog.csdn.net/hanruikai/article/details/7639007

标签: none

添加新评论