import java.util.LinkedList;
public class BinaryTree {
public static void main(String[] args) {
int randoms[] = new int[]{67, 7, 30, 73, 10, 0, 78, 81, 10, 74};
Node roots = new Node();
for (int number : randoms) {
roots.add(number);
}
//roots.preorderTraversal1();
//System.out.println();
roots.postorderTraversal2();
}
}
class Node {
/**
* 左孩子
*/
public Node lchild;
/**
* 右孩子
*/
public Node rchild;
/**
* 数据域
*/
public Integer value;
/**
* 添加孩子结点
*/
public void add(Integer i) {
if (null == this.value) {
this.value = i;
} else if (i <= this.value) {
if (null == this.lchild) {
lchild = new Node();
}
lchild.add(i);
} else {
if (null == this.rchild) {
rchild = new Node();
}
rchild.add(i);
}
}
/**
* 前序遍历(递归版本)
*/
public void preorderTraversal1() {
System.out.print(value + " ");
if (null != lchild) {
lchild.preorderTraversal1();
}
if (null != rchild) {
rchild.preorderTraversal1();
}
}
/**
* 前序遍历(非递归版本)
*/
public void preorderTraversal2() {
//用来暂存结点的栈
Stack<Node> nodes = new Stack<Node>();
//获取根节点
Node node = this;
//当遍历到最后一个结点时,栈为空,左右结点也为空,则结束遍历
while (node != null || !nodes.isEmpty()) {
//先靠左遍历把最左边的打印出来,然后再入栈
while (node != null) {
//当前结点非空则输出值
System.out.print(node.value + " ");
//入栈
nodes.push(node);
//一直寻找他的左结点
node = node.lchild;
}
//最左边的一条遍历完了后开始出栈且获取右结点
if (!nodes.isEmpty()) {
node = nodes.pop();
node = node.rchild;
}
}
}
/**
* 中序遍历(递归版本)
*/
public void inorderTraversal1() {
if (null != lchild) {
lchild.inorderTraversal1();
}
System.out.print(value + " ");
if (null != rchild) {
rchild.inorderTraversal1();
}
}
/**
* 中序遍历(非递归版本)
*/
public void inorderTraversal2() {
//暂存结点的栈
Stack<Node> nodes = new Stack<Node>();
//获取根节点
Node node = this;
//当遍历到最后一个结点时,栈为空,左右结点也为空,则结束遍历
while (node != null || !nodes.isEmpty()) {
//先把靠左的结点入栈
while (node != null) {
nodes.push(node);
node = node.lchild;
}
//再从末尾的几点开始遍历入栈右子树
if (!nodes.isEmpty()) {
node = nodes.pop();
//打印结点
System.out.print(node.value + " ");
//获取右节点
node = node.rchild;
}
}
}
/**
* 后序遍历(递归版本)
*/
public void postorderTraversal1() {
if (null != lchild) {
lchild.postorderTraversal1();
}
if (null != rchild) {
rchild.postorderTraversal1();
}
System.out.print(value + " ");
}
/**
* 后序遍历(非递归版本)
*/
public void postorderTraversal2() {
//将结点暂存在栈中
Stack<Node> nodes = new Stack<Node>();
//获取根节点
Node node = this;
Node lastVisit = this;
while (node != null || !nodes.isEmpty()) {
//先将左侧结点入栈
while (node != null) {
nodes.push(node);
node = node.lchild;
}
//先获得栈顶的元素
node = nodes.peek();
if (node.rchild == null || node.rchild == lastVisit) {
System.out.print(node.value + " ");
//访问过了元素,则出栈
nodes.pop();
//标记为访问过了,最后一次访问的
lastVisit = node;
//防止下次循环把已入栈过的元素重复入栈
node = null;
} else {
//如果右边还有子树还没遍历则继续遍历
node = node.rchild;
}
}
}
/**
* 层序遍历
*/
public void levelTraversal() {
//使用队列来暂存结点
Queue<Node> nodes = new LinkedList<>();
//获取根节点
Node node = this;
//如果该树为空,则不遍历
if (node != null) {
nodes.offer(node);
}
//只要队列不为空,则继续遍历
while (!nodes.isEmpty()) {
//获取队头元素
node = nodes.peek();
//如果该节点的左右子节点都不为空,则加入队列,否则跳过
if (node.lchild != null) {
nodes.offer(node.lchild);
}
if (node.rchild != null) {
nodes.offer(node.rchild);
}
//打印队头元素的数据域的值
System.out.print(node.value + " ");
//队头元素遍历完毕,出队
nodes.poll();
}
}
}
class Stack<T> {
private LinkedList<T> stack = new LinkedList<>();
public void push(T t) {
stack.addFirst(t);
}
public T pop() {
return stack.removeFirst();
}
public T peek() {
return stack.getFirst();
}
public boolean isEmpty() {
return stack.isEmpty();
}
@Override
public String toString() {
return stack.toString();
}
}
数据结构 - 二叉树的遍历(递归VS非递归)
我走得很慢,但我从不后退!