当前位置：网站首页>二叉 树
二叉 树
2022-06-09 06:22:00 【AloneDrifters】
文章目录
递归方式 先序、中序、后序 遍历
public class RecursiveTraversalBT {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int v) {
value = v;
}
}
public static void f(Node head) {
if (head == null) {
return;
}
// 1
f(head.left);
// 2
f(head.right);
// 3
}
// 先序打印所有节点
public static void pre(Node head) {
if (head == null) {
return;
}
System.out.println(head.value);
pre(head.left);
pre(head.right);
}
public static void in(Node head) {
if (head == null) {
return;
}
in(head.left);
System.out.println(head.value);
in(head.right);
}
public static void pos(Node head) {
if (head == null) {
return;
}
pos(head.left);
pos(head.right);
System.out.println(head.value);
}
}
非递归方式 先序、中序、后序 遍历
使用栈
import java.util.Stack;
public class UnRecursiveTraversalBT {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int v) {
value = v;
}
}
//先序遍历
public static void pre(Node head) {
System.out.print("pre-order: ");
if (head != null) {
Stack<Node> stack = new Stack<Node>();
stack.add(head);
while (!stack.isEmpty()) {
head = stack.pop();
System.out.print(head.value + " ");
if (head.right != null) {
stack.push(head.right);
}
if (head.left != null) {
stack.push(head.left);
}
}
}
System.out.println();
}
//中序遍历
public static void in(Node cur) {
System.out.print("in-order: ");
if (cur != null) {
Stack<Node> stack = new Stack<Node>();
while (!stack.isEmpty() || cur != null) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
System.out.print(cur.value + " ");
cur = cur.right;
}
}
}
System.out.println();
}
//使用了两个栈实现后序遍历
public static void pos1(Node head) {
System.out.print("pos-order: ");
if (head != null) {
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();
s1.push(head);
while (!s1.isEmpty()) {
head = s1.pop(); // 头 右 左
s2.push(head);
if (head.left != null) {
s1.push(head.left);
}
if (head.right != null) {
s1.push(head.right);
}
}
// 左 右 头
while (!s2.isEmpty()) {
System.out.print(s2.pop().value + " ");
}
}
System.out.println();
}
//使用一个栈实现后序遍历
public static void pos2(Node h) {
System.out.print("pos-order: ");
if (h != null) {
Stack<Node> stack = new Stack<Node>();
stack.push(h);
Node c = null;
while (!stack.isEmpty()) {
c = stack.peek();
if (c.left != null && h != c.left && h != c.right) {
stack.push(c.left);
} else if (c.right != null && h != c.right) {
stack.push(c.right);
} else {
System.out.print(stack.pop().value + " ");
h = c;
}
}
}
System.out.println();
}
}
实现二叉树的按层遍历
1）宽度优先遍历，用队列
import java.util.LinkedList;
import java.util.Queue;
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;
}
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);
}
}
}
}
2）通过设置flag变量的方式，来发现某一层的结束
参考 （求二叉树的最大宽度） 这个题
求二叉树的最大宽度
1）使用map
2）不使用map
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
public class TreeMaxWidth {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static int maxWidthUseMap(Node head) {
if (head == null) {
return 0;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
// key 在 哪一层，value
HashMap<Node, Integer> levelMap = new HashMap<>();
levelMap.put(head, 1);
int curLevel = 1; // 当前你正在统计哪一层的宽度
int curLevelNodes = 0; // 当前层curLevel层，宽度目前是多少
int max = 0;
while (!queue.isEmpty()) {
Node cur = queue.poll();
int curNodeLevel = levelMap.get(cur);
if (cur.left != null) {
levelMap.put(cur.left, curNodeLevel + 1);
queue.add(cur.left);
}
if (cur.right != null) {
levelMap.put(cur.right, curNodeLevel + 1);
queue.add(cur.right);
}
if (curNodeLevel == curLevel) {
curLevelNodes++;
} else {
max = Math.max(max, curLevelNodes);
curLevel++;
curLevelNodes = 1;
}
}
max = Math.max(max, curLevelNodes);
return max;
}
public static int maxWidthNoMap(Node head) {
if (head == null) {
return 0;
}
Queue<Node> queue = new LinkedList<>();
queue.add(head);
Node curEnd = head; // 当前层，最右节点是谁
Node nextEnd = null; // 下一层，最右节点是谁
int max = 0;
int curLevelNodes = 0; // 当前层的节点数
while (!queue.isEmpty()) {
Node cur = queue.poll();
if (cur.left != null) {
queue.add(cur.left);
nextEnd = cur.left;
}
if (cur.right != null) {
queue.add(cur.right);
nextEnd = cur.right;
}
curLevelNodes++;
if (cur == curEnd) {
max = Math.max(max, curLevelNodes);
curLevelNodes = 0;
curEnd = nextEnd;
}
}
return max;
}
}
二叉树的序列化和反序列化
1）可以用 先序或者中序或者后序，来实现二叉树的序列化
（用了什么方式序列化，就用什么方式反序列化）
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class SerializeAndReconstructTree {
/* * 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化， * 以下代码全部实现了。 * 但是，二叉树无法通过中序遍历的方式实现序列化和反序列化 * 因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。 * 比如如下两棵树 * __2 * / * 1 * 和 * 1__ * \ * 2 * 补足空位置的中序遍历结果都是{ null, 1, null, 2, null} * * */
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static Queue<String> preSerial(Node head) {
Queue<String> ans = new LinkedList<>();
pres(head, ans);
return ans;
}
public static void pres(Node head, Queue<String> ans) {
if (head == null) {
ans.add(null);
} else {
ans.add(String.valueOf(head.value));
pres(head.left, ans);
pres(head.right, ans);
}
}
public static Queue<String> inSerial(Node head) {
Queue<String> ans = new LinkedList<>();
ins(head, ans);
return ans;
}
public static void ins(Node head, Queue<String> ans) {
if (head == null) {
ans.add(null);
} else {
ins(head.left, ans);
ans.add(String.valueOf(head.value));
ins(head.right, ans);
}
}
public static Queue<String> posSerial(Node head) {
Queue<String> ans = new LinkedList<>();
poss(head, ans);
return ans;
}
public static void poss(Node head, Queue<String> ans) {
if (head == null) {
ans.add(null);
} else {
poss(head.left, ans);
poss(head.right, ans);
ans.add(String.valueOf(head.value));
}
}
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;
}
public static Node buildByPosQueue(Queue<String> poslist) {
if (poslist == null || poslist.size() == 0) {
return null;
}
// 左右中 -> stack(中右左)
Stack<String> stack = new Stack<>();
while (!poslist.isEmpty()) {
stack.push(poslist.poll());
}
return posb(stack);
}
public static Node posb(Stack<String> posstack) {
String value = posstack.pop();
if (value == null) {
return null;
}
Node head = new Node(Integer.valueOf(value));
head.right = posb(posstack);
head.left = posb(posstack);
return head;
}
}
2）按层遍历
public class SerializeAndReconstructTree {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
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(); // head 父 子
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));
}
}
二叉树有 left、right、parent ，给这样二叉树的某个结点，返回该节点的后继节点
public class SuccessorNode {
public static class Node {
public int value;
public Node left;
public Node right;
public Node parent;
public Node(int data) {
this.value = data;
}
}
public static Node getSuccessorNode(Node node) {
if (node == null) {
return node;
}
if (node.right != null) {
return getLeftMost(node.right);
} else {
// 无右子树
Node parent = node.parent;
while (parent != null && parent.right == node) {
// 当前节点是其父亲节点右孩子
node = parent;
parent = node.parent;
}
return parent;
}
}
public static Node getLeftMost(Node node) {
if (node == null) {
return node;
}
while (node.left != null) {
node = node.left;
}
return node;
}
}
折纸条
public class PaperFolding {
public static void printAllFolds(int N) {
process(1, N, true);
System.out.println();
}
// 当前你来了一个节点，脑海中想象的！
// 这个节点在第i层，一共有N层，N固定不变的
// 这个节点如果是凹的话，down = T
// 这个节点如果是凸的话，down = F
// 函数的功能：中序打印以你想象的节点为头的整棵树！
public static void process(int i, int N, boolean down) {
if (i > N) {
return;
}
process(i + 1, N, true);
System.out.print(down ? "凹 " : "凸 ");
process(i + 1, N, false);
}
public static void main(String[] args) {
int N = 4;
printAllFolds(N);
}
}
边栏推荐
- TypeScrtipt 中的模块化
- Transmission medium twisted pair and optical fiber and binary
- Unity location service GPS API
- 全志V3s学习记录（11）音频、视频使用总结
- Mt2712 platform AGL6 demo adaptation
- C List sort
- ImportError: cannot import name ‘joblib‘ from ‘sklearn. externals‘
- 无缓存安装指令
- Cmake compiling littlevgl demo
- Introduction to bladed fault simulation method
猜你喜欢
邂逅 NodeJS
iTOP-IMX6Q开发板QT5.7系统Mplayer移植-交叉编译 Libmad-0.15.1b
Le Conseil de développement ITop - 2k1000 démarre ramdisk - make Start USB
Postman installation
The national industrial level Quanzhi t3/a40i core board -com-x40i helps the intelligent power system
照葫芦画瓢，移植qt5.12到T507开发板
Testing and threading
全志V3s学习记录（11）音频、视频使用总结
全志V3s学习记录（12）RTL8723BS的使用
全志平台BSP裁剪（4）kernel裁剪--File systems ＆ driver ＆ 杂项裁剪
随机推荐
Atlas7 NAND stress test program
全志H3停产,A40I/T3更胜一筹--CoM-X40I核心模块来了
C＃ 委托相关
C entrustment related
ImportError: cannot import name ‘joblib‘ from ‘sklearn.externals‘
[reprint] LCD common interface principle
Talk about bladed software
Mt2712 platform AGL6 demo adaptation
基于国产全志A40I的机器人示教器解决方案
MySQL password is correct but cannot log in
全志平台BSP裁剪（3）附件二 Kernel hacking配置说明
Solution of robot teaching pendant based on domestic Quanzhi a40i
全志平台BSP裁剪（6）附件三--rootfs menuconfig配置说明
Dropout正则化
全志V3s学习记录（9）buildroot文件系统构建
Competition between am335x and Quanzhi a40i
Yocto compiling libdrm
全志V3s学习记录（12）RTL8723BS的使用
Bladed software windfile calculation
Adam neural network