Take you off [data structure] Chengwang Chapter 8: binary tree

Preface

A tree structure

Tree is a kind of nonlinear data structure , It is from n（n>=0） Finite nodes make up a set with hierarchical relations . It's called a tree because it looks like an upside down tree , That is to say, it is root up , And leaf down .

characteristic :

1. There's a special node , Called the root node , The root node does not have a precursor node ,A It's the root node

2. Except for the root node , The remaining nodes are divided into M(M > 0) Disjoint sets T1、T2、......、Tm, And every set of them Ti (1 <= i <= m) Another subtree similar to a tree . The root node of each subtree has and has only one precursor , There can be 0 One or more successors

B C D E...... It's all a collection .

B It's a subtree , Its precursor is A

Be careful : In the tree structure , There can be no intersection between subtrees , Otherwise, it is not a tree structure

Good place to draw the red line

3. Trees are defined recursively .

Degree of node ： The number of subtrees a node contains is called the degree of the node ; Pictured above ：A For the 6

The maximum depth is the height of the tree Pictured above :A The depth is 1,E The depth is 2,J The depth is 3,Q The depth is 4

The degree of a tree ： In a tree , The degree of the largest node is called the degree of the tree ; Pictured above ： The degree of the tree is 6

Leaf node or terminal node ： Degree is 0 A node of is called a leaf node ; Pictured above ：B、C、H、I... Equal nodes are leaf nodes

Parent node or parent node ： If a node has child nodes , This node is called the parent of its child ; Pictured above ：A yes B Parent node

Child node or child node ： The root node of the subtree that a node contains is called the child node of the node ; Pictured above ：B yes A The child node of

Root node ： In a tree , Nodes without parents ; Pictured above ：A

Hierarchy of nodes ： Starting from the root , The root for the first 1 layer , The child node of the root is the 2 layer , And so on ;

The representation of trees

  Tree structure is more complex than linear table , It's more troublesome to store and represent , In fact, there are many representations of trees , Such as ： Parenting , Child representation 、 Child brother notation and so on . Let's have a simple understanding of the most commonly used child brother representation .

A yes val value

child It's a quote from the first child , The first child is B, So I quoted B This node

Node nextBrother Next brother : because A Root node , No brothers , therefore brother The value of is null

To B after ,B My first child was D, Brother is C, hypothesis C No brothers ,brother The value of is also null

And so on

The application of tree

File system management ( Directories and files )

Binary tree

A binary tree is a finite set of nodes , This collection :

1. Or is empty

2. Or it's a root node plus two binary trees called left and right subtrees .

Each node of a binary tree has either 0 A child , Or there is 1 A child , Or have two children <=2

A tree , If it's a binary tree , Then each of his subtrees is a binary tree

The degree of nonexistence of binary trees is greater than 2 Cut off

The subtree of a binary tree has left and right branches , The order cannot be reversed , So a binary tree is an ordered tree

Two special binary trees  

1. Full binary tree : A binary tree , If the node number of each layer reaches the maximum , Then this binary tree is a full binary tree . in other words , If the number of layers of a binary tree is K, And the total number of nodes is 2 Of k The power minus 1 , Then it's full of binary trees .

2. Perfect binary tree : A complete binary tree is an efficient data structure , A complete binary tree is derived from a full binary tree . For a depth of K Of , Yes n A binary tree of nodes , If and only if each of its nodes has a depth of K From the full binary tree of 1 to n A complete binary tree is called when its nodes correspond to each other . It should be noted that a full binary tree is a special kind of complete binary tree .

Properties of binary trees  

1. If the specified number of layers of the root node is 1, Then the second of a non empty binary tree i There is a maximum of

2. If it is specified that the depth of a binary tree with only root nodes is 1, Then the depth is K The number of nodes in a binary tree is the largest

3. Any binary tree , If the number of leaf nodes is n0, Degree is 2 The number of non leaf nodes is n2, Then there are n0＝n2＋1 

1 and 2 Relatively simple , An equiratio sequence can be derived

Let's deduce the formula 3,

Suppose the binary tree has N Nodes , A binary tree , or n0( Represents a leaf node ), or n1, want N2

therefore :N = n0+n1+n2

One has N Tree of nodes , Yes N-1 side

The total number of edges equals :

Degree is 0 The node of , produce 0 side

Degree is 1 The node of , produce n1 side

Degree is 2 The node of , produce n2 side

N-1 = n1 + 2*n2

n0+n1+n2 = n1 + 2*n2 -1

n0 = n2 + 1

Come to the conclusion : Any binary tree , The leaf node ratio is 2 One more node

4. have n The depth of a complete binary tree of nodes k by Round up

The figure below is rounded up

Let's look at a problem :

In possession of 2n In a complete binary tree of nodes , The number of leaf nodes is ()

A:n

B:n+1

C:n-1

D:n/2

choose A

According to the conclusion we put forward above : Any binary tree , The leaf node ratio is 2 One more node

5. Those who have n Complete binary tree of nodes , If all nodes are sorted from top to bottom and from left to right 0 Numbered starting , Then for the serial number is i There are ：

if i>0, Parental serial number ：(i-1)/2;i=0,i Number the root node , No parent nodes

explain :
 

Suppose the subscript of the child node is i, Then the subscript of the parent node is :

hypothesis Ii by 5, The father node is 2, hypothesis i by 6, The father node is 2

(i-1)/2

(5-1)/2 = 2

(6-1)/2 = 2

if 2i+1<n, Left child serial number :2i+1, Otherwise no left child

if 2i+2<n, Right child number :2i+2, Otherwise no right child

explain :

Suppose the subscript of the parent node is i

Left the child :2i + 1

The right child :2i + 2

Binary tree storage  

The storage structure of binary tree is divided into ： Sequential storage and chain storage similar to linked list .

The chain storage of binary tree is referenced by nodes one by one , The common expressions are binary and trigeminal , As follows ：

binary : Child representation

Trident : The expression of children's parents

The creation of binary tree  

Premise : The creation of binary tree is a very complicated process , The previous knowledge is not enough to let you know about binary trees , So now create a binary tree , This creation method is only used in the early stage , Relatively simple , Not the right or common way to create .

Suppose you create this tree

class BTNode{
public char val;
public BTNode left;// Left child's quote
public BTNode right;// Right child's quote
public BTNode(char val){
this.val = val;
}
}
public class BinaryTree {
public BTNode root;// The root node is the root of a binary tree , Is not a root belonging to a node
public BTNode createTree(){
BTNode A = new BTNode('A');
BTNode B = new BTNode('B');
BTNode C = new BTNode('C');
BTNode D = new BTNode('D');
BTNode E = new BTNode('E');
BTNode F = new BTNode('F');
BTNode G = new BTNode('G');
BTNode H = new BTNode('H');
A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.left = F;
C.right = G;
E.right = H;
return A;
}
}

This is a simple way to create a binary tree

Traversal of binary tree

Traversal of binary tree , a key 》 All binary tree related topics , Basically, we need to solve problems through some kind of traversal .

1. The former sequence traversal （ Also called root first traversal ）

Print first when root is encountered , Print the left subtree , Print the right subtree

 2. In the sequence traversal

Print the left subtree first , Then print the root , Then print the right subtree

3. After the sequence traversal

Print the left subtree first , Then print the right subtree , Then print the root

Write a preorder traversal code ：

 // The former sequence traversal
public void preOrder(BTNode root){
if(root == null){
return;
}
System.out.println(root.val+ " ");
preOrder(root.left);
preOrder(root.right);
}

  recursively

The problem of binary tree is naturally written with recursion ,90%

Print the results :

Let's look at a problem :

144. Preorder traversal of two tree - Power button （LeetCode）

The first way to write code : Traversal ideas

class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<>();
pre(list,root);
return list;
}
public void pre(List<Integer> list,TreeNode root){
if(root != null){
list.add(root.val);
pre(list,root.left);
pre(list,root.right);
}
}
}

The second solution : Traversal ideas

class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null){
return list;
}
list.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
return list;
}
}

The third solution : Sub problem ideas

class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null){
return list;
}
list.add(root.val);
List<Integer> leftTree = preorderTraversal(root.left);
list.addAll(leftTree);
List<Integer> rightTree = preorderTraversal(root.right);
list.addAll(rightTree);
return list;
}
}

unfinished , To be continued ......