本文实例阐述了java实现二叉树深度优先遍历和广度优先遍历算法。 分享仅供参考。 具体如下。
1 .分析
二叉树深度优先扫描的非递归通用方法采用堆栈，广度优先扫描的非递归通用方法采用队列。
深度优先遍历：所有可能的分支路径无法再深入，每个节点只能访问一次。 需要特别注意的是，二叉树的深度优先扫描比较特殊，可以细分为先序扫描、中序扫描、后序扫描。 具体说明如下。
第一个遍历：对其中一个子树，首先访问根，然后遍历其左侧的子树，最后遍历其右侧的子树。
中顺扫描(对于任意一个子树，首先扫描其左子树，然后访问根，最后扫描其右子树。
后续遍历：对于任何一个子树，首先遍历其左边的子树，然后遍历其右边的子树，最后访问根。
广度优先遍历：也称为分层遍历，从上到下依次访问各层，在各层中，从左到右或从右到左访问，访问完一层后进入下一层，直到节点无法访问
2 .举例
要遍历二叉树，必须使用前导遍历(递归、非递归)、中序遍历(递归、非递归)、后序遍历(非递归)和宽度优先遍历，如下图所示。
参考代码
package binarytreetraversetest；
import java.util.linkedlist；
导入Java.util.queue；
//*
*二叉树深度优先遍历和广度优先遍历
* @author fantasy
* @版本1.02016/10/05-2016/10/07
*/
publicclassbinarytreetraversetest {
publicstaticvoidmain (字符串[ ] args ) {
binarysorttreetree=newbinarysorttree (；
tree.insertnode(35；
tree.insertnode(20；
tree.insertnode(15；
tree.insertnode(16；
tree.insertnode(29；
tree.insertnode(28；
tree.insertnode(30；
tree.insertnode(40；
tree.insertnode(50；
tree.insertnode(45；
tree.insertnode(55；
system.out.print ('向前遍历(递归):')；
tree.preorder traverse (tree.get root )；
system.out.println (；
system.out.print ('中顺序扫描(递归):')；
树. in order traverse (tree.get root )；
system.out.println (；
system.out.print ('后遍历(递归):')；
tree.postorder traverse (tree.get root )；
system.out.println (；
system.out.print ('超前遍历(非递归):')；
tree.preordertraversenorecursion (tree.get root )；
system.out.println (；
system.out.print ('中序扫描(非递归):')；
tree.inordertraversenorecursion (tree.get root )；
system.out.println (；
system.out.print ('后遍历(非递归):')；
tree.postordertraversenorecursion (tree.get root )；
system.out.println (；
system.out.print ('广度优先遍历：')；
tree.breadthfirsttraverse (tree.get root )；
}
}
//*
*节点
*/
类节点{
e值lue；
节点左；
节点光；
节点(值) {
this.value=value；
左=空；
right=null；
}
}
//*
*使用一个前置序列构建1
棵二叉排序树(又称二叉查找树)*/
class binarysorttree> {
private node root;
binarysorttree() {
root = null;
}
public void insertnode(e value) {
if (root == null) {
root = new node(value);
return;
}
node currentnode = root;
while (true) {
if (value.compareto(currentnode.value) > 0) {
if (currentnode.right == null) {
currentnode.right = new node(value);
break;
}
currentnode = currentnode.right;
} else {
if (currentnode.left == null) {
currentnode.left = new node(value);
break;
}
currentnode = currentnode.left;
}
}
}
public node getroot(){
return root;
}
/**
* 先序遍历二叉树(递归)
* @param node
*/
public void preordertraverse(node node) {
system.out.print(node.value + " ");
if (node.left != null)
preordertraverse(node.left);
if (node.right != null)
preordertraverse(node.right);
}
/**
* 中序遍历二叉树(递归)
* @param node
*/
public void inordertraverse(node node) {
if (node.left != null)
inordertraverse(node.left);
system.out.print(node.value + " ");
if (node.right != null)
inordertraverse(node.right);
}
/**
* 后序遍历二叉树(递归)
* @param node
*/
public void postordertraverse(node node) {
if (node.left != null)
postordertraverse(node.left);
if (node.right != null)
postordertraverse(node.right);
system.out.print(node.value + " ");
}
/**
* 先序遍历二叉树(非递归)
* @param root
*/
public void preordertraversenorecursion(node root) {
linkedlist> stack = new linkedlist>();
node currentnode = null;
stack.push(root);
while (!stack.isempty()) {
currentnode = stack.pop();
system.out.print(currentnode.value + " ");
if (currentnode.right != null)
stack.push(currentnode.right);
if (currentnode.left != null)
stack.push(currentnode.left);
}
}
/**
* 中序遍历二叉树(非递归)
* @param root
*/
public void inordertraversenorecursion(node root) {
linkedlist> stack = new linkedlist>();
node currentnode = root;
while (currentnode != null || !stack.isempty()) {
// 一直循环到二叉排序树最左端的叶子结点(currentnode是null)
while (currentnode != null) {
stack.push(currentnode);
currentnode = currentnode.left;
}
currentnode = stack.pop();
system.out.print(currentnode.value + " ");
currentnode = currentnode.right;
}
}
/**
* 后序遍历二叉树(非递归)
* @param root
*/
public void postordertraversenorecursion(node root) {
linkedlist> stack = new linkedlist>();
node currentnode = root;
node rightnode = null;
while (currentnode != null || !stack.isempty()) {
// 一直循环到二叉排序树最左端的叶子结点(currentnode是null)
while (currentnode != null) {
stack.push(currentnode);
currentnode = currentnode.left;
}
currentnode = stack.pop();
// 当前结点没有右结点或上一个结点(已经输出的结点)是当前结点的右结点，则输出当前结点
while (currentnode.right == null || currentnode.right == rightnode) {
system.out.print(currentnode.value + " ");
rightnode = currentnode;
if (stack.isempty()) {
return; //root以输出，则遍历结束
}
currentnode = stack.pop();
}
stack.push(currentnode); //还有右结点没有遍历
currentnode = currentnode.right;
}
}
/**
* 广度优先遍历二叉树，又称层次遍历二叉树
* @param node
*/
public void breadthfirsttraverse(node root) {
queue> queue = new linkedlist>();
node currentnode = null;
queue.offer(root);
while (!queue.isempty()) {
currentnode = queue.poll();
system.out.print(currentnode.value + " ");
if (currentnode.left != null)
queue.offer(currentnode.left);
if (currentnode.right != null)
queue.offer(currentnode.right);
}
}
}
② 输出结果
先序遍历(递归)：35 20 15 16 29 28 30 40 50 45 55
中序遍历(递归)：15 16 20 28 29 30 35 40 45 50 55
后序遍历(递归)：16 15 28 30 29 20 45 55 50 40 35
先序遍历(非递归)：35 20 15 16 29 28 30 40 50 45 55
中序遍历(非递归)：15 16 20 28 29 30 35 40 45 50 55
后序遍历(非递归)：16 15 28 30 29 20 45 55 50 40 35
广度优先遍历：35 20 40 15 29 50 16 28 30 45 55
希望本文所述对大家java程序设计有所帮助。
希望与广大网友互动？？
点此进行留言吧！