Do you really know binary tree? (Part I)

Before we talk about binary trees, let's first understand the concept of trees , 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 .

· There is a special node , It's called the root node , The root node has no precursor node

· Except for the root node , The rest of the nodes are divided into M(M>0) Disjoint sets T1、T2、……、Tm, 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 defined recursively .

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

The concept of trees

Degree of node ： The number of subtrees a node contains is called the degree of the node ; Pictured above ：A For the 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 ;

Non terminal node or branch node ： The degree is not for 0 The node of ; Pictured above ：D、E、F、G... Such nodes are branch 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 ;

Brother node ： Nodes with the same parent are called siblings ; Pictured above ：B、C It's a brother node ;

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;

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 height or depth of a tree ： The maximum level of nodes in the tree ; Pictured above ： The height of the tree is 4;

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 collection of trees that do not intersect each other is called a forest ;

The representation of a tree

Tree structure is more complex than linear table , It's more troublesome to store and represent , Since the value field is saved , Also save the relationship between nodes , In practice, there are many representations of trees, such as ： Parenting 、 Child representation 、 The child's parent representation and the child's brother representation . Here I will briefly introduce the most commonly used child brother expression .

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

};

  The use of trees in practice

Concept and structure of 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. The degree of nonexistence of binary trees is greater than 2 The node of

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

 3. A binary tree can be an empty tree , You can have only the root node , There can be only left subtree, only right subtree, or both left and right subtrees

Special binary tree

1. Full binary tree ： A binary tree , If the number of nodes in each layer reaches the maximum , Then this binary tree is full of binary trees . in other words , If the number of layers of a binary tree is K, And the total number of nodes is -1 , Then it's full of binary trees . Every floor is full （ The first k layer , This floor has Nodes are full ）.

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 The nodes are paired one by one It should be called a complete binary tree . It should be noted that a full binary tree is a special kind of complete binary tree . front k-1 The layers are full , The last layer of discontent , But the last layer is continuous from left to right .

  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 k There is a maximum of Nodes .

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

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 , Then there are n0＝n2 ＋1, That is to say, the degree is 0 The node ratio of is always 2 One more node .

4. If the specified number of layers of the root node is 1, have n The depth of a full binary tree of nodes ,h= . .

5. Those who have n Complete binary tree of nodes , If all nodes are in the array order from top to bottom and from left to right 0 Numbered starting , On the other hand 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

3. if 2i+2<n, Right child number ：2i+2,2i+2>=n Otherwise no right child

Binary tree storage structure

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

1. Sequential storage

Sequential structure storage is to use arrays to store , Generally, arrays are only suitable for representing complete binary trees , Because it is not a complete binary tree, there will be a waste of space . In reality, only heap will use array to store . The binary tree is stored in order, which is physically an array , Logically, it is a binary tree .

 2. Chain store

The chain storage structure of binary tree refers to the use of linked list to represent a binary tree , Chain is used to indicate the logical relationship of elements . The usual method is that each node in the linked list consists of three fields , Data fields and left and right pointer fields , The left and right pointers are used to give the storage address of the chain node where the left child and the right child of the node are located . Chain structure can be divided into binary chain and trigeminal chain .

                          Binary list                                                                     Trident linked list

typedef int BTDataType;

// Binary chain

struct BinaryTreeNode

{

        struct BinTreeNode* _pLeft; // Point to the left child of the current node

        struct BinTreeNode* _pRight; // Point to the right child of the current node

        BTDataType _data; // Current node value range

}

// Trident chain

struct BinaryTreeNode

{

        struct BinTreeNode* _pParent; // Points to the parent of the current node

        struct BinTreeNode* _pLeft; // Point to the left child of the current node

        struct BinTreeNode* _pRight; // Point to the right child of the current node

        BTDataType _data; // Current node value range

};