Data structure —— tree and binary tree (1)

Basic knowledge

• (1) Basic concept of tree
• (2) binary tree

1. The definition of binary tree and its main characteristics
2. Sequential storage structure and chain storage structure of binary tree
3. Traversal of binary trees
4. The basic concept and construction of clue binary tree

• (3) Trees and forests

1. The storage structure of a tree
2. Forest and binary tree conversion
3. Traversal of trees and forests

• (4) the application of tree and binary tree

1. Binary search tree
2. Balanced binary trees
3. Huffman tree and Huffman coding tree

Knowledge framework

(1) Basic concept of tree

Basic concepts of trees

Tree definition: tree is a finite set of N(N>=0) nodes, when N=0, called empty tree. Any non-empty tree should satisfy the requirement that there is only one root node. When N>1, the remaining nodes can be divided into several non-intersecting finite sets, which themselves form a tree (reflecting the definition of recursion), called the subtree of the root node. Obviously the definition of a tree is recursive, it’s a recursive data structure. As a logical structure, tree is also a hierarchical structure with the following two characteristics:

• The root of the tree has no precursor, and all nodes except the root have one or only one precursor.
• All nodes in a tree can have zero or more successors.
• Trees are suitable for representing hierarchical data. Any node in the tree (except the root node) is directly related to at most one node in the upper layer (its parent). The root node has no direct supernode, so there are at most n-1 edges in a tree of n nodes. Each node in the tree has a direct relationship with zero or more nodes (its children) at the next level.

– The important conclusion is that any tree with N (N>=1) nodes has N-1 edges

Basic terminology

(As explained above)

• Ancestor/descendant node:

For K: any node on the unique path from root node A to K is called the ancestor node of K. For example, node B is the ancestor node of K and K is the descendant node of B.

• Parent/child node:

The node E closest to K on the path is called the parent of K, and K is the child of E. Root A is the only node in the tree that has no parents.

• Sibling node:

Nodes with the same parents are called sibling nodes. For example, K and L have the same parent node E, that is, K and L are siblings.

• C:

The number of children of a node in the tree is called the degree of the node, and the maximum degree of the node in the tree is called the degree of the tree. Let’s say the degree of B is 2, but the degree of D is 3, so the degree of the tree is 3.

• Branch node (non-terminal node) :

Nodes whose degree is greater than 0 are called branch nodes (also called non-terminal nodes). Nodes with degree 0 (no children) are called leaf nodes (also known as terminal nodes). In a branch node, the number of branches at each node is the degree of that node.

• The height, depth, or hierarchy of nodes:

The hierarchy of nodes is defined from the root, which is the first layer (some textbooks define it as layer 0), its children as layer 2, and so on. The depth of a node is accumulated layer by layer from the root node. The height of nodes is accumulated layer by layer from bottom to top from leaf nodes.

• Tree height/depth:

The height (also called depth) of a tree is the maximum number of layers of nodes in the tree.

• Ordered and unordered trees:

A tree in which the subtrees of nodes are ordered from left to right and cannot be swapped is called an ordered tree. In an ordered tree, a node whose children appear in order from left to right is associated. The reverse is called an unordered tree. In the figure above, if you switch the positions of the children, you get a different tree.

• Path and path length:

The path between two nodes in a tree is made up of the sequence of nodes that pass between the two nodes, and the length of the path is the number of edges that pass along the path. The path length of A and K is 3. The path length is B and E.

• Forest:

A forest is a collection of M trees that do not intersect each other. The concept of a forest is very similar to the concept of a tree, because you just delete the root node of a tree and it becomes a forest. Conversely, the forest becomes a tree by adding a node to n independent trees and making the N trees subtrees of the node

The nature of the tree

• The number of nodes in the tree is equal to the degree of all nodes +1.
• The difference between a tree of degree M and an m cross tree

For example, the difference between a binary tree and an ordered tree of degree 2 is that a tree of degree 2 has at least three nodes, while a binary tree can be empty. Degree of 2 children orderly tree nodes around the order is relative to the case of another child nodes, if some nodes have only one child, the child node is no difference between them about the order, but whether children count of 2 binary tree, all you need to determine the order from left to right, that is to say, binary tree nodes number is not relative to the other, It’s certain.

• A tree of degree M has at most m^(i-1) nodes at the i-th layer (I ≥1), and a tree of degree M has at most m^(i-1) nodes at the i-th layer (I ≥1).
• An m-tree of height H has at most (m^(h−1))/(m−1) nodes
• An m-tree of height h has at least one node; A tree of height h and degree M has at least h+m+1 nodes
• The minimum height of an M-tree with n nodes is [logm(n(m−1)+1)], [] takes the integral function

Relationship between tree node and degree:

1. Summary points =n0+n1+n2…… +nm
2. Total score =1n1+2n2+3N3… +mnm
3. Summary points = total points +1

(2) binary tree

1. The definition and main characteristics of binary tree

• Binary tree definition:

A special tree structure of binary trees is characterized by the fact that each node has at most two subtrees (that is, there is no node with degree greater than 2 in the binary tree), and the subtrees of the binary tree are divided into left and right, and the order cannot be reversed (that is, the binary tree is an ordered tree). A binary tree is a finite set of n (n ≥ 0) nodes. If it is an empty tree, n = 0. It consists of a root node and a left subtree and a right subtree connected to a disjoint root, in which the left and right subtrees are binary trees.

• There are five forms of binary trees:

(a) empty binary tree (b) only root (c) only left subtree (d) both left and right subtrees (e) only right subtree

• Special binary tree

1. Full binary tree:

A binary tree of height H with 2^h-1 nodes

Features :(special complete binary tree)

• Only the last layer has leaf nodes
• There are no nodes of degree 1
• The left child of node I is 2i, and the right child is 2i+1. The parent of node I is [I /2] (integer function []) (if any)

2. Complete binary tree:

A complete binary tree is called a complete binary tree if and only if each node corresponds with nodes numbered 1 — n in a full binary tree of height H.

Features :(equivalent to removing the maximum node from a full binary tree)

• Only the last two layers may have leaf nodes
• There’s at most one node of degree 1
• The left child of node I is 2i, and the right child is 2i+1. The parent of node I is [I /2] (integer function []) (if any)
• I <=[n/2] is a branch node, and I >[n/2] is a leaf node

3. Binary sort tree:

A binary tree is either an empty binary tree or a binary tree with the following properties:

• The keywords of all nodes in the left subtree are smaller than those of the root node.
• The keywords of all nodes in the right subtree are greater than those of the root node.

4. Balanced binary tree: The depth difference between the left and right subtrees of any node in the tree is no more than 1.

The depth of the left subtree is 2, and the depth of the right subtree is 3

• The main features of binary trees are as follows:

1. The leaf node tree of a non-empty binary tree is equal to the number of nodes with degree 2 plus 1, that is, n0 = n2 + 1
2. There is at most 2 ^(k-1) at the k-layer of non-empty binary tree, K >=1; The i-th layer of m-tree has at most m^(i-1) nodes (I ≥1).
3. A binary tree of height h has at most 2^h-1,(h>=1)
4. The complete binary tree is numbered from top to bottom and from left to right, then:

• When I >1, the parent node of node I is numbered as [I /2], that is, when I is even, the parent node is numbered as I /2, and this node is the left child of its parent node. If I is even, its parent node is numbered (i-1) /2, and this node is the right child of its parent node.
• When 2i≤n, the left child of node I is numbered 2i; otherwise, there is no left child.
• When 2i+1≤n, the left child of node I is numbered 2i+1; otherwise, there is no right child.
• Node I’s level (depth) is log2(I)+1;

5. The minimum height of a complete binary tree with n (n>0) nodes is [log2(n+1)] or [log2(n)]+1,

2. Sequential storage structure and chain storage structure of binary tree

Sequential storage structure

The order of the binary tree storage structure refers to the storage unit with a set of address continuous storage in turn from top to bottom, from left to right fully binary tree node, the node of full binary tree Numbers for I stored in the array subscript is I – 1 array component, and then through a certain way to determine the nodes on the logical relationship between father and son or brothers. 0 represents a nonexistent null node. In the worst case, a single-branch tree of height H with only H nodes would occupy 2^ H-1 memory cells using a sequential structure. Therefore, the sequential storage structure is suitable for complete binary trees.

#define MaxSize 100 struct TreeNode{ ElemType value; // The data element in the node bool isEmpty; // if the node is null}; TreeNode t[Maxsize];Copy the code

Define an array T with length MaxSixe, and complete each node in the complete binary tree in order from top to bottom and from left to right.

for(int i=0; i<MaxSize; i++){ t[i].isEmpty=true; // initialize all nodes marked null}Copy the code

Here is:

In the sequential storage structure of binary tree, it is necessary to match the node number of the binary tree with that of the complete binary tree.

Chain storage structure

A chained structure is a binary tree stored in a linked list, and each node in the binary tree is stored by a linked node in the linked list. In a binary tree, the node structure usually includes several data fields and several pointer fields, so the binary linked list contains at least three fields: data field, left pointer field lchild, and right pointer field rchild.

// typedef struct BiTNode{ElemType data; Struct BiTNode *lchild,*rchild; }; BiTNode,*BiTNode;Copy the code

A binary list with n nodes has n+1 empty chain fields. (Can be used to construct the clue binary tree)

Initialize the binary tree and insert the nodes

srruct ElemType{ int value; } typedef struct BiTNode{ ElemType data; Struct BiTNode *lchild,*rchild; }; BiTNode,*BiTNode; // Define an empty tree BiTree root=NULL; Root =(BiTree)malloc(sizeof(BiTNode)); root->data={1}; root->lchild=NULL; root->rchild=NULL; // Insert a new node BiTree *p=(BiTNode *)malloc(sizeof(BiTNode)); p->data={2}; p->lchild=NULL; p->rchild=NULL; root->lchild=p; // as the left child of the rootCopy the code

Add a pointer to the parent node

// typedef struct BiTNode{ElemType data; Struct BiTNode *lchild,*rchild; Struct BiTNode *parent; // parent pointer}; BiTNode,*BiTNode;Copy the code

3. Binary tree traversal

Traversal: refers to a search path to visit each node in the tree, so that each node is visited once and only once.

The first sequence traversal

Preorder Preorder traversal:

If the binary tree is empty, do nothing, otherwise:

• Accessing the root
• The left subtree is traversed in order
• The right subtree is traversed in order

Void PreOrder(BiTree T){if(T! = NULL){ visit(T); // access the root PreOrder(T->lchild); PreOrder(T->rchid); // Recursively traverse the right subtree}}Copy the code

With the help of stack, three recursive traversal algorithms of binary tree can be transformed into non-recursive algorithms.

Preemptive traversal non-recursive algorithm: Similar to mid-order traversal, except that the access operation precedes the push operation.

Void PerOrder_NonRrecurrence(BiTree T){InitStack(s); // create stack and initialize BiTNode p = T; / / create a traverse the pointer p while (p | |! IsEmpty(s)){// Loop if(p){// If p is not empty (not empty left subtree) visit(p); // Access the node Push(s, p); P = p->lchild; } else{// Pop(s, p); P = p->rchild; // the pointer p points to the right subtree of the node, and the next loop traverses all the left nodes of the right subtree}}}Copy the code

In the sequence traversal

Order traversal operation in Inorder:

If the binary tree is empty, do nothing, otherwise:

• Middle order traverses the left subtree
• Accessing the root
• Middle order traverses the right subtree

Void InOrder(BiTree T){if(T! = NULL){ InOrder(T->lchild); // Recursively visit the left subtree visit(T); // access root InOrder(T->rchild); // Access right subtree recursively}}Copy the code

Middle-order traversal non-recursive algorithm:

Scan (non-access operation) all left nodes of the root node and push them one by one, then push one node * P (this node has no left child or all left child nodes have been accessed) and access. The right child of that node is then scanned and pushed onto the stack, and all left children of that right child are scanned and pushed onto the stack. Repeat until the stack is empty.

Void InOrder_NonRrecurrence(BiTree T){InitStack(s); // create stack and initialize BiTNode p = T; / / create a traverse the pointer p while (p | |! IsEmpty(s)){// If p is not empty or the stack is not empty, loop if(p){// If p is not empty (not empty left subtree), loop through the left subtree Push(s, p); P = p->lchild; } else{// Pop(s, p); Visit (p); P = p->rchild; // the pointer p points to the right subtree of the node, and the next loop traverses all the left nodes of the right subtree}}}Copy the code

After the sequence traversal

Sequential traversal operations in Postorder:

If the binary tree is empty, do nothing, otherwise:

• The left subtree is traversed sequentially
• The right subtree is traversed sequentially
• Accessing the root

Void PostOrder(BiTree T){if(T! = NULL){ PostOrder(T->lchild); PostOrder(T->rchild); // recursively traverse the right subtree visit(T); // Access the root}}Copy the code

Post-order traversal non-recursive algorithm:

Start at the root, push it, and search down its left subtree until you find a node that has no left child, but you can’t push it out of the stack and access it, because if it has a right subtree, the same rules apply to its right subtree. If the top element wants to be accessed out of the stack, either the right subtree is empty or the right subtree has just been accessed (at which point the left subtree has already been accessed), thus ensuring the correct order of access.

Void PostOrder_NonRrecurrence(BiTree T){InitStack(s); // create stack and initialize BiTNode p = T; / / create a traverse the pointer p while (p | |! IsEmpty(s)){// Loop if(p){// If p is not empty (not empty left subtree) Push(s, p); P = p->lchild; } else{GetTop(s,p); If (p->rchild&&p->rchild! P =p->rchild; p=p->rchild; Else {// otherwise, pop the node and access pop(s,p); Visit (p->data); // access this node r=p; P =NULL; }}//else}//while}Copy the code

Level traversal

The hierarchical traversal of a binary tree is to access nodes in the binary tree in the order of layers 1, 2, 3, and 4 in the direction indicated by the arrow.

The hierarchical traversal needs the help of queue: the binary root node is first joined in the queue, and then the binary root node is out of the queue and visited. If there is a left sub-tree, the left sub-tree root node is joined in the queue. If there is a right subtree, the right subtree root node is added to the queue. The queue is then dequeued and accessed, and the above operation is repeated until the queue is empty.

Void LevelOrder(BiTree T){InitQueue(Q); // create an empty queue Q BiTree p; P EnQueue(Q, T); // join the queue while(! IsEmpty Q){// If the queue is not empty, continue to loop through DeQueue(Q, p); // Visit (p); If (p->lchild! EnQueue(Q, p->Lchild); If (p->child! EnQueue(Q, p->rchild); // right child root node join the queue}}Copy the code

Construct binary tree from traversal sequence

Key: find the root of the tree, divide the left and right sub-trees according to the middle order sequence, and then find the left and right sub-tree roots. (Careful drawing is required to analyze and understand the result combination generated by sequential sequence and middle sequence combination)

• Pre-ordered sequence + middle-ordered sequence
• Post-ordered sequence + middle-ordered sequence
• Sequence + middle sequence

At the same time: a binary tree cannot be uniquely determined by the combination of sequential sequence, sequential sequence and sequential sequence.

4. The basic concept and construction of clue binary tree

The basic concept

Definition: N +1 null Pointers in a binary tree of N nodes. This is because each leaf node has two null Pointers, and each node with degree 1 has a null pointer. The total number of null Pointers is 2n0+ N1, and n0=n2+1. That means twice the number of leaf nodes plus twice the number of nodes per child.

In binary tree cueing, it is usually stipulated that: if there is no left subtree, lchild is made to point to its precursor node; If there is no right subtree, let rchlid point to its successor. The addition of two flag fields indicates whether the current pointer field points to a front or rear drive or a left or right subtree.

The meaning of the flag field:

Storage structure of clue binary tree:

Typedef struct ThreadNode{ElemType data; Struct ThreadNode *lchild,*rchild; Int ltag,rtag; } ThreadNode, *ThreadTree;Copy the code

The binary linked list constituted by the above node structure is the storage structure of the binary tree, which is called the clue linked list, in which the pointer to the precursor and successor of the node is called the clue. A binary tree with clues is called a cued binary tree. The process of traversing a binary tree in some order to turn it into a cued binary tree is called cueing.

Construction of binary tree of clue

A binary tree clue is a clue that changes the null pointer of the binary tree to point to a precursor or successor. The information of precursor or successor can only be obtained in traversal. Therefore, the cueing of binary tree is essentially traversing the binary tree once. In the traversal process, check whether the left and right pointer fields of the current node are empty; if so, change them into clues pointing to precursor node or successor node.

Take the binary tree of middle-order clue as an example

Through the order traversal for binary tree cue recursive algorithm

void InThread(ThreadTree &p,ThreadTree &pre){ if(p! =NULL){ InThread(p->lchild,pre); If (p->lchild==NULL){p->lchild==NULL; p->ltag=1; } if(pre! =NULL&&pre->rchild==NULL){ pre->rchild=p; Pre ->rtag=1; } pre=p; // mark the current node as InThread(p->rchild,pre); }//if(p! =NULL) }Copy the code

The main process algorithm of middle order clue binary tree is established by middle order traversal

void CreateInThread(ThreadTree T){ ThreadTree pre=NULL; if(T! =NULL){// InThread(T,pre); Pre ->rchild=NULL; Pre ->rtag=1; }}Copy the code

To facilitate operation, add a header node to the binary tree’s clue list, and make the pointer of the lchild field of the header node point to the root node of the binary tree, and make the pointer of the rchild field point to the last node visited by the middle order traversal. Instead, let the first node and the lChild field of the last node point to the head node. This is equivalent to the establishment of a bidirectional cue linked list for the binary tree, which is convenient to traverse the binary tree from back to front or from front to back.

Traversal of a binary tree of clues

Traversal of binary trees with middle order clues

The nodes of the binary tree of middle order cue contain the precursor and successor information of the binary tree. In traversal, the first node in the sequence is found first, and then the successor of the node is found successively until the successor is empty. The law of finding the successor of a node in a middle-order clue binary tree is as follows: if its right symbol is “1”, the right chain is the clue and indicates the successor; otherwise, the first node visited in the right subtree (the lowest left node in the right subtree) is the successor.

Traversal of a cued binary tree without a head node:

• Find the first node under the middle-ordered sequence in the middle-ordered clue binary tree:

ThreadNode *Firstnode(ThreadNode *p){ while(p->ltag==0) p=p->lchild; // return p; }Copy the code

• To find the successor of node P in binary tree of middle-ordered clue under middle-ordered sequence:

ThreadNode *Nextnode(ThreadNode *p){ if(p->rtag==0) return Firstnode(p->rchild); else return p->rchild; //rtag==1Copy the code

• Middle-order traversal algorithm of middle-order binary tree without head node:

void Inorder(ThreadNode *T){ for(ThreadNode *p=Firstnode(T); p! =NULL; P=Nextnode(p)) visit(p); }Copy the code

The establishment of the binary tree of the preorder cue and the binary tree of the postorder cue is relative to the position of the recursive function of the left and right subtree which only needs to change the code section of the transformation of the cue and call the cue. The sequential cue binary tree and the successors of the sequential cue binary tree are similar.

How to find successors of nodes in a binary tree of preordered clues? If there is a left child, the left child is his successor; If there is no left child but a right child, the right child is the successor; If it is a leaf node, the right chain domain directly indicates the successor of the node.

It is complicated to find the successor of the node in the binary tree with posterior clue, which can be divided into three cases :① if the node X is the root of the binary tree, then the successor is empty; ② if the node X is the right child of its parents, or the left child of its parents and their parents have no right subtree, then the successor is the parent; ③ If node X is the left child of its parents and their parents have right subtrees, then the first node listed is traversed by the next right subtree of the parents. In the figure, the successor of node B cannot be found through the chain domain. It can be seen that the parents of nodes need to be known when the successor of node B is found on the binary tree of the trailing clue, that is, the trigonal linked list with marked domain should be used as the storage structure.

(3) Trees and forests

(4) the application of tree and binary tree