二叉树
原创
1.二叉树遍历
三种常见二叉树遍历：前序遍历，中序遍历，后续遍历。
三者都是针对根节点来讲，整体是按照【左->根->右】的顺序来输出。
前序遍历也叫先序遍历，先根遍历，意思就是根节点先输出，顺序就是根->左->右。
同理，中序遍历就是根节点输出的顺序在中央，输出顺序就是左->根->右。
后续遍历就是左->右->根。
二叉树的遍历，如果用非递归方式，一般都是用栈来实现。
前序迭代两种方法 + 递归：
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 删除。
评论
登录后参与评论
推荐阅读
目录