二叉树深度优先遍历
先序遍历
// 树节点public static class Node {private Node left;private Node right;private int value;public Node(int value) {this.value = value;}}
先序遍历的递归实现
public static void pre(Node head) {if (head == null) return;System.out.print(head.value + "\t");pre(head.left);pre(head.right);}
先序遍历的非递归实现
非递归代码实现如下：
public static void preUnRec(Node head) {
if (head != null) {
Stack<Node> stack = new Stack<>();
stack.push(head); // 头节点先入栈
while (!stack.empty()) {
Node node = stack.pop(); // 栈顶元素出栈，孩子节点入栈，如果有右孩子右侧孩子先入栈。
System.out.print(node.value + "\t");
if (node.right != null) { // 右孩子先入栈
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
}
中序遍历
中序遍历的递归实现
public static void in(Node head) {
if (head == null) return;
in(head.left);
System.out.print(head.value + "\t");
in(head.right);
}
中序遍历的非递归实现
/**
* 中序遍历 - 非递归
* @param cur 二叉树的当前节点
* 当前节点有左孩子，左孩子先入栈，左孩子优先
* 当前节点没有左孩子，当前节点出栈，打印节点信息，
* 当前节点指向其右孩子。
*/
public static void inUnRec(Node cur){
if (cur != null) {
Stack<Node> stack = new Stack<Node>();
while (!stack.isEmpty() || cur != null) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
Node node = stack.pop();
System.out.print(node.value + "\t");
cur = node.right;
}
}
}
}
后序遍历
后序遍历的递归实现
public static void pos(Node head) {
if (head == null) return;
pos(head.left);
pos(head.right);
System.out.print(head.value + "\t");
}
后序遍历的非递归实现
后序遍历的非递归实现，是在先序遍历的非递归实现的基础上进行改造的，先序遍历依次将根节点存入栈中，每次节点出栈后，依次将节点的右孩子先入栈，然后左孩子再入栈，最后得到一个根左右的一个顺序。
如果在先序遍历中，将孩子的入栈顺序进行调整，左孩子先入栈，右孩子后入栈，我们将得到一个“根右左”的出栈顺序，如果我们将节点按照这个顺序存入到一个新栈中，最后再对这个新栈进行出栈操作，我们将得到一个“根左右”的顺序，也就是二叉树后续遍历的顺序。
/**
* 后续遍历 - 非递归 通过先序序列非递归方法进行改造 根 左 右 -》 根 右 左 -》 反转成 左 右 根
* @param head
*/
public static void postUnRec(Node head){
if (head != null) {
Stack<Node> stack = new Stack<>();
Stack<Node> stack2 = new Stack<>();
stack.push(head);
while (!stack.isEmpty()) {
Node node = stack.pop();
System.out.print(node.value + "\t");
stack2.push(node);
if (node.left != null) { // 左孩子先入栈，出栈时左孩子优先级次之
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
System.out.println("------中间序列-----");
while (!stack2.empty()) {
System.out.print(stack2.pop().value + "\t");
}
}
}
二叉树宽度优先遍历—按层遍历
按层遍历实现思路：
（1）二叉树头节点入队，队列对头元素cur出队，打印
（2）出队元素cur有左孩子，左孩子入队，有右孩子，右孩子入队。顺序是先左后右
可以通过设置flag的方式来判断二叉树按层遍历某一层是否结束。
// 二叉树按层遍历代码实现
public class LevelTraversalBT {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int v) {
value = v;
}
}
// 二叉树的按层遍历
public static void level(Node head) {
if (head == null) {
return;
}
// LinkedList 底层是双端节点
Queue<Node> queue = new LinkedList<>();// 队列来保存出栈的顺序
queue.add(head);
while (!queue.isEmpty()) {
Node cur = queue.poll(); // 队头元素出队
System.out.println(cur.value);
if (cur.left != null) { // 有左孩子，左孩子入队
queue.add(cur.left);
}
if (cur.right != null) { // 有右孩子，右孩子入队
queue.add(cur.right);
}
}
}
public static void main(String[] args) {
Node head = new Node(1);
head.left = new Node(2);
head.right = new Node(3);
head.left.left = new Node(4);
head.left.right = new Node(5);
head.right.left = new Node(6);
head.right.right = new Node(7);
level(head);
System.out.println("========");
}
}
二叉树的序列化和反序列化
二叉树 -> 字符串 ->二叉树 二叉树和字符串是一一对应的
二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化，但是不能通过中序遍历方式来进行。
eg:
* 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化，
* 以下代码全部实现了。
* 但是，二叉树无法通过中序遍历的方式实现序列化和反序列化
* 因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。
* 比如如下两棵树
* __2
* /
* 1
* 和
* 1__
* \
* 2
* 补足空位置的中序遍历结果都是{ null, 1, null, 2, null}
在二叉树的序列化和反序列化中，二叉树中的Null节点是不可忽略的，使用特殊来标识NULL。
先序方式序列化
在二叉树先序遍历递归代码实现的基础上进行改造，只不过对于每个树节点的空值也要进行存储，下面对二叉树先序遍历来进行一步步的改造得到，先序序列化的代码实现。
二叉树先序遍历递归代码实现如下：
public static void pre(Node head){ if(head == null) return null; System.out.print(head.vlaue + "\t") pre(head.left); pre(head.right); }改造1-先序遍历打印节点时，把还孩子节点为空的值也打印出来，用 # 来表示空节点
public static void pre-1(Node head){ if(head == null){ System.out.print("#\t") } else{ System.out.print(head.vlaue + "\t") pre(head.left); pre(head.right); } }对上图中二叉树进行先序遍历运行结果为: a b # c # # #
改造2-上面得到的输出序列就是二叉树先序方式序列化的结果，那么我们就考虑下一步，如何将这些结果保存起来，我们想到的是把这些节点按照先序遍历的顺序存储在一个队列中，如果遇到空的则保存为 #，得到队列后对队列进行出队操作，就可以得到序列化之后的结果。代码如下:
public static void pre-2(Node head, Queue<String> queue){ if(head == null){ queue.add("#"); } else { queue.add(String.valueOf(head.value)); pre(head.left,queue); pre(head.right,queue); } }得到二叉树按照先序序列化的代码实现
# 按照先序方式序列化二叉树 public Queue<String> static preSerial(Node head){ Queue<String> queue = new LinkedList<>(); pre-2(head,queue); return queue; }先序方式反序列化
通过序列化结果的值来将其进行反序列化，还原成二叉树的一个过程。如果采用的是先序方式序列化，则反序列化的时候也要采用先序的方式进行反序列化。
根据序列化得到的队列，依次出队，按照先序遍历的方式来构建二叉树，// 给定一个队列，建立一棵树，返回树的头节点 public static Node buildByPreQueue(Queue<String> prelist) { if (prelist == null || prelist.size() == 0) { return null; } return preb(prelist); } // 反序列化的过程 public static Node preb(Queue<String> prelist) { String value = prelist.poll(); if (value == "#") { // # 代表的是null,当取出的节点为#时，不建树，直接结束返回空 return null; } // 如果队列中出来的元素非空，则将该值作为节点值来建节点，作为当前的头节点 Node head = new Node(Integer.valueOf(value)); head.left = preb(prelist); // 先让左树消费这个队列 head.right = preb(prelist); // 再让右树消费这个队列 return head; }按层遍历方式序列化
如图，对于同一棵二叉树，按照按层遍历的方式进行序列化的结果为a,b,#,#,c,#,#
同先序遍历方式序列化的方式一样，该代码的实现仍然是基于按层遍历来改造的
二叉树按层方式序列化代码实现如下：
public static Queue<String> levelSerial(Node head) {
Queue<String> ans = new LinkedList<>(); // 用来保存序列化之后的结果
if (head == null) {
ans.add(null);
} else {
// 将头节点进行序列化，放入结果结合中
ans.add(String.valueOf(head.value));
// 队列用来存储序列化之后的节点，该队列中出队的元素来序列化其孩子节点；就是来帮助我们进行按层遍历的
Queue<Node> queue = new LinkedList<Node>(); // 进队列时进行序列化，出队列对其孩子进行序列化
queue.add(head); // 将序列化之后的节点加入到队列中
while (!queue.isEmpty()) {
head = queue.poll(); // 弹出一个节点，依次序列化该节点的左右孩子
if (head.left != null) {
// 左孩子非空，进行序列化，并且入队
ans.add(String.valueOf(head.left.value));
queue.add(head.left);
} else {
// 左孩子为空，只进行序列化，不将空放入序列化队列中
ans.add(null);
}
if (head.right != null) {
// 右孩子非空，进行序列化，并且入队
ans.add(String.valueOf(head.right.value));
queue.add(head.right);
} else {
// 右孩子为空，只进行序列化，不将空放入序列化队列中
ans.add(null);
}
}
}
return ans;
}
按层遍历方式反序列化
按照按层方式进行序列化之后的序列来进行对其反序列化操作。
按层进行反序列化代码实现如下：
public static Node buildByLevelQueue(Queue<String> levelList) {
if (levelList == null || levelList.size() == 0) {
return null;
}
// 先对头节点进行反序列化 -- 和序列化步骤一一对应
Node head = generateNode(levelList.poll());
Queue<Node> queue = new LinkedList<Node>();
if (head != null) {
queue.add(head);
}
Node node = null;
while (!queue.isEmpty()) {
node = queue.poll();
node.left = generateNode(levelList.poll()); // 先将左孩子进行反序列化
node.right = generateNode(levelList.poll()); // 再将有孩子进行反序列化
if (node.left != null) {
queue.add(node.left); // 如果左孩子非空加入到队列中，
}
if (node.right != null) {
queue.add(node.right); // 如果有孩子非空加入到队列中
}
}
return head;
}
// 根据给定的值来建立树的节点
public static Node generateNode(String val) {
if (val == null) {
return null;
}
return new Node(Integer.valueOf(val));
}
若有收获，就点个赞吧
0 人点赞
