Basic concepts of binary tree

Preface ：

• In this paper, Knowledge of binary tree .

• Question answering ：New Young

• Data collected by bloggers New Young, In the serial .
• Reprint please indicate the source ：New Young

Trees

The concept of tree

Trees are a kind of nonlinear Data structure of , 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 .

• There is one Special nodes , It's called the root node , The root node There is no precursor node .
• Except for the root node , The rest of the nodes are divided into M(M>0) Disjoint sets T1、T2、……、T, And every set of them Ti(1<= i<= m) It is also a subtree with a structure similar to that of a tree .
• The root node of each subtree has and only has one precursor , There can be 0 One or more successors therefore , Trees are recursively defined Of
  

Related nouns of tree

Child node or child node ： A node contains a subtree of Root node The point is called the child node of this node ; Pictured above ：B yes A The child node of

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

Brother node ： Have the same Parent node The nodes of are called brother nodes ; Pictured above ：B、C It's a brother node

Cousin node ： The nodes of both parents on the same layer are cousins to each other ; Pictured above ：H、I Be brothers to each other

The ancestor of node ： From the root to all nodes on the branch through which the node passes ; Pictured above ：A Is the ancestor of all nodes

descendants ： Any node in a subtree with a node as its root is called the descendant of the node . Pictured above ： All nodes are A The descendants of

The forest ： from m（m>0） A disjoint tree Trees The collection of is called forest .

The degree of node ： A node contains subtree The number of nodes is called the degree of the node ; Pictured above ：A For the 6

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

Non terminal node or branch node ： Opposite to the leaf node , The degree is not for 0 The node of ; Pictured above ：D、E、F、G… Such nodes are branch nodes .

The degree of a tree ： In a tree , The degree of the largest node is called the degree of the tree ; Pictured above ：A Degree 6 Maximum , So the degree of the tree is zero 6

Hierarchy of nodes ： Consider that it may be an empty tree , There is no node . Here, it is agreed that the root node is the first layer . 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 height or depth of a tree ： The maximum level of nodes in the tree ; Pictured above ： The height of the tree is 4

The representation of a tree

There are many ways to represent trees ： Parenting , Child representation 、 The child's parent representation and the child's brother representation etc. . Let's briefly understand the most commonly used Child brother notation .

typedef int DataType;
struct Node
{
     
struct Node* _firstChild1; //  The first child node 
struct Node* _pNextBrother; //  Point to its next sibling node 
DataType _data; //  Data fields in nodes 
};

Tree references

It can be found that the physical structure of the tree is finite , The file system in our computer ：

Binary tree

Concept

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

1. Or is empty
2. It consists of a root node plus two binary trees called left subtree and right subtree

Be careful ：

1. Binary tree The degree of node The maximum is 2
2. The subtree of a binary tree has left and right branches , So a binary tree is an ordered tree .

Some rules of binary tree

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^（i-1) Nodes .----- This is a problem of finding subitems in an increasing sequence .

2. If the specified number of layers of the root node is 1, Then the depth is h The number of nodes in a binary tree is the largest 2^h -1 . ---- Incremental sequence summation problem .

3. Any binary tree , If the degree is 0 The number of leaf nodes is N0 , Degree is 2 The number of branch nodes is N2 , Always Yes N0＝ N2＋1

4. If the specified number of layers of the root node is 1, have n Of nodes Full binary tree The depth of the ,h= log2(N+1). ----------------2^h-1=N.

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

   1. if i>0,i The parent sequence number of the location node ：(i-1)/2;i=0,i Number the root node , No parent nodes
   2. if 2i+1<n, Left child serial number ：2i+1;2i+1>=n Otherwise no left child — The subscript crossing the line ,
   3. if 2i+2<n, Right child number ：2i+2;2i+2>=n Otherwise no right child — The subscript crossing the line

   ​

The composition type of binary tree

Special binary tree

Full binary tree ： Every layer of a binary tree all achieve The maximum number of nodes (2^h -1), The binary tree formed is ： Full binary tree

Perfect binary tree ：H A binary tree of layers , front H-1 The layer is full of binary trees , The first H The layer can be or not a full binary tree , But be sure to follow Strictly Of ： Insert the left node below , Rear right node , Insert nodes . Therefore, a full binary tree is a special complete binary tree .

Binary tree storage

Binary trees can generally use two structures to store , A sequential structure , A chain structure .

• Sequential storage ： Is to use arrays to store , Only suitable for expressing Perfect binary tree , Because it is not a complete binary tree, there will be a waste of space . The binary tree is stored in order, which is physically an array （ That is, continuous storage units in memory ）, Logically, it is a binary tree .
  

• Chain store ： adopt Left and right children To store binary trees . shortcoming ： It's hard to find parent nodes .
  
  ​

subject

1. A binary tree has 399 Nodes , Among them is 199 The individual degree is 2 The node of , Then the number of leaf nodes in the binary tree is （ ）
   A There is no such binary tree
   B 200
   C 198
   D 199

answer ：B. Two fork tree , Degree is 0 The eternal ratio of is 2 One more . So the leaf nodes have 200 individual ,200+199=399, The binary tree exists .

2. In the following data structure , What is not suitable for sequential storage structure is （ ）

   A Incomplete binary tree
   B Pile up
   C queue
   D Stack

   answer ：A. Array form is generally suitable for Perfect binary tree , Don't waste too much space , But it will not waste more .

3. 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

answer :A. Set the degree as 0 For the N0 individual , Degree is 2 For the N2 individual , The possible degree of existence in a complete quadratic tree is 1 Of , So set it as N1;

​ N0=N2+1;

2N=N2+N0+N1

2N=2N0-1+N1;

because N1 Only in 0 and 1 The value of , And we can know from the law of parity ,N1 Necessary for 1.

2N=2N0,N0=N;

​