遍历二叉树(广度,深度,递归,非递归)

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<Node> queue = new LinkedList<Node>(); 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<Node> queue = new LinkedList<Node>(); 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<Node> travStack = new Stack<Node>();

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<Node> travStack = new Stack<Node>();

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<Node> travStack = new Stack<Node>();

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<Node> travStack = new Stack<Node>();

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<Node> travStack = new Stack<Node>(), output = new Stack<Node>();

if (p != null) { // left-to-right postorder = right-to-left preorder

travStack.push(p);

while (!travStack.isEmpty()) {

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<Node> travStack = new Stack<Node>();

while (p != null || !travStack.empty()) {

if (p != null) { //针进栈，遍历左子树

travStack.push(p);

p = p.left;

} else {

根指

//如果根结点没有右子树，

//或是右子树已经被访问，

//则访问根结点；否则遍历右子树

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) {

inOrde …… 此处隐藏：5095字，全部文档内容请下载后查看。喜欢就下载吧 ……