当前位置:网站首页>Basic knowledge and examples of binary tree
Basic knowledge and examples of binary tree
2022-07-06 04:44:00 【KevinJune】
Catalog
1 Node structure of binary tree
1.1.2 Recursive version Preface Middle preface In the following order
1.1.3 Non recursive version of Preface Middle preface In the following order
2 Related concepts of binary tree and its implementation judgment
2.1 How to judge whether a binary tree is a search binary tree ?
2.2 How to judge whether a binary tree is a complete binary tree ?
2.3 How to judge whether a binary tree is full of binary trees ?
2.4 How to judge whether a binary tree is a balanced binary tree ?
3 Given the nodes of two binary trees node1 and node2, Find their lowest common ancestor node
4 Find the successor of a node in the binary tree
5 Serialization and deserialization of binary trees
1 Node structure of binary tree
class Node<V>{
V value;
Node left;
Node right;
}
Using recursive and non recursive methods to realize the preorder of binary tree 、 Middle preface 、 After the sequence traversal
How to complete the width first traversal of binary tree ( Common topics : Find the width of a binary tree )
1.1 Using recursive and non recursive methods to realize the preorder of binary tree 、 Middle preface 、 After the sequence traversal
1.1.1 Recursive order
void f(Node head)
{
if(head == null)
{
return;
}
f(head.left);
f(head.right);
}
analysis : It will return to the original function many times , Although nothing was done , Every node will be used 3 Time
1.1.2 Recursive version Preface Middle preface In the following order
All are processed by recursive order , Choose a different time to print .
The first order is to print out ( Around the head ):1,2,4,5,3,6,7 ( Print the first time you enter the function , The other two times will not be printed )
The middle order is printed out as ( Left head right ):4,2,5,1,6,3,7( Print the second time you enter the function , The other two times will not be printed )
The following sequence is printed out as ( Left and right ):4,5,2,6,7,3,1( Print the third time you enter the function , The other two times will not be printed )
1.1.3 Non recursive version of Preface Middle preface In the following order
Self stack .
First step :
① Pop up a node from the stack cur
② Print ( Handle )cur
③ First press the right child into the stack, and then press the left child into the stack ( If any )
④ go back to ① repeat
Subsequent steps :
① Pop up a node from the stack cur
② take cur Put it into the collection stack
③ First press the right child into the stack, and then press the left child into the stack ( If any )
④ go back to ① repeat
⑤ Until there is no number, the data will be ejected from the collection stack and printed in turn
Intermediate steps :
① Each subtree is stacked on the left border of the whole tree
② Print in the process of pop-up in turn
③ Stack the right tree of the pop-up node ( When entering the stack, it is also the left border of the whole tree )
④ go back to ②, If there is no data in the stack, go back to ①
ex. step1:1,2,4 Into the stack -> eject 4->4 There is no right tree back ①-> eject 2->2 There is a right tree , take 5 Into the stack ->····
1.2 How to complete the width first traversal of binary tree ( Common topics : Find the width of a binary tree )
Preorder traversal is the depth first traversal of binary trees
Width first traversal uses queues ,
Width first traversal step :
① Pop up a node from the queue list cur
② Print ( Handle )cur
③ First put the left child in the queue, and then put the right child in the queue ( If any )
④ go back to ① repeat
Find the width of a binary tree ( Hash table method )
Queue<Node> queue = new LinkedList<>();
queue.add(head);
HashMap<Node,Integer> levelMap = new HashMap<>(); // Store all nodes and their levels
levelMap.put(head,1); // The head node of the tree , The node level is 1
int curLevel = 1;
int curLevelNodes = 0;
int max = Integer.MIN_VALUE; // Minimum value of global variable ( Or take 0 Can also be )
while(!queue.isEmpty())
{
Node cur = queue.poll();
int curNodeLevel = levelMap.get(cur);// Get the current level
if(curNodeLevel == curLevel)
{
curLevelNodes++; // If the current level is at the level to be calculated , Then pop up the data ++
}
else
{
max = Math.max(max,curLevelNodes); // If not , Then the current level is the next , Start comparing the maximum width
curLevel++; // The level that needs to be calculated at the beginning is next level
curLevelNodes = 1; // Initialize the number of nodes of this level
}
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);
}
}
2 Related concepts of binary tree and its implementation judgment
2.1 How to judge whether a binary tree is a search binary tree ?
Search binary trees : For every sub tree , His left tree nodes are smaller , The nodes of his right tree are larger .
Method :
In the sequence traversal , What you get is an ascending data , It is a search binary tree
2.2 How to judge whether a binary tree is a complete binary tree ?
Perfect binary tree : The depth of a tree is one k There are n Of nodes Binary tree , Click from top to bottom for the nodes in the tree 、 Number from left to right , If the number is i(1≤i≤n) Node and Full binary tree Number is i The nodes of the binary tree have the same position , This binary tree is called a complete binary tree .
Method : Width traversal
① Any node has right or left , return false ( That is, it is not a complete binary tree )
② In dissatisfaction ① Under the circumstances , If you meet the first child or so, it's not all , Subsequent leaf nodes ( That is, there is no subtree )
③ return ① Continue to judge
2.3 How to judge whether a binary tree is full of binary trees ?
A full binary tree means that there are no child nodes in the last layer , A binary tree in which all nodes on each layer have two children .
A simple way to understand : Use a function to find the maximum depth of a binary tree D, Use a function to find the number of nodes of the binary tree N. Satisfy , It's full of binary trees
2.4 How to judge whether a binary tree is a balanced binary tree ?
Balanced binary trees : Balance tree (Balance Tree,BT) refer to , The height difference of any node's subtree is less than or equal to 1. And both the left tree and the right tree are balanced trees .
public static boolean isBalanced(Node head){
return process(head).isBalanced;
}
public static class ReturnType{
public boolean isBalanced;
public int height;
public ReturnType(boolean isB, int hei){
isBalanced = isB;
height = hei;
}
}
public static ReturnType process(Node x){
if( x == null)
{// base
return new ReturnType(true, 0);
}
ReturnType leftData = process(x.left);
ReturnType rightData = process(x.right);
int height = Math.max(leftData.height, rightData.height)+1;
boolean isBalanced = leftData.isBalanced&&rightData.isBalanced
&&Math.abs(leftData.height-rightData.height<2)
return new ReturnType(isBalanced, height);
}
3 Given the nodes of two binary trees node1 and node2, Find their lowest common ancestor node
Their thinking :
① First, establish the parent node of each node through the hash table
② Create hash table set1 Storage node1 Sequence of nodes
③ Give Way node2 Back up , And judge whether the new value is set1 in
4 Find the successor of a node in the binary tree
There is now a new binary tree node type as follows :
public class Node{
public int value;
public Node left;
public Node right;
public Node parent;
public Node(int val){
value = val;
}
}
This structure has one more point to the parent node than the normal binary tree node structure parent The pointer
So let's say I have one Node A binary tree of nodes of type , For each node in the tree parent Pointers all point correctly to their parent node , Head of the node parent Point to null.
I'm just going to give you a node in the binary tree node, Please implement return node The function of the subsequent nodes of .
A sequence traversed in the middle order of a binary tree ,node The next node of node Successor node .
Problem solving analysis :
①x When there is a right tree , here x The successor node of is the leftmost node on the right tree
②x When there is no right tree ,x Keep looking up , Judge whether it is currently the left node of the father , Until the time is y yes x Successor node
③ When x When it is the rightmost node , At this time, there is no successor node , Its successor node is null
public static Node getSuccessorNode(Node node){
if (node == null){
return node
}
if (node.right != null){
return getLeftMost(node.right);// situation ①
} else{ // situation ②
Node parent = node.parent;
while(parent != null && parent.left != node){// The current node is the right child of its parent 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;
}
5 Serialization and deserialization of binary trees
Is how a tree in memory becomes a string ( serialize ), How to change from string form to tree in memory ( Deserialization )
How to judge whether a binary tree is a subtree of another binary tree
With “#” Representational space ,“_” For the end
public static String serialByPre(Node head){
if(head == null){
return "#_";
}
String res = head.value + "_";
res += serialByPre(head.left);
res += serialByPre(head.right);
return res;
}
public static Node reconByPreString(String preStr){
String[] values = preStr.split("_");
Queue<String> queue = new LinkedList<String>();
for(int i = 0 ; i != value.length; i++){
queue.add(value[i]);
}
return reconByPreOrder(queue);
}
public static Node reconPreOrder(Queue<String> queue){
String value = queue.poll();
if(value.equals("#"){
return null;
}
Node head = new Node(Integer.valueOf(value));
head.left = reconPreOrder(queue);
head.right = reconPreOrder(queue);
return head;
}
6 creasing problem
Please put a piece of paper on the table , Then fold it in half from the bottom of the note to the top , Press out the creases and unfold .
Now the crease is concave , That is, the direction of the crease bulge points to the back of the paper .
If you fold the note in half from the bottom to the top twice in a row , Press out the creases and unfold , At this time, there are three creases on the right , From top to bottom are the lower creases 、 Lower crease and upper crease
Given an input parameter N, It means that the paper is folded in half from the bottom to the top N Time .
Please print the direction of all creases from top to bottom .
for example :N=1 when , Print down , N=2 when , Print : down down up
Problem solving analysis : That is, a left subtree is concave , The right subtree is a convex full binary tree
pubulic static void printAllFolds(int N){
printProcess(1,N,true);
}
// A recursive process , Came to a node
//i Is the number of layers of the node ,N The total number of floors , down == true concave , down == false Convex
public static void printProcess(int i, int N, boolean down){
if(i > N){
return;
}
printProcess(i + 1, N, true);
System.out.println(down ? " concave " : " Convex ");
printProcess(i + 1, N, false);
}
边栏推荐
- cdc 能全量拉去oracle 表嘛
- Ue5 small knowledge points to enable the setting of lumen
- Etcd database source code analysis -- etcdserver bootstrap initialization storage
- Case of Jiecode empowerment: professional training, technical support, and multiple measures to promote graduates to build smart campus completion system
- 优秀PM必须经历这3层蜕变!
- 麥斯克電子IPO被終止:曾擬募資8億 河南資產是股東
- ISP学习(2)
- Quatre méthodes de redis pour dépanner les grandes clés sont nécessaires pour optimiser
- newton interpolation
- Solutions: word coverage restoration, longest serial number, Xiaoyu buys stationery, Xiaoyu's electricity bill
猜你喜欢
Redis —— Redis In Action —— Redis 实战—— 实战篇一 —— 基于 Redis 的短信登录功能 —— Redis + Token 的共享 session 应用— 有代码
ue5 小知识点 开启lumen的设置
[Yu Yue education] reference materials of complex variable function and integral transformation of Northwestern Polytechnic University
Postman前置脚本-全局变量和环境变量
Easyrecovery靠谱不收费的数据恢复电脑软件
IPv6 comprehensive experiment
Basic explanation of turtle module - draw curve
Canal synchronizes MySQL data changes to Kafka (CentOS deployment)
Yyds dry inventory automatic lighting system based on CC2530 (ZigBee)
English Vocabulary - life scene memory method
随机推荐
[mathematical modeling] differential equation -- sustainable development of fishing industry
Crawler notes: improve data collection efficiency! Use of proxy pool and thread pool
How does computer nail adjust sound
Fuzzy -- basic application method of AFL
L'introduction en bourse de MSK Electronics a pris fin: 800 millions de RMB d'actifs de Henan étaient des actionnaires
Postman关联
Postman前置脚本-全局变量和环境变量
[Zhao Yuqiang] deploy kubernetes cluster with binary package
flink sql 能同时读多个topic吗。with里怎么写
SQL注入漏洞(MSSQL注入)
满足多元需求:捷码打造3大一站式开发套餐,助力高效开发
11. Intranet penetration and automatic refresh
Easyrecovery reliable and toll free data recovery computer software
The most detailed and comprehensive update content and all functions of guitar pro 8.0
It is also a small summary in learning
Dry goods collection | Vulkan game engine video tutorial
Fedora/REHL 安装 semanage
Flink kakfa data read and write to Hudi
Platformio create libopencm3 + FreeRTOS project
Patent | subject classification method based on graph convolution neural network fusion of multiple human brain maps