当前位置：网站首页>Tree structured binary tree
Tree structured binary tree
2022-06-22 14:54:00 【South wind knows easy***】
1. Traverse
Binary trees use preorder traversal ：
public class PreOrder {
public static void main(String[] args) {
PreOrder order = new PreOrder();
order.preOrder(order.initTree());
}
public void preOrder(TreeNode root) {
if (root != null) {
// Print the root node
System.out.print(root.val + " ");
// Visit the left subtree
preOrder(root.left);
// Visit the right subtree
preOrder(root.right);
}
}
// Construct initialization tree
public TreeNode initTree() {
TreeNode treeNode = new TreeNode(1);
treeNode.left = new TreeNode(2);
treeNode.right = new TreeNode(3);
treeNode.left.left = new TreeNode(4);
treeNode.left.right = new TreeNode(5);
treeNode.right.left = new TreeNode(6);
return treeNode;
}
}
Non recursive implementation , What should be done ？
We can use the stack structure to realize , Put the root node on the stack first , Then loop through the following operations until the stack is empty ：
- Take out the first element at the top of the stack （ node ）, Output .
- If the right node of the first node at the top of the stack is not empty , Then push the right node onto the stack .
- If the left node of the first node at the top of the stack is not empty , Then push the left node onto the stack .
import java.util.Stack;
public class PreOrder {
public static void main(String[] args) {
PreOrder order = new PreOrder();
order.preOrder(order.initTree());
}
public void preOrder(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
// If the tree is empty, it will directly return
if (root == null) return;
// First push the root node into the stack
stack.add(root);
// Loop through the following code until the stack is empty
while (!stack.isEmpty()) {
// Take out the top element of the stack , It can be understood as the current root node
TreeNode node = stack.pop();
// Output the current root node
System.out.print(node.val + " ");
// Press the right subtree first
if (node.right != null) stack.push(node.right);
// Then push the left subtree
if (node.left != null) stack.push(node.left);
}
}
// Construct initialization tree
public TreeNode initTree() {
// Construct a binary tree
TreeNode treeNode = new TreeNode(1);
treeNode.left = new TreeNode(2);
treeNode.right = new TreeNode(3);
treeNode.left.left = new TreeNode(4);
treeNode.left.right = new TreeNode(5);
treeNode.right.left = new TreeNode(6);
return treeNode;
}
}
Binary tree traversal using middle order ：
public class InOrder {
public static void main(String[] args) {
InOrder order = new InOrder();
order.inOrder(order.initTree());
}
public void inOrder(TreeNode root) {
if (root != null) {
// The left subtree
inOrder(root.left);
// Print the current root node
System.out.print(root.val + " ");
// Right subtree
inOrder(root.right);
}
}
// Construct initialization tree
public TreeNode initTree() {
// Construct a binary tree
TreeNode treeNode = new TreeNode(1);
treeNode.left = new TreeNode(2);
treeNode.right = new TreeNode(3);
treeNode.left.left = new TreeNode(4);
treeNode.left.right = new TreeNode(5);
treeNode.right.left = new TreeNode(6);
return treeNode;
}
}
The non recursive method of medium order traversal , It is similar to the previous sequence , Also with the help of the stack . The general idea is , If the current root node is not empty or the stack is not empty , Execute the following loop ：
If the current root node is not empty , Execute the following loop ：
- Stack the current node , And the current node is set as its left node .
- If the current root node is empty , Take out the first element in the stack , That is, the leftmost child node that has not been traversed is printed , Then set the current node as its right node , It is equivalent to accessing the left subtree and the current node , Then we visit the right subtree .
import java.util.Stack;
public class InOrder {
public static void main(String[] args) {
InOrder order = new InOrder();
order.inOrder(order.initTree());
}
public void inOrder(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
// Stack the current node
stack.push(root);
// Traversing its left subtree
root = root.left;
}
// Out of the stack
root = stack.pop();
// The current node is traversed
System.out.print(root.val + " ");
// Right node
root = root.right;
}
}
// Construct initialization tree
public TreeNode initTree() {
// Construct a binary tree
TreeNode treeNode = new TreeNode(1);
treeNode.left = new TreeNode(2);
treeNode.right = new TreeNode(3);
treeNode.left.left = new TreeNode(4);
treeNode.left.right = new TreeNode(5);
treeNode.right.left = new TreeNode(6);
return treeNode;
}
}
Binary tree uses postorder traversal recursive solution
The writing of recursion is not very different from the previous sequence and the middle sequence , But the order of recursion is different , Similar to the previous ：
public class PostOrder {
public static void main(String[] args) {
PostOrder order = new PostOrder();
order.postOrder(order.initTree());
}
public void postOrder(TreeNode root) {
if (root != null) {
// The left subtree
postOrder(root.left);
// Right subtree
postOrder(root.right);
// Print the root node
System.out.print(root.val + " ");
}
}
// Construct initialization tree
public TreeNode initTree() {
// Construct a binary tree
TreeNode treeNode = new TreeNode(1);
treeNode.left = new TreeNode(2);
treeNode.right = new TreeNode(3);
treeNode.left.left = new TreeNode(4);
treeNode.left.right = new TreeNode(5);
treeNode.right.left = new TreeNode(6);
return treeNode;
}
}
Binary tree uses post ordered non recursive algorithm
import java.util.*;
public class PostOrder {
public static void main(String[] args) {
PostOrder order = new PostOrder();
order.postOrder(order.initTree());
}
public void postOrder(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
// Join the root node first
stack.add(root);
// Loop to determine whether the stack is empty
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
res.add(0, node.val);
// Press in the left side first , Press in the right side again , When you push the stack , It will be on the right and then on the left
if (node.left != null) {
stack.add(node.left);
}
if (node.right != null) {
stack.add(node.right);
}
}
for (Integer item : res) {
System.out.print(item + " ");
}
}
// Construct initialization tree
public TreeNode initTree() {
// Construct a binary tree
TreeNode treeNode = new TreeNode(1);
treeNode.left = new TreeNode(2);
treeNode.right = new TreeNode(3);
treeNode.left.left = new TreeNode(4);
treeNode.left.right = new TreeNode(5);
treeNode.right.left = new TreeNode(6);
return treeNode;
}
}
Level traversal of binary tree
import java.util.ArrayList;
import java.util.LinkedList;
public class LevelTree {
public static void main(String[] args) {
TreeNode root = initTree();
ArrayList<Integer> results = print(root);
results.forEach(e -> System.out.print(e + " "));
}
// Print hierarchically
public static ArrayList<Integer> print(TreeNode root) {
// Result set
ArrayList<Integer> results = new ArrayList<>();
// The bidirectional queue
LinkedList<TreeNode> queue = new LinkedList<>();
if (root != null) {
// Add the root node to the queue
queue.add(root);
// Loop to determine if the queue is empty
while (!queue.isEmpty()) {
// Take out the first element
TreeNode treeNode = queue.pollFirst();
// Add result set
results.add(treeNode.val);
// If the left subtree is not empty , Is added to the end of the queue
if (treeNode.left != null) {
queue.add(treeNode.left);
}
// If the right subtree is not empty , Is added to the end of the queue
if (treeNode.right != null) {
queue.add(treeNode.right);
}
}
}
return results;
}
// Construct initialization tree
public static TreeNode initTree() {
// Construct a binary tree
TreeNode treeNode = new TreeNode(1);
treeNode.left = new TreeNode(2);
treeNode.right = new TreeNode(3);
treeNode.left.left = new TreeNode(4);
treeNode.left.right = new TreeNode(5);
treeNode.right.left = new TreeNode(6);
return treeNode;
}
}
According to two traversal orders , Reconstruct the binary tree
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
public class ConstructTree {
public static void main(String[] args) {
int[] pre = {
1, 2, 4, 7, 3, 5, 6, 8 };
int[] in = {
4, 7, 2, 1, 5, 3, 8, 6 };
TreeNode root = constructBinaryTree(pre, in);
preOrder(root);
}
public static TreeNode constructBinaryTree(int[] pre, int[] in) {
if (pre == null || pre.length == 0 || in == null || in.length == 0) {
return null;
}
return constructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
}
static TreeNode constructBinaryTree(
int[] pre,
int startPre,
int endPre,
int[] in,
int startIn,
int endIn
) {
// If you don't meet the conditions, return to null
if (startPre > endPre || startIn > endIn) {
return null;
}
// Build root node
TreeNode root = new TreeNode(pre[startPre]);
for (int index = startIn; index <= endIn; index++) {
if (in[index] == pre[startPre]) {
// Build the left subtree
root.left =
constructBinaryTree(
pre,
startPre + 1,
startPre + (index - startIn),
in,
startIn,
index - 1
);
// Build the right subtree
root.right =
constructBinaryTree(
pre,
(index - startIn) + startPre + 1,
endPre,
in,
index + 1,
endIn
);
break;
}
}
return root;
}
// Preorder traversal binary tree
public static void preOrder(TreeNode root) {
if (root != null) {
// Print the root node
System.out.print(root.val + " ");
// Visit the left subtree
preOrder(root.left);
// Visit the right subtree
preOrder(root.right);
}
}
}
The height of the apple tree ( Find the height of the binary tree )
public class TreeDepth {
public static void main(String[] args) {
TreeNode root = initTree();
System.out.println(" The height of the tree is ：" + treeDepth(root));
}
public static int treeDepth(TreeNode root) {
// If the node is null, return 0
if (root == null) return 0;
return Math.max(treeDepth(root.left), treeDepth(root.right)) + 1;
}
// Initialize tree structure
public static TreeNode initTree() {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(6);
root.left.right.left = new TreeNode(7);
return root;
}
}
Mirror , You take a picture of this tree 
public class MirrorTree {
public static void main(String[] args) {
TreeNode root = initTree();
mirror(root);
preOrder(root);
}
public static void mirror(TreeNode root) {
if (root == null) {
return;
} else {
root = reverse(root);
}
}
// Turn left and right
public static TreeNode reverse(TreeNode root) {
if (root == null) {
return root;
} else {
// First, reverse the left and right subtrees respectively , And save
TreeNode left = reverse(root.right);
TreeNode right = reverse(root.left);
root.left = left;
root.right = right;
return root;
}
}
// Initialize tree structure
public static TreeNode initTree() {
TreeNode root = new TreeNode(8);
root.left = new TreeNode(6);
root.right = new TreeNode(1);
root.left.left = new TreeNode(5);
root.left.right = new TreeNode(7);
root.right.left = new TreeNode(9);
root.right.right = new TreeNode(2);
return root;
}
// Preorder traversal binary tree
public static void preOrder(TreeNode root) {
if (root != null) {
// Print the root node
System.out.print(root.val + " ");
// Visit the left subtree
preOrder(root.left);
// Visit the right subtree
preOrder(root.right);
}
}
}
import java.util.Stack;
public class MirrorTree {
public static void main(String[] args) {
TreeNode root = initTree();
mirror(root);
preOrder(root);
}
public static void mirror(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
// First add the root node to the stack
stack.push(root);
// Determine whether the root node is empty
while (!stack.isEmpty()) {
// Pop up the first node
TreeNode node = stack.pop();
// Save the left subtree
TreeNode tempNode = node.left;
// Replace the left subtree with the right subtree
node.left = node.right;
// The right subtree is replaced by the previous left subtree
node.right = tempNode;
// Add left node
if (node.left != null) {
stack.push(node.left);
}
// Add the right node to the stack
if (node.right != null) {
stack.push(node.right);
}
}
}
// Initialize tree structure
public static TreeNode initTree() {
TreeNode root = new TreeNode(8);
root.left = new TreeNode(6);
root.right = new TreeNode(1);
root.left.left = new TreeNode(5);
root.left.right = new TreeNode(7);
root.right.left = new TreeNode(9);
root.right.right = new TreeNode(2);
return root;
}
// Preorder traversal binary tree
public static void preOrder(TreeNode root) {
if (root != null) {
// Print the root node
System.out.print(root.val + " ");
// Visit the left subtree
preOrder(root.left);
// Visit the right subtree
preOrder(root.right);
}
}
}
The substructure of a tree
public class SubTree {
public static void main(String[] args) {
TreeNode root1 = initTree1();
TreeNode root2 = initTree2();
System.out.println(" Trees 2 Is it a tree 1 The subtree of ：" + hasSubtree(root1, root2));
}
public static boolean hasSubtree(TreeNode root1, TreeNode root2) {
// Just one for null, Then return to false
if (root1 == null || root2 == null) {
return false;
}
// Compare from the current root node
if (sameTree(root1, root2)) {
return true;
} else {
// Otherwise, use left subtree or right subtree and root2 matching
return hasSubtree(root1.left, root2) || hasSubtree(root1.right, root2);
}
}
public static boolean sameTree(TreeNode root1, TreeNode root2) {
// Here we need to pay attention to , When the substructure traversal ends , Should return to true
if (root2 == null) {
return true;
}
if (root1 != null) {
// Two nodes are equal
if (root1.val == root2.val) {
// Recursively judge that the left subtree and the right subtree also match
return (
sameTree(root1.left, root2.left) && sameTree(root1.right, root2.right)
);
} else {
return false;
}
}
return false;
}
// Construct master tree
public static TreeNode initTree1() {
TreeNode root = new TreeNode(8);
root.left = new TreeNode(6);
root.right = new TreeNode(1);
root.left.left = new TreeNode(5);
root.left.right = new TreeNode(7);
root.right.left = new TreeNode(9);
root.right.right = new TreeNode(2);
return root;
}
// Construct subtree
public static TreeNode initTree2() {
TreeNode root = new TreeNode(6);
root.left = new TreeNode(5);
root.right = new TreeNode(7);
return root;
}
}
The nearest common ancestor node of different nodes
public class CommonAncestor {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
// Initialize the node to be found
TreeNode p = new TreeNode(4);
TreeNode q = new TreeNode(5);
root.left.left = p;
root.left.right = q;
root.right.left = new TreeNode(6);
TreeNode commonNode = lowestCommonAncestor(root, p, q);
// Output common node
System.out.println("common node: " + commonNode.val);
}
public static TreeNode lowestCommonAncestor(
TreeNode root,
TreeNode p,
TreeNode q
) {
// If any one equals null, Go straight back to
if (root == null || p == root || q == root) {
return root;
}
// Look in the left subtree
TreeNode left = lowestCommonAncestor(root.left, p, q);
// Look in the right subtree
TreeNode right = lowestCommonAncestor(root.right, p, q);
// If both sides find
if (left != null && right != null) {
// Return to their nearest common ancestor
return root;
}
return left == null ? right : left;
}
}
The path sum of the tree （ backtracking ）
generally speaking , Every node in a binary tree , Are storing their own data , The data can be numbers , It could be something else . Suppose we have a binary tree and an integer , Print out all paths where the sum of node values in the binary tree is an input integer in dictionary order . The so-called path , That is, a path is formed from the root node of the tree down to the node passing through the leaf node .
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.stream.Collectors;
public class FindPathForTree {
public static void main(String[] args) {
TreeNode root = initTree1();
ArrayList<ArrayList<Integer>> results = findPath(root, 18);
results
.stream()
.forEach(
r -> {
r.forEach(e -> System.out.print(e + " --> "));
System.out.println("");
}
);
}
public static ArrayList<ArrayList<Integer>> findPath(
TreeNode root,
int target
) {
// Result set
ArrayList<ArrayList<Integer>> results = new ArrayList<>();
// queue
LinkedList<Integer> queue = new LinkedList<>();
int sum = 0;
if (root != null) {
// Start at the root node
addDatas(root, target, results, queue, sum);
}
return results;
}
public static void addDatas(
TreeNode root,
int target,
ArrayList<ArrayList<Integer>> results,
LinkedList<Integer> queue,
Integer sum
) {
if (root != null) {
// Accumulate the current value
sum = sum + root.val;
// Add to queue
queue.add(root.val);
// If and meet , And it's a leaf node
if (sum == target && root.left == null && root.right == null) {
addResult(results, queue);
} else {
// Recursive left subtree
addDatas(root.left, target, results, queue, sum);
// Recursive right subtree
addDatas(root.right, target, results, queue, sum);
}
// processed , Pop up the last value , Equivalent to backtracking
queue.pollLast();
// The value of and also needs to be backtracked
sum = sum - root.val;
}
}
public static void addResult(
ArrayList<ArrayList<Integer>> results,
Queue<Integer> queue
) {
// Add results to the final result set
ArrayList<Integer> result = (ArrayList<Integer>) queue
.stream()
.collect(Collectors.toList());
results.add(result);
}
// Construct trees
public static TreeNode initTree1() {
TreeNode root = new TreeNode(8);
root.left = new TreeNode(6);
root.right = new TreeNode(1);
root.left.left = new TreeNode(5);
root.left.right = new TreeNode(7);
root.right.left = new TreeNode(9);
root.right.right = new TreeNode(2);
return root;
}
}
Balanced binary trees
We all know , Balanced binary tree is a special kind of binary tree , Balanced binary trees （Balanced Binary Tree）, It has the following properties ： It is an empty tree or the absolute value of the height difference between its left and right subtrees does not exceed 1, And both the left and right subtrees are a balanced binary tree .
public class BalanceTree {
// Test code
public static void main(String[] args) {
// Construct a binary tree
TreeNode treeNode = new TreeNode(1);
treeNode.left = new TreeNode(2);
treeNode.right = new TreeNode(3);
treeNode.left.left = new TreeNode(4);
treeNode.left.right = new TreeNode(5);
treeNode.right.left = new TreeNode(6);
treeNode.right.right = new TreeNode(7);
boolean result = isBalance(treeNode);
System.out.println(result);
}
public static boolean isBalance(TreeNode root) {
if (root != null) {
// The left subtree
int left = deep(root.left);
// Right subtree
int right = deep(root.right);
// Absolute value of altitude difference
if (Math.abs(left - right) > 1) {
return false;
} else {
// Recursively determine left and right subtrees
return isBalance(root.left) && isBalance(root.right);
}
}
return true;
}
// Find the depth of the tree
public static int deep(TreeNode node) {
if (node == null) {
return 0;
}
// Maximum height of left and right subtrees +1
return Math.max(deep(node.left), deep(node.right)) + 1;
}
}
class TreeNode {
int val;
public TreeNode left;
public TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
边栏推荐
- S7-200SMART与FANUC机器人进行Profinet通信的具体方法和步骤
- Network address translation nat
- Unity sub thread calls UI of main thread
- 同花顺开户难么？网上开户安全么？
- Struggle, programmer chapter 45 tenderness is like water and a good time is like a dream
- unity和C＃中怎么去比较2个日期大小
- 本周四晚19：00战码先锋第7期直播丨三方应用开发者如何为开源做贡献
- Biden signs two new laws aimed at strengthening government cyber security
- C＃泛型_泛型类
- flutter video_player實現監聽和自動播放下一首歌曲
猜你喜欢
RealNetworks vs. Microsoft: the battle in the early streaming media industry
![[introduction to postgraduate entrance examination] analysis of postgraduate entrance examination data of Cyberspace Security Major of Beijing Jiaotong University from 2018 to 2022](/img/84/b572b3b80cc0dd1489076116cf0638.png)
[introduction to postgraduate entrance examination] analysis of postgraduate entrance examination data of Cyberspace Security Major of Beijing Jiaotong University from 2018 to 2022
Phpstudy 2016 build Pikachu range
利用图片实现APP元素定位sikulix
NF-ResNet：去掉BN归一化，值得细读的网络信号分析 | ICLR 2021
![Front and back management system of dessert beverage store based on SSM framework dessert mall cake store [source code + database]](/img/1b/9060d58d4dbb7f6f3c3a58959b7f14.png)
Front and back management system of dessert beverage store based on SSM framework dessert mall cake store [source code + database]
基于SSM框架实现的甜品饮品店前后台管理系统甜品商城蛋糕店【源码+数据库】
The diffusion model is crazy again! This time the occupied area is
No wonder the postgraduate entrance examination is so hot. These are the "hidden benefits" of Postgraduates!
Network address translation nat
随机推荐
Common real machine debugging plug-ins for unity commercial games
Perceptron of machine learning
Groovy语法介绍
How to compare the size of two dates in unity and C ＃
Closure of groovy
A thorough understanding of singleton
All famous network platforms in the world
Vscode个性化设置：让一个小萌妹陪你敲代码
网站存在的价值是什么？为什么要搭建独立站
C ＃ paging calculation total pages, current page data set
d的破坏与安全
[live broadcast review] battle code pioneer phase VI: build a test subsystem and empower developers to provide
unity和C＃中怎么去比较2个日期大小
Struggle, programmer -- Chapter 48 A thousand gold coins are bought like Fu. Who can complain about this situation
【毕业设计】基于半监督学习和集成学习的情感分析研究
Messiari annual report-2021
Front and back management system of dessert beverage store based on SSM framework dessert mall cake store [source code + database]
Groovy之闭包
Detailed explanation of CSAPP Labs
基于SSH框架甜品商城管理系统【源码+数据库】