Chapter 5 Trees and Binary Trees (1)

This is the 7th day of my participation in the August Text Challenge.More challenges in August

Chapter 5 Trees and Binary Trees (1)

The outline

The basic concept of trees the storage structure of trees the number of trees and the traversal of forests the definition and properties of binary trees the storage structure of binary trees the traversal clue of binary trees the mutual conversion of binary trees and the application of binary trees and the search set binary sorting tree balanced binary tree Huffman treeCopy the code

Focus on

Four kinds of Traversal binary trees Properties of binary sorting tree balanced binary tree Huffman treeCopy the code

The difficulties in

The post-order traversal nonrecursion of binary tree realizes balance adjustment of binary tree equilibrium of cuedCopy the code

First, the basic concept of trees

Definition:

A finite set of N(N>0) nodes should satisfy for any non-empty tree

1. There is only one specific node called root
2. When N>1, other nodes can be divided into m(m>0) finite sets T1, T2…… Tm, where each set itself is a tree and is called a subtree of the root node

Tree characteristics:

1. The definition of a tree is recursive. It is a recursive data structure
2. The tree is a nonlinear structure in logical structure
3. The root node of the tree has no precursor node, and all nodes except the root node have only one precursor node
4. The leaf node of the tree has no successors. All nodes except the leaf node have one or more successors

Basic terms:

Taking K as an example, any node on the unique path from root A to node K is called the ancestor of K
Node B is the ancestor of node K, which is the descendant of node B
The node E closest to K among the ancestor nodes is called the parent node of K, while K is the child node of node E
Nodes with the same parents are called siblings. For example, K and L are siblings
The number of children of a node is called the degree of node. For example, degree B of node is 2 and degree D of node is 3
The maximum degree of a node in a tree is called the degree of the tree. For example, the degree of the tree in the right picture is 3
Nodes with degrees greater than 0 are called branch nodes (also called non-terminal nodes)
Nodes with degree 0 are called leaf nodes (also known as terminal nodes)
The hierarchy of nodes is defined from the root, which is layer 1, its children layer 2, and so on
The height (depth) of the tree is the maximum number of layers of nodes in the tree. In the figure below, the height (depth) of the tree is 4

The sequence of nodes passing between two nodes in a tree constitutes the path between them
The length of the path is the number of edges along the path. For example, the length of the path between node A and node K is 3, and it passes through node B and node E
An ordered tree is a tree where the children of any node are ordered from left to right and cannot be swapped
An unordered tree is one in which there is no sequential relationship between the children of any node
A forest is a collection of disjoint trees in m(m>0)

Note:

Branches in a tree are directed, so the path in the tree is also from parent to child, two children of the same parent

There is no path between

Above concept need not special memory, one’s deceased father grind does not test pure concept question, above concept practice much nature remembered

Properties of trees:

1. The number of nodes in the tree is equal to the degree of all nodes plus 1, that is, the number of nodes = the number of edges +1= the degree of all nodes +1

Above property should remember on the foundation of understanding, take an examination of grind often can take an examination of calculation

Second, the storage structure of the tree

1. Parental representation

A set of continuous space is used to store each node, and a pseudo-pointer is added to each node to indicate the location of its parent node in the array

Parental notation stores structural code implementations

// The parents of the tree represent the storage structure
#define MAXSIZE 100
typedef struct{
	ElemType data;
	int parent;
}PTNode;

typedef struct{
	PTNode nodes[MAXSIZE];
	int n;
}PTree; 
Copy the code

Pay attention to

The storage structure takes advantage of the fact that each node has only one parent
The time complexity of this structure is 0(1) for finding parents through nodes, and the time complexity of 0(n) for finding children through parents requires traversing the entire array.

2. Child notation

The children of each node are linked together in a single linked list to form a linear structure

Note:

N nodes have N children linked lists
In this structure, the time complexity of finding the child through parents is 0, and the time complexity of finding the child through nodes is 0(N).

Child representations store structural code implementations

//2. Child representation storage structure
typedef struct CTNode{ // Child node
	int child;
	struct CTNode *next; 
}CTNode,*ChildPtr;

 typedef struct CTBox{ // Table header structure
 	ElemType data;
	ChildPtr firstchild; 
 }CTBox;
 
 typedef struct CTree{ / / tree structure
 	CTBox nodes[MAXSIZE];
	int n; 
 }CTree;
Copy the code

3. Child brother notation

Each node contains three parts: a pointer to the first child node, its value, and a pointer to its next sibling.

Note:

The child brother representation is also called binary tree representation, that is, binary linked list as the storage structure of the tree
The advantage of this method is that the tree can be easily converted into a binary tree and the child nodes can be easily found
The disadvantage is that it is cumbersome to find the parent node from the current node

Child brother notation stored code implementation

//3. Child sibling representation storage structure
 typedef struct CSNode{
 	ElemType data;
 	struct CSNode *firstchild, *nextsibling;
 }CSNode,*CSTree; 
Copy the code

Chapter 5 Trees and Binary Trees (1)