Comprehensive summary of tree and binary tree

I’m participating in nuggets Creators Camp # 4, click here to learn more and learn together!

One, foreword

Learning objective 1: Master the basic concept of tree and binary tree, five properties, judge complete binary tree, full binary tree.
Learning goal 2: Memorize the four major traversals of binary trees and write the traversal order and corresponding recursive code. Understand binary tree and tree conversion process
Key points: binary tree traversal, properties, binary tree and tree conversion

Ii. Concept and Definition

1. The tree

What is a tree? Is it the one down here?

Abstraction is good, but for those of you who have experience with data structures, the following diagram is even better:

Please clarify the relationships in the picture above:

The diagram above has only one root node, grandfather as the root can be called the large root heap, and you as the root can only be called the small root heap. It goes down into different nodes, and a node with several lines underneath it is called a degree, and there are no nodes underneath it is called a leaf.

Those at the same level are called siblings, and those at the next level are called children. There are several levels within several generations. The highest level is called the height of the family, and the highest number of children is called the degree of the family.

2. The binary tree

A binary tree, a binary tree literally means a tree can only have two forks. The cross on the left is called the left child and the cross on the right is called the right child.

Official term: a tree where each node has a degree of 2 or less and children have a definite order of nodes.

3. Full binary tree

A full binary tree is full, which means that each level is the largest node and cannot be empty.

4. Complete binary tree

Nodes are numbered from left to right in order to build a binary tree. There is no case where there are no left children but there are right children.
A full binary tree is always a complete binary tree, and a complete binary tree is not always a full binary tree

Properties of binary trees

As the saying goes: nature learn well, detours less walk half!

1. Layer nodes

At most 2^{i-1} nodes (I >=1) at the I level of the binary tree

2. Summary points

A binary tree of depth k has at most 2^{k}-1 nodes (k>=1)

The depth of 3.

If you round it down, say 4.5, you round it down to 4

4. Junction points

For any binary tree, the number of nodes of degree 0 is equal to the number of nodes of degree 2 +1.

5. Child node

The node is I and the parent is I /2 rounded down, the left child is 2 times I, the right child is 2 times I +1

I’m not going to do that, but I really don’t want to write it.

Four, binary tree traversal

1. Traversal in sequence

Algorithm on

Traversal order: root -> left -> right subtree
Dynamic diagram: Like the dynamic diagram above, sequential traversal is like a small person running around the outer circle of the binary tree starting at the root (if they find a gap, they get in) and output the sequence in the order they run

Recursive code

void  PreOrder(BiTree root) 
/* Traverses the binary tree in order, root is the pointer to the root of the binary tree (or a subtree) */
{
	if(root! =NULL)
	{
		Visit(root ->data);  /* Access the root */
		PreOrder(root ->LChild);  /* First traverses the left subtree */
		PreOrder(root ->RChild);  /* Traverses the right subtree */}}Copy the code

2. Middle order traversal

Algorithm on

Traversal order: left subtree -> root -> right subtree
Just like a projector, a binary tree is projected onto the same horizontal line from the left to the right. The resulting sequence of left-to-right correlation is the middle order traversal of the binary tree

Recursive code

void  InOrder(BiTree root)  
/* In order to traverse the binary tree, root is a pointer to the root of the binary tree (or a subtree) */
{
	if(root! =NULL)
	{
		InOrder(root ->LChild);   /* Order traverses the left subtree */
		Visit(root ->data);        /* Access the root */
		InOrder(root ->RChild);   /* Order traverses the right subtree */}}Copy the code

3. Back-order traversal

Before you look at the dynamic graph of the post-traversal, remember the dynamic graph of the pre-traversal? Don’t forget.

Postorder traversal is to perform operations like grape cutting on the basis of preorder traversal, as shown in the following figure:

Algorithm on

Traversal order: left subtree -> right subtree -> root
Dynamic diagram: post order traversal is also in accordance with the order of the first order traversal output, but post order traversal is like cutting grapes, can only be cut one by one, can not let more than 1 grapes fall down together, that is wrong. For example, in the figure above, D, E, H, I and J will fall if you cut B, while H will fall if you cut H. This is the rule

Recursive code

void  PostOrder(BiTree root)  
/* Traverses the binary tree sequentially. Root is a pointer to the root of the binary tree (or a subtree) */
{
	if(root! =NULL)
	{
		PostOrder(root ->LChild);   /* Traverses the left subtree */
		PostOrder(root ->RChild);   /* Traverses the right subtree */
    	Visit(root ->data);        /* Access the root */
     }
Copy the code

4. Hierarchical traversal

Algorithm explanation is a layer of left to right output, the algorithm does not require mastery

expand

First root traversal of a tree == first order traversal of a binary tree
Middle root traversal of a tree == post-order traversal of a binary tree
Backroot traversal of a tree == middle-order traversal of a binary tree

Five, the simple application of ergodic calculation method

1. Establish a binary tree for binary linked list storage

void CreateBiTree(BiTree *bt)
   // Build binary list of binary tree according to "extended sequential traversal sequence" algorithm
{
    char ch;
    ch = getchar();
    ifBt (ch = = '. ') * =NULL;  // Input with a dot (.) to indicate a null node.
    else 
	{
	      *bt=(BiTree)malloc(sizeof(BiTNode)); // create a new node
          (*bt)->data=ch;
          CreateBiTree(&((*bt)->LChild)); // Generate the left subtree
          CreateBiTree(&((*bt)->RChild)); // Generate the right subtree}}Copy the code

2. Output leaf nodes

void  PreOrder(BiTree root) 
/* Traverses the binary tree first, root is a pointer to the binary root node */
{
	if(root! =NULL)
	{
		if (root ->LChild==NULL && root ->RChild==NULL)
			printf("%c ",root ->data);  /* Outputs the leaf node */
		PreOrder(root ->LChild);  /* First traverses the left subtree */
		PreOrder(root ->RChild);  /* Traverses the right subtree */}}Copy the code

3. Count the number of binary tree leaves

/* LeafCount is a global variable that holds the number of leaf nodes, initialized to 0 */ before callingMethod one:void leaf_a(BiTree root)
{
	if(root! =NULL)
	{
		leaf_a(root->LChild);	
            leaf_a(root->RChild);
		if (root ->LChild==NULL && root ->RChild==NULL) LeafCount++; }}Copy the code

4. Find the height of binary tree

int PostTreeDepth(BiTree bt)   /* Backorder traversal to find the height of binary tree recursive algorithm */
{
	int hl,hr,max;
	if(bt! =NULL)
	{
		hl=PostTreeDepth(bt->LChild);  /* Find the depth of the left subtree */
		hr=PostTreeDepth(bt->RChild);  /* Find the depth of the right subtree */max=hl>hr? hl:hr;/* Get the left and right subtree depth */
		return(max+1);               /* Returns the tree depth */
	}
	else return(0);             /* If the tree is empty, 0 */ is returned
}
Copy the code

5. Print the binary tree as a tree

void PrintTree(BiTree bt,int nLayer)  /* Print binary tree */ as vertical tree
{
	if(bt == NULL) return;
	PrintTree(bt->RChild,nLayer+1);
	for(int i=0; i<nLayer; i++)printf("");
	printf("%c\n",bt->data);
	PrintTree(bt->LChild,nLayer+1);
}
Copy the code

Tree and binary tree conversion

1. Tree -> binary tree

Interpretation of the

Join all siblings
For each node in the tree, only the connection to the first node is preserved, and the others are deleted
The entire tree is rotated 90 degrees clockwise

2. Binary tree -> tree

Interpretation of the

Will the left child’s right child, right child’s right child…… All connected
All parent nodes remove the connection to the right child
Adjust the Angle

3. Forest -> binary tree

Interpretation of the

Start by converting every tree in the forest into a binary tree
Join the binary root nodes as brothers
Adjust the Angle

This is the end of the book. In fact, it is a comprehensive summary, but it is not comprehensive at all. The intention is to use these dynamic illustrations to help you understand the algorithm better, so that it might be easier to learn.

Comprehensive summary of tree and binary tree

One, foreword

Ii. Concept and Definition

1. The tree

2. The binary tree

3. Full binary tree

4. Complete binary tree

Properties of binary trees

1. Layer nodes

2. Summary points

The depth of 3.

4. Junction points

5. Child node

Four, binary tree traversal

1. Traversal in sequence

2. Middle order traversal

3. Back-order traversal

4. Hierarchical traversal

Five, the simple application of ergodic calculation method

1. Establish a binary tree for binary linked list storage

2. Output leaf nodes

3. Count the number of binary tree leaves

4. Find the height of binary tree

5. Print the binary tree as a tree

Tree and binary tree conversion

1. Tree -> binary tree

2. Binary tree -> tree

3. Forest -> binary tree

Related Posts

Ele. me produces a hands-on tutorial on Node.js

【 Data structure 】 Sort algorithm by bubble sort

The front-end algorithm, you know stacks, queues, linked lists, package them for you