Tree and binary tree: storage structure of binary tree

Trees and binary trees ： Binary tree storage structure

The sequential storage structure of binary tree

Review the properties of binary trees 4, Complete binary tree nodes are numbered by sequence ：

The sequential storage structure of a complete binary tree

Sequential storage structure of incomplete binary tree

Characteristics of binary tree sequential storage structure ：

• about Perfect binary tree Come on , Its sequential storage is very suitable
• about General binary tree , Especially for those binary trees with many single branch nodes , Because only a few storage units may be used , Especially for degenerate binary trees （ That is, each branch node is a single branch ）, The waste of space is amazing
• In a sequential storage structure , It's easy to find parents and children at a node

The chain storage structure of binary tree

reference The child chain storage structure of the tree - The chain storage structure of binary tree
In the chain storage of binary tree , The types of nodes are defined as follows ：

typedef struct node {
    
	ElemType data;
	struct node *lchild,*rchild; // All points to binary trees ： Recursion 
}BTNode;

Characteristics of binary chain storage structure ：

• Except pointer , Binary chain Save storage space . The storage space occupied has nothing to do with the tree , It is only related to the number of nodes in the tree
• In a binary chain , It's easy to find a child at a node , But it is inconvenient to find his parents
• A tree is represented by a child sibling chain storage structure - Binary chain

In a binary chain , Number of null pointers ？

• n Nodes — 2n A pointer to a domain
• The number of branches is n-1 — The non empty finger field has n-1 individual
• Number of empty finger needle fields = 2n-(n-1) = n+1

Advantages and disadvantages of binary tree sequential storage and chain storage ：

One , Sequential storage

advantage ： It is more efficient to read a specified node O(0)

shortcoming ： It's a waste of space ( In the case of incomplete binary trees )

Two , Chain store

advantage ： The efficiency of reading a specified node is low O(nlogn)

shortcoming ： Relatively large binary trees waste less space

The sequential storage of binary trees , It is very convenient to find descendant nodes and ancestor nodes , But for ordinary binary trees , Sequential storage wastes a lot of storage space , It is also not conducive to the insertion and deletion of nodes . Therefore, sequential storage is generally used to store complete binary trees

The chain storage of binary tree saves storage space compared with sequential storage , When inserting or deleting nodes, you only need to modify the pointer , But it is inconvenient to find the specified node . However, ordinary binary trees usually use chain storage structure