遍历二叉树广度深度递归非递归.docx
《遍历二叉树广度深度递归非递归.docx》由会员分享，可在线阅读，更多相关《遍历二叉树广度深度递归非递归.docx（15页珍藏版）》请在冰点文库上搜索。
遍历二叉树广度深度递归非递归
import java.util.*;
class Node {
Node left;
Node right;
int key;
public Node（int key） {
this.key = key;
}
}
public class BTree {
Node root;
/**
* the constructor
**/
public BTree（） {
this.root = null;
}
public BTree（int[] array） {
if （array == null || array.length == 0） {
throw new IllegalArgumentException（）;
}
root = new Node（array[0]）;
Queue queue = new LinkedList（）;
queue.offer（root）;
int i = 1;
while（i < array.length） {
if （!
queue.isEmpty（）） {
Node p = queue.poll（）;
p.left = new Node（array[i]）;
queue.offer（p.left）;
i++;
if （i < array.length） {
p.right = new Node（array[i]）;
queue.offer（p.right）;
i++;
}
}
}
}
/********************************************************************
* 广度优先遍历
*
********************************************************************/
public void breadthFirstTraverse（） {
Node p = root;
if （p !
= null） {
Queue queue = new LinkedList（）;
queue.offer（p）;
while （!
queue.isEmpty（）） {
p = queue.poll（）;
System.out.println（p.key）;
if （p.left !
= null） {
queue.offer（p.left）;
}
if （p.right !
= null） {
queue.offer（p.right）;
}
}
}
}
/********************************************************************
* 深度优先遍历
*
********************************************************************/
/**
* iterative traverse
*
**/
public void iterativePreorder（） {
Node p = root;
Stack travStack = new Stack（）;
if （p !
= null） {
travStack.push（p）;
while （!
travStack.isEmpty（）） {
p = travStack.pop（）;
System.out.println（p.key）;
if （p.right !
= null）
travStack.push（p.right）;
if （p.left !
= null） // left child pushed after right
travStack.push（p.left）; // to be on the top of the stack;
}
}
}
public void iterativeInorder（） {
Node p = root;
Stack travStack = new Stack（）;
while （p !
= null） {
while（p !
= null） { // stack the right child （if any）
if （p.right !
= null） // and the node itself when going
travStack.push（p.right）; // to the left;
travStack.push（p）;
p = p.left;
}
p = travStack.pop（）; // pop a node with no left child
while （!
travStack.isEmpty（） && p.right == null） { // visit it and all
System.out.println（p.key）; // nodes with no right child;
p = travStack.pop（）;
}
System.out.println（p.key）; // visit also the first node with
if （!
travStack.isEmpty（）） // a right child （if any）;
p = travStack.pop（）;
else p = null;
}
}
public void iterativeInorderPlus（） {
Node p = root;
Stack travStack = new Stack（）;
travStack.push（p）;
while （!
travStack.empty（）） {
while （（p = travStack.peek（）） !
= null） {//向左走到尽头
travStack.push（p.left）;
}
travStack.pop（）; //pop the null element
if （!
travStack.empty（）） {
p = travStack.pop（）; //访问结点，向右一步
System.out.println（p.key）;
travStack.push（p.right）;
}
}
}
public void iterativeInorderPlusPlus（） {
Node p = root;
Stack travStack = new Stack（）;
while （p !
= null || !
travStack.empty（）） {
if （p !
= null） { //根指针进栈，遍历左子树
travStack.push（p）;
p = p.left;
} else { //根指针退栈，访问根结点，遍历右子树
p = travStack.pop（）;
System.out.println（p.key）;
p = p.right;
}
}
}
public void iterativePostorder（） {
Node p = root;
Stack travStack = new Stack（）, output = new Stack（）;
if （p !
= null） { // left-to-right postorder = right-to-left preorder
travStack.push（p）;
while （!
travStack.isEmpty（）） {
p = travStack.pop（）;
output.push（p）;
if （p.left !
= null）
travStack.push（p.left）;
if （p.right !
= null）
travStack.push（p.right）;
}
while （!
output.isEmpty（）） {
p = output.pop（）;
System.out.println（p.key）;
}
}
}
public void iterativePostorderPlus（） {
Node p = root;
Node q = null;
Stack travStack = new Stack（）;
while （p !
= null || !
travStack.empty（）） {
if （p !
= null） { //根指针进栈，遍历左子树
travStack.push（p）;
p = p.left;
} else {
p = travStack.peek（）;
//如果根结点没有右子树，
//或是右子树已经被访问，
//则访问根结点；否则遍历右子树
if （p.right == null || p.right == q） {
p = travStack.pop（）;
System.out.println（p.key）;
q = p;
p = null;
} else {
p = p.right;
}
}
}
}
/**
* recursive traverse
*
*
**/
public void preOrderTraverse（Node p） {
if （p !
= null） {
System.out.println（p.key）;
if （p.left !
= null） {
preOrderTraverse（p.left）;
}
if （p.right !
= null） {
preOrderTraverse（p.right）;
}
}
}
public void inOrderTraverse（Node p） {
if （p !
= null） {
if （p.left !
= null） {
inOrderTraverse（p.left）;
}
System.out.println（p.key）;
if （p.right !
= null） {
inOrderTraverse（p.right）;
}
}
}
public void postOrderTraverse（Node p） {
if （p !
= null） {
if （p.left !
= null） {
postOrderTraverse（p.left）;
}
if （p.right !
= null） {
postOrderTraverse（p.right）;
}
System.out.println（p.key）;
}
}
/**
* 通过转换树遍历
*
* 不使用任何堆栈或线索化遍历一个树也是可能的。
* 有很多这样的算法，它们都是在遍历期间对树进行了暂时的改变，
* 这些改变包含了为一些引用域赋了新的值。
但是，树可能会失去
* 它的树结构，这在完成遍历后需要恢复
**/
/**
* Joseph M.Morris 先序遍历
**/
public void morrisPreorder（） {
Node p = root, tmp = null;;
while （p !
= null） {
if （p.left == null） {
System.out.println（p.key）;
p = p.right;
}
else {
tmp = p.left;
while （tmp.right !
= null && tmp.right !
= p） // go to the rightmost node of the left subtree or
tmp = tmp.right; // to the temporary parent of p;
if （tmp.right == null） { // if ‘true‘ rightmost node was
System.out.println（p.key）;
tmp.right = p; // reached, make it a temporary
p = p.left; // parent of the current root,
}
else { // else a temporary parent has been
// System.out.println（p.key）; // found; visit node p and then cut
tmp.right = null; // the right pointer of the current
p = p.right; // parent, whereby it ceases to be
} // a parent;
}
}
//System.out.printf（"temp.key = %s", tmp.key）;
}
/**
* Joseph M.Morris 中序遍历
*
* MorrisInorder（）
* while 未结束
* if 节点无左子女
* 访问他；
* 到右边；
* else
* 使该节点成为其左子女的最右节点的右子女
* 到这个节点的左子女
**/
public void morrisInorder（） {
Node p = root, tmp = null;;
while （p !
= null） {
if （p.left == null） {
System.out.println（p.key）;
p = p.right;
}
else {
tmp = p.left;
升级会员 