Technology Sharing

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

This article will start with the concepts related to trees and binary trees to help us further study binary trees.

🌈个人主页：It's the waiter.
🌈C语言笔记专栏：C language notes
🌈C++笔记专栏： C++ Notes
🌈初阶数据结构笔记专栏： Beginner Data Structure Notes

🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅

1. Tree concept and structure

A tree is a nonlinear data structure consisting ofn(n>=0)A finite number of nodes form a hierarchical set, however, the tree is not very valuable in practice, but the binary tree is of great practical value (the reason why this set is called a tree is that it has its roots facing upwards and its leaves facing downwards, which looks very much like a tree)

• There is a special node, called the root node, which has no predecessor node.
• Except the root node, the remaining nodes are divided intoM(M>0)mutually disjoint setsT1、T2、....、Tm, where each setTi(1<=i<=m)This is another subtree with a structure similar to a tree. The root node of each subtree has one and only one predecessor and can have zero or more successors.
• The tree is a recursive definition, and at the same time it is important to note that in the tree structureThere cannot be any intersection between subtrees, otherwise it is not a tree structure.

1.1 Tree-related concepts

• Degree of node: The number of subtrees a node contains is called the degree of the node; as shown in the figure above: A is 6
• Leaf node or terminal node: A node with a degree of 0 is called a leaf node; As shown in the figure above: nodes B, C, H, I... are leaf nodes
• Non-terminal nodes or branch nodes: Nodes with a degree not equal to 0; As shown in the figure above: D, E, F, G... and other nodes are branch nodes
• Parent node or parent node: If a node has child nodes, then this node is called the parent node of its child nodes; As shown above: A is the parent node of B
• Child node or subnode: The root node of a subtree contained in a node is called the child node of the node; As shown in the figure above: B is the child node of A
• Brother Node: Nodes with the same parent node are called sibling nodes; As shown in the figure above: B and C are sibling nodes
• Degree of tree: In a tree, the degree of the largest node is called the degree of the tree; As shown in the figure above: the degree of the tree is 6
• Node hierarchy: Starting from the root, the root is the first layer, the child nodes of the root are the second layer, and so on
• Height or depth of the tree: The maximum level of nodes in the tree; As shown above: The height of the tree is 4
• Cousin Node: Nodes whose parents are on the same layer are cousins; as shown in the figure above: H and I are sibling nodes
• Ancestors of a node: All nodes on the branch from the root to the node; as shown above: A is the ancestor of all nodes
• Descendants: Any node in a subtree with a node as its root is called a descendant of that node. As shown in the figure above: All nodes are descendants of A.
• forest: A collection of m (m>0) disjoint trees is called a forest

2. Storage Representation of Trees

Since the tree structure is more complex than the linear table, the storage method is also more complicated. It is necessary to save both the value range and the relationship between nodes.

Here are some methods based on previous knowledge:

• Each child has an address and can store data through a pointer array (the space is fixed, and there is a cost and space problem when applying for new space)
• For the first method optimization, the pointer array is used as a sequential list to store children, which solves the problem of fixed space.
• Recommended commonly used solution: Left child, right brother method (the eldest child takes the second child, the second child takes the third child, without tiring both parents)

typedef int DataType;
struct Node
{
    struct Node* _firstChild1; // 第一个孩子结点
    struct Node* _pNextBrother; // 指向其下一个兄弟结点
    DataType _data; // 结点中的数据域
};
1
2
3
4
5
6
7

Of course, it is not limited to the above methods. There are also parent representation, child representation, child-parent representation, and child-sibling representation. Here we will briefly understand the most commonly used ones.Child sibling representation

3. Binary Tree Concept

A binary tree is a finite set of nodes. There are two possible cases:

1. Empty Tree
2. It consists of a root node plus two binary trees called left subtree and right subtree (the subtree may be empty)

Two conclusions can be drawn from the figure:

1. There is no node with degree greater than 2 in a binary tree.

2. The subtrees of a binary tree are divided into left and right, and the order cannot be reversed, so the binary tree is an ordered tree

Notice:For any binary tree, it is composed of the following situations (The empty tree case is the easiest to forget)

3.1 Binary trees in reality (you have to bow down to them when you see them)

4. Special Binary Tree

• Full Binary Tree: A binary tree is a full binary tree if the number of nodes in each layer reaches the maximum value. In other words, the number of levels of a binary tree is K, and the total number of nodes is 2^K-1, then it is a full binary tree
• Complete Binary Tree:Complete binary tree is a very efficient data structure. Complete binary tree is derived from full binary tree. For a binary tree with height K and n nodes, it is called a complete binary tree if and only if each node corresponds one-to-one with the nodes numbered from 1 to n in the full binary tree with height K.

In brief summary:

• Every level of a full binary tree is full

• If the height of a complete binary tree is n, then the first n-1 layers are full, but the last layer is not necessarily full.But it must be continuous from left to right

• A complete binary tree is a very efficient data structure. A full binary tree is a special type of complete binary tree.

• Necessary and sufficient conditions for a full binary tree to be a complete binary tree

4.1 Not a complete binary tree

This is an ordinary binary tree, which is not continuous from left to right.

5. Storage structure of binary tree

Binary trees can generally be stored in two structures: a sequential structure and a chain structure.

5.1 Sequential Storage

Sequential structure storage is to use arrays to store,Generally, arrays are only suitable for representing complete binary trees., because if the binary tree is not full, there will be a waste of space. In reality, only heaps use arrays to store data. Binary tree sequential storage is physically an array and logically a binary tree. In the following questions, we need to solve a problem based on the combination of the physical array and the logical binary tree.

5.2 The relationship between parent and child nodes (important)

• leftchild = parent * 2 + 1;

• rightchild = paretn * 2 +2;

• parent = (child - 1) / 2;(Does not distinguish between left and right children)

• Regarding the third point, based on my personal reasoning,leftchildSubscript split intoleftchild- 1and1,forleftchild-1forparentSubscript twice, for(child - 1) / 2The operation willleftchildDisassemble it into1The integer of the part divided by 2 is 0.leftchild -1Part of it can be seen asleftchild,andrightchild与leftchild相差1,becauserightchild = leftchild - 1and through the aboveleftchild - 1 ~= leftchild, it can be inferred thatrightchild = leftchild(在进行/2运算，取整数情况下)

5.3 Chain Storage

The chain storage structure of a binary tree means that a binary tree is represented by a linked list, that is, a 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, the data field and the left and right pointer fields. The left and right pointers are used to give the storage address of the link point where the left child and right child of the node are located. The chain structure is divided into binary chain and ternary chain. Currently, we are generally learning binary chains. Later, we will learn higher-order data structures such as red-black trees and use ternary chains.

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
        struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
    struct BinTreeNode* _pParent; // 指向当前节点的双亲
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5.4 Summary

Sequential structure storage is stored through arrays.Generally speaking, arrays are only suitable for complete binary trees. Incomplete binary trees are not suitable for array structure storage. Ordinary binary trees are only suitable for chain structure storage.However, in reality, only when a heap is used will an array be used for storage, and most of the storage is still done through a linked structure.

the reason is:

1. First of all, we need to know that the binary tree has its own special logical structure. Unlike other data structures, it is not suitable for adding, deleting, checking and modifying heap data because it consumes a lot of space and has more complicated logic.If such a complex structure is used to store data, it is not without value., it is better to use a sequential table to store data from the beginning. In general, the structure of a binary tree is recursive, and it is more troublesome to implement it with non-recursion.
2. The density of elements stored in an ordinary binary tree may be very low, and the continuous storage structure will cause a lot of space waste.
3. The heap is sorted according to the "heap attribute", which determines the position of the nodes in the tree (explained in the introduction to the heap below)

---

The above is all the content of this article. Thank you for watching! Here are the notes on the entry-level data structure of the waiter. I hope it will be helpful for you in learning the entry-level data structure!