Technology Sharing

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

1. The concept and structure of the tree

1.1 The concept of tree

A tree is aNonlinearThe data structure is a hierarchical set of n (n>=0) finite nodes.It is called a tree because it looks like an upside-down tree, meaning its roots are facing upwards and its leaves are facing downwards.

• Root node: The root node has no predecessor node.
• Except for the root node, the remaining nodes are divided into a subtree with a structure similar to a tree. The root node of each subtree has one and only one predecessor and can have 0 or more successors.
• Therefore, the tree isRecursive definitionof.

1.2 Tree-related concepts

• Degree of node: The number of subtrees a node contains is called the degree of the node; as shown above: A is 4
• Leaf node or terminal node: A node with a degree of 0 is called a leaf node; As shown in the figure above: B, F, G, D, H nodes are leaf nodes
• Non-terminal nodes or branch nodes: Nodes with a degree not equal to 0; As shown in the figure above: Nodes A, C, and E 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 above: the degree of the tree is 4
• 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;
• The height or depth of the tree: The maximum level of nodes in the tree; As shown above: The height of the tree is 3
• Cousin Node: Nodes whose parents are on the same layer are cousins; as shown in the figure above: F and G 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 mutually disjoint trees is called a forest;

1.3 Tree Representation

The tree structure is more complicated than the linear table, and it is more troublesome to store and represent.It is necessary to save both the value range and the relationship between nodes.In practice, there are many ways to represent trees, such as:Parent representation, child representation, child-parent representation, and child-sibling representationwait.

In the process of introducing the following storage structure, we use the following tree as an example.

1.3.1 Parent Representation

We assume that the nodes of the tree are stored in a set of continuous spaces, andIn each node, an indicator is attached to indicate the position of its parent node in the linked list.That is to say, in addition to knowing who it is, each node also knows where its parents are.

Data is the data field, which stores the data information of the node, and parent is the pointer field, which stores the index of the parent of the node in the array.
Below is the node structure definition code for our parent representation.

/*树的双亲表示法结点结构定义*/
#define MAX_TREE_SIZE 100
typedef int TElemType;	//树结点的数据类型，目前暂定为整型
/*结点结构*/
typedef struct TreeNode
{
	TElemType data;	//结点数据
	int parent;	//双亲位置
}TreeNode;
/*树结构*/
typedef struct
{
	TreeNode nodes[MAX_TREE_SIZE];	//结点数组
	int r, n;	//根的位置和结点数
}PTree;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

With this storage structure, we can easily find the parent node of a node based on its parent pointer.The time complexity is 0(1), until parent is -1, it means the root of the tree node is found. But if we want to know what the children of the node are, sorry, please traverse the entire structure.

1.3.2 Child-sibling representation

Just now we studied the storage structure of the tree from the perspective of the parent and from the perspective of the child. What if we look at it from the perspective of the brothers of the tree nodes? Of course, for a hierarchical structure like a tree, it is not enough to only study the brothers of the nodes. After observation, we found that for any tree, the first child of its node is unique if it exists, and its right brother is also unique if it exists. Therefore, we set two pointers, pointing to the first child of the node and the right sibling of this node.

/*树的孩子兄弟表示法结构定义*/
typedef struct TreeNode
{
	TElemtype data;
	struct TreeNode *firstchild, *rightsib;
} TreeNode,* pTreeNode;
1
2
3
4
5
6

1.4 Practical Applications of Trees

2. The concept and structure of binary tree

2.1 Concept

A binary tree is a finite set of nodes that:

• Or empty
• It consists of a root node plus two binary trees, also called left subtree and right subtree.

As can be seen from the above 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 a binary tree isOrdered Tree

Note: Any binary tree is composed of the following situations:

2.2 Special Binary Tree

1. Full Binary Tree: a binary tree,If the number of nodes in each layer reaches the maximum value, then the binary tree is a full binary tree.That is to say, if the number of layers of a binary tree is K and the total number of nodes is 2^k-1, then it is a full binary tree.
2. Complete Binary Tree: A complete binary tree is a very efficient data structure.A complete binary tree is derived from a full binary tree.A binary tree with a depth of K and n nodes is called a complete binary tree if and only if each of its nodes corresponds one-to-one with the nodes numbered from 1 to n in the full binary tree with a depth of K.A full binary tree is a special kind of complete binary tree.
   

2.3 Properties of Binary Trees

1. If the number of layers of the root node is set to 1, then the number of layers of a non-empty binary treeThere are at most 2^(i-1) on the i-th layer Nodes
2. If the number of layers of the root node is specified as 1, thenThe maximum number of nodes in a binary tree of depth h is 2^h-1
3. For any binary tree, ifThe number of leaf nodes with degree 0 is n0, and the number of branch nodes with degree 2 is n2, so n0 = n2 + 1
4. If the number of layers of the root node is specified as 1,The depth of a full binary tree with n nodes is h=log (n+1) (ps: log is based on 2, n+1 is the logarithm)
5. For a complete binary tree with n nodes, if all nodes are numbered starting from 0 in array order from top to bottom and from left to right, then for the node with serial number i, there are:
   • If i>0, the parent number of the node at position i is: (i-1)/2; if i=0, i is the root node number, no parent node
   • If 2i+1, 2i+1>=n otherwise there is no left child
   • If 2i+2, 2i+2>=n otherwise there is no right child

2.4 Storage structure of binary tree

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

1. Sequential storage
   Sequential structure storage is to useArraysTo store, usually using an arrayOnly suitable for representing complete binary trees, because it is not a complete binary tree, there will be a waste of space. In reality, only heaps use arrays for storage.Binary tree sequential storage is physically an array and logically a binary tree.
   2. Chain storage
   The chain storage structure of a binary tree means thatUsing a linked list to represent a binary tree, that is, using a chain to indicate the logical relationship of elements. **The usual method is that each node in a 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 node 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 generally study binary chains.
   

3. The sequential structure of binary trees and their implementation

Ordinary binary trees are not suitable for storage in arrays because there may be a lot of space waste.Complete binary trees are more suitable for sequential structure storageIn reality, we usually useA heap (a binary tree) uses an array of sequential structures to storeIt should be noted that the heap here is different from the heap in the operating system's virtual process address space. One is a data structure, and the other is a segmented area for managing memory in the operating system.
For specific implementation and application, please see:[Data Structure] 08. Heap and its application

4. Chain structure of binary tree and its implementation

4.1 Binary Tree Traversal

The easiest way to learn about binary tree structures is to traverse them.Binary tree traversal is to perform corresponding operations on the nodes in the binary tree in sequence according to certain specific rules, and each node is operated only onceThe operation performed when visiting a node depends on the specific application problem. Traversal is one of the most important operations on a binary tree and is also the basis for other operations on a binary tree.

4.1.1 Pre-order traversal

//根 左子树 右子树
void PrevOrder(pTreeNode root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%d ", root->val);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

The following figure shows the recursive process:

4.1.2 In-order traversal

//左子树 根 右子树
void InOrder(pTreeNode root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

The following is the recursive process:

4.1.3 Post-order traversal

//左子树 右子树 根
void PostOrder(pTreeNode root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

The following is the recursive process:

4.2.4 Level-order traversal

Level-order traversal: In addition to pre-order traversal, in-order traversal, and post-order traversal, you can also perform level-order traversal on a binary tree. Assume that the root node of the binary tree is located at level 1. Level-order traversal starts from the root node of the binary tree, first visits the root node of the first level, then visits the nodes on the second level from left to right, then the nodes on the third level, and so on.The process of visiting the nodes of the tree layer by layer from top to bottom and from left to right is called level-order traversal.。
Diagram:

We introduce a queue here to perform a pre-order traversal of the binary tree.

// 层序遍历
void LevelOrder(pTreeNode root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		pTreeNode front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			printf("NULL ");
		}
		else
		{
			printf("%d ", front->val);
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}
	QueueDestory(&q);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

4.1 Creation and destruction of binary trees

To create and destroy a binary tree, we useBinary Tree TraversalTake this as an example.

//二叉树的创建
struct TreeNode* Creat(char* arr,int n,int* i)
{ 
    if(*i<n&&arr[*i]=='#')
    {
        (*i)++;
        return NULL;
    }
    
    TreeNode* newnode=(TreeNode*)malloc(sizeof(TreeNode));
    newnode->left=NULL;
    newnode->right=NULL;

    newnode->val=arr[(*i)++];
    newnode->left=Creat(arr,n,i);
    newnode->right=Creat(arr,n,i);
    
    return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

//二叉树的销毁
void TreeDestroy(struct TreeNode* root)
{
    if(root==NULL)
    {
        return;
    }
    TreeDestroy(root->left);
    TreeDestroy(root->right);
    free(root);
}
1
2
3
4
5
6
7
8
9
10
11

4.3 Other operations on binary trees

The following operations are all carried out along the idea of ​​traversal.

// 二叉树节点个数
int TreeSize(pTreeNode root)
{
	if (root == NULL)
	{
		return 0;
	}
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}
1
2
3
4
5
6
7
8
9

// 二叉树叶子节点个数
int TreeLeafSize(pTreeNode root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

// 二叉树第k层节点个数
int TreeLevelKSize(pTreeNode root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

// 二叉树查找值为x的节点
pTreeNode TreeFind(pTreeNode root, TreeDataType x)
{

	if (root == NULL)
	{
		return NULL;
	}
	//相等就返回
	if (root->val == x)
		return root;
	//找左子树
	pTreeNode left=TreeFind(root->left, x);
	if (left)
	{
		return left;
	}
	//找右子树
	pTreeNode right = TreeFind(root->right, x);
	if (right)
	{
		return right;
	}
	//都没找到
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

//二叉树的高度
int TreeHeight(pTreeNode root)
{
	if (root == NULL)
	{
		return 0;
	}
	int max_left = TreeHeight(root->left) ;
	int max_right = TreeHeight(root->right);
	return max_left > max_right ? max_left + 1 : max_right + 1;
}
1
2
3
4
5
6
7
8
9
10
11

//判断是否是完全二叉树
bool TreeComplete(pTreeNode root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		pTreeNode front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			break;
		}
		else
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}
	while (!QueueEmpty(&q))
	{
		pTreeNode front = QueueFront(&q);
		QueuePop(&q);
		if (front)
		{
			QueueDestory(&q);
			return false;
		}
	}
	QueueDestory(&q);
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36