对于二叉树,它的特点就是任何一个节点,左节点小于父节点、右节点大于父节点遍历二叉树有多种方式,如中序遍历、层序遍历、后序遍历,中序遍历的思路就是左-->父--->右的顺序,下面给出递归和非递归的两种方法,递归很好理解,非递归就是一直找到最左节点,然后回溯节点,如果存在右节点,则重复上述过程
如将下面的二叉树使用中序遍历输出有序数组
代码如下
import JAVA.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* 中序遍历的非递归和递归的实现
*
* @author ssj
*
*/
public class MiddleList {
public static void main(String[] args) {
// 创建一颗二叉树
Node root = new Node("10");
Node n6 = new Node("6");
Node n14 = new Node("14");
n6.setParent(root);
n14.setParent(root);
root.setLeft(n6);
root.setRight(n14);
Node n4 = new Node("4");
Node n8 = new Node("8");
n6.setLeft(n4);
n6.setRight(n8);
Node n12 = new Node("12");
Node n16 = new Node("16");
n14.setLeft(n12);
n14.setRight(n16);
System.out.println("---------递归遍历结果--------------------");
List list = new ArrayList();
middleListDG(root, list);
System.out.println(list);
System.out.println("---------非递归遍历结果--------------------");
List list2 = middleList(root);
System.out.println(list2);
}
/**
* 递归中序遍历
*
* @param root
* @return
*/
public static void middleListDG(Node root, List list) {
if (root == null) {
return;
}
middleListDG(root.left, list);
list.add(root.name);
middleListDG(root.right, list);
}
/**
* 非递归中序遍历
* @param root
* @return
*/
public static List middleList(Node root) {
Stack<Node> sk = new Stack<Node>();
List list = new ArrayList();
Node n = root;
while (n != null) {
// 一直找到最左边的节点
while (n != null) {
sk.push(n);
n = n.left;
}
// 输出最左边的节点
while (!sk.empty()) {
Node n2 = sk.pop();
list.add(n2.getName());
// 如果该节点存在右节点,先输出所有的右节点,即重复以上过程
if (n2.right != null) {
n = n2.right;
break;
}
}
}
return list;
}
}
/**
* 树节点
* @author ssj
*
*/
class Node {
public String name;
public Node left;
public Node right;
public Node parent = null;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public Node(String name) {
super();
this.name = name;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
输出结果