java版二叉树所有递归和非递归遍历算法 - JAVA

erNoRecursion() {
System.out.print("binaryTree非递归先序遍历:");
LinkedList> stack = new LinkedList>();
stack.push(root);
Node current = null;
while (!stack.isEmpty()) {
current = stack.pop();
System.out.print(current.getValue());
if (current.getRightChild() != null)
stack.push(current.getRightChild());
if (current.getLeftChild() != null)
stack.push(current.getLeftChild());
}
System.out.println();
}

/**
* 栈内保存将要访问的元素
*/
public void inorderNoRecursion() {
System.out.print("binaryTree非递归中序遍历:");
LinkedList> stack = new LinkedList>();
Node current = root;
while (current != null || !stack.isEmpty()) {
while(current != null) {
stack.push(current);
current = current.getLeftChild();
}
if (!stack.isEmpty()) {
current = stack.pop();
System.out.print(current.getValue());
current = current.getRightChild();
}
}
System.out.println();
}

/**
* 当上一个访问的结点是右孩子或者当前结点没有右孩子则访问当前结点
*/
public void postorderNoRecursion() {
System.out.print("binaryTree非递归后序遍历:");
Node rNode = null;
Node current = root;
LinkedList> stack = new LinkedList>();
while(current != null || !stack.isEmpty()) {
while(current != null) {
stack.push(current);
current = current.getLeftChild();
}
current = stack.pop();
while (current != null && (current.getRightChild() == null ||current.getRightChild() == rNode)) {
System.out.print(current.getValue());
rNode = current;
if (stack.isEmpty()){
System.out.println();
return;

}
current = stack.pop();
}
stack.push(current);
current = current.getRightChild();
}

}

public static void main(String[] args) {
BinaryTree bt = new BinaryTree(new int[]{1,2,3,4,5,6,7,8});
bt.inorder();
bt.preorder();
bt.layerorder();
bt.preorderNoRecursion();
bt.inorderNoRecursion();
bt.postorderNoRecursion();
System.out.println("深度为：" + bt.getLength());
}
}

class Node{
private V value;
private Node leftChild;
private Node rightChild;

public Node(){
};

public Node(V value) {
this.value = value;
leftChild = null;
rightChild = null;
}

public void setLeftChild(Node lNode) {
this.leftChild = lNode;
}

public void setRightChild(Node rNode) {
this.rightChild = rNode;
}

public V getValue() {
return value;
}

public void setValue(V value) {
this.value = value;
}

public Node getLeftChild() {
return leftChild;
}

public Node getRightChild() {
retur

java版 二叉树 所有递归和非递归遍历算法(二)

java版二叉树所有递归和非递归遍历算法(二)