三种常见二叉树遍历:前序遍历,中序遍历,后续遍历。
三者都是针对根节点来讲,整体是按照【左->根->右】的顺序来输出。
前序遍历也叫先序遍历,先根遍历,意思就是根节点先输出,顺序就是根->左->右。
同理,中序遍历就是根节点输出的顺序在中央,输出顺序就是左->根->右。
后续遍历就是左->右->根。
二叉树的遍历,如果用非递归方式,一般都是用栈来实现。
1.迭代方法一:将所有元素依次push 到栈中,每次从栈中取元素。
2.迭代方法二:只push 右孩子。
3.递归
代码如下:
public class Test {
@Data
class Node {
int value;
Node leftNode;
Node rightNode;
}
//迭代第一种方法
public void preOrder1(Node node) {
if (node == null) return;
Stack<Node> stack = new Stack<>();
stack.push(node);
while(!stack.empty()) {
Node curNode = stack.pop();
System.out.print(curNode.value);
if (curNode.rightNode != null) stack.push(curNode.rightNode);
if (curNode.leftNode != null) stack.push(curNode.leftNode);
}
}
//迭代第二种方法
public void preOrder2(Node node) {
Stack<Node> stack = new Stack<>();
Node curNode = node;
while (curNode != null) {
System.out.print(curNode.value);
if (curNode.rightNode != null) stack.push(curNode.rightNode);
curNode = curNode.leftNode != null ? curNode.leftNode : stack.pop();
}
}
//递归
public void preOrderRecursion(Node node) {
if (node == null) return;
System.out.print(node.value);
preOrderRecursion(node.leftNode);
preOrderRecursion(node.rightNode);
}
}
public void inOrder(Node node) {
if (node == null) return;
Node cur = node;
Stack<Node> stack = new Stack<>();
while(cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.leftNode;
} else {
//此时证明cur的父节点无左孩子,那么输出cur的父节点,即栈弹出
cur = stack.pop();
System.out.print(cur.value);
cur = cur.rightNode;
}
}
}
//递归
public void inOrderRecursion(Node node) {
if (node == null) return;
inOrderRecursion(node.leftNode);
System.out.print(node.value);
inOrderRecursion(node.rightNode);
}
后续遍历的要求就是左->右->中。对于此顺序,即根节点是最后一个输出的。
设置两个栈结构,代码如下
public void postOrder(Node node) {
if (node == null) return;
Stack<Node> stack1 = new Stack<>();
Stack<Node> stack2 = new Stack<>();
stack1.push(node);
while(!stack1.empty()) {
node = stack1.pop();
stack2.push(node);
if (node.leftNode != null) stack1.push(node.leftNode);
if (node.rightNode!= null) stack1.push(node.rightNode);
}
while(!stack2.isEmpty()) {
System.out.print(stack2.pop().value);
}
}
//递归
public void postOrderRecursion(Node node) {
if (node == null) return;
postOrderRecursion(node.leftNode);
postOrderRecursion(node.rightNode);
System.out.print(node.value);
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。