Basic data structure – binary tree

1. Tree concept and structure

Tree is a non-linear data structure, which is a set of hierarchical relationships composed of n (n>=0) limited nodes. It’s called a tree because it looks like an upside-down tree, which means it has the roots pointing up and the leaves pointing down.
There is a special node called the root node. The root node has no predecessor node.
Except for the root node, the remaining nodes are divided into M (M>0) disjoint sets T1, T2,…, Tm, where each set Ti (1<= i<= m) is a tree structure with Tree-like subtrees. The root node of each subtree has one and only one predecessor, and can have 0 or more successors.
Therefore, the tree is defined recursively

Note: In the tree structure, there cannot be intersection between subtrees, otherwise it will not be a tree structure

None of the things below are trees.

Tree related concepts

Degree of node: The number of subtrees contained in a node is called the degree of the node; as shown below: A’s is 6
Leaf node or terminal node: A node with degree 0 is called a leaf node; As shown in the figure below: Nodes such as B, C, H, I… are leaf nodes.
Non-terminal nodes or branch nodes: nodes whose degree is not 0; As shown in the figure below: nodes such as D, E, F, G… are branch nodes
Parent node or parent node: If a node contains child nodes, this node is called the parent node of its child node; as shown below: A is the parent node of B
Child node or child node: The root node of the subtree contained by a node is called the child node of the node; as shown below: B is the child node of A
Sibling nodes: Nodes with the same parent node are called sibling nodes; as shown below: 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 below: the degree of the tree is 6
The level of the node: starting from the definition of the root, the root is the 1st level, the child nodes of the root are the 2nd level, and so on;
The height or depth of the tree: the maximum level of nodes in the tree; as shown below: the height of the tree is 4
Cousin nodes: Nodes whose parents are on the same level are cousins of each other; as shown below: H and I are brother nodes of each other.
Ancestors of a node: all nodes on the branches from the root to the node; as shown in the figure above: A is the ancestor of all nodes
Descendants: Any node in the subtree rooted at a node is called a descendant of that node. As shown above: all nodes are descendants of A
Forest: A collection of m (m>0) disjoint trees is called a forest.

tree representation
The tree structure is more complicated than the linear table, and it is more troublesome to store and represent it. Since the value range is saved, the relationship between the nodes and the nodes must also be saved. In fact, there are many ways to represent trees, such as: parent representation. , child representation, child parent representation, child brother representation, etc. Here we will briefly take a look at the most commonly used representations of child brothers

typedef int DataType;
struct Node
{
struct Node* _firstChild1; // first child node
struct Node* _pNextBrother; // Point to its next sibling node
DataType _data; // Data field in the node
};

2. Binary tree concept and structure

Concept
A binary tree is a finite set of nodes, which is:
1. Or empty
2. It consists of a root node plus two binary trees, also known as the left subtree and the right subtree

As can be seen from the picture above:
1. There is no node with degree greater than 2 in a binary tree.
2. The subtrees of a binary tree can be divided into left and right subtrees, and the order cannot be reversed, so the binary tree is an ordered tree.

Binary trees are composed of the following situations

Special binary tree:
1. Full binary tree: A binary tree is a full binary tree if the number of nodes in each layer reaches the maximum. That is to say, if 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.
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. For a binary tree with depth 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 depth K. It should be noted that a full binary tree is a special kind of complete binary tree.

A complete binary tree is full except for the last level, and other nodes are added from left to right.

Properties of binary trees

1. If the number of levels of the root node is specified to be 1, then there are at most 2^(h-1) nodes on the i-th level of a non-empty binary tree.
2. If the number of levels of the root node is specified to be 1, then the maximum number of nodes of a binary tree with depth h is 2^h-1.
3. For any binary tree, if the degree is 0, the number of leaf nodes is , and the number of branch nodes with degree 2 is , then n0=n2 +1
4. If the number of levels of the root node is specified to be 1, the depth of a full binary tree with n nodes, h= log2(n + 1)
5. For a complete binary tree with n nodes, if all nodes are numbered starting from 0 in array order from top to bottom, left to right, then
The node with serial number i is:
1. If i>0, the parent number of the node at position i: (i-1)/2;

i=0, i is the root node number, there is no parent node

2. If 2i + 1

2i + 1>=n otherwise there is no left child
3. If 2i + 2

2i + 2>=n otherwise there is no right child

B’s father: (1-1)/2=0

C’s father: (2-1)/2=0

B’s left Han 1*2 + 1=3

B’s right child 1*2 + 2=4

Storage structure of binary tree
Binary trees can generally be stored using two structures,a sequential structure and a chain structure.

sequential storage
Sequential structure storage is to use arrays for storage. Generally, arrays are only suitable for representing complete binary trees, because if they are not complete binary trees, there will be a waste of space.

Chain storage
The linked storage structure of a binary tree means that a linked list is used to represent a binary tree, that is, a chain is used to indicate the logical relationship of elements. The usual method is thateach 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 link points where the left child and right child of the node are respectively. storage address.

typedef int BTDataType;

typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;

3. Implementation of binary tree chain structure

Before learning the basic operations of a binary tree, you need to create a binary tree first, and then you can learn its related basic operations. Since everyone currently does not have a deep enough understanding of the binary tree structure, in order to reduce everyone’s learning cost, here we quickly create a simple binary tree manually and quickly enter the binary tree operation learning. When the binary tree structure is almost understood, we will go back and study the real binary tree. Creation method.

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include "Queue.h"

typedef int BTDataType;

typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
BTNode* temp = (BTNode*)malloc(sizeof(BTNode));
if (temp == NULL)
{
perror("malloc fail");
return NULL;
}

temp->data = x;
temp->left = temp->right = NULL;
return temp;
}

BTNode*CreatTree()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);

node1->left = node2;
node1->right = node4;

node2->left = node3;

node4->left = node5;
node4->right = node6;

return node1;

}

Note: The above code is not a way to create a binary tree. The real way to create a binary tree will be explained in detail later.
Before looking at the basic operations of binary trees, let’s review the concept of binary trees.

A binary tree is:

1. Empty tree
2. Non-empty: the root node, the left subtree of the root node, and the right subtree of the root node.

Binary tree traversal

1. Preorder Traversal (also known as preorder traversal) – the operation of accessing the root node occurs before traversing its left and right subtrees.
2. Inorder Traversal (Inorder Traversal) – The operation of accessing the root node occurs during the traversal of its left and right subtrees (in between).
3. Postorder Traversal – The operation of accessing the root node occurs after traversing its left and right subtrees.

Since the visited node must be the root of a certain subtree, N (Node), L (Left subtree) and R (Right subtree) can be interpreted as the root, the left subtree of the root and the right subtree of the root. NLR, LNR and LRN are also called first root traversal, middle root traversal and last root traversal respectively.

Preorder traversal

Preorder traversal visits the root first and then the left and right subtrees. Because the access operations are the same, we use recursive operations to complete.

For example, take the binary tree above. Preorder traversal, first visit the root, output A, then recurse, the left subtree is the root, visit B, output B, then B’s left subtree is the root and visit D, then the left and right subtrees of D are empty, return to B At this level, the right subtree of B is visited, and when the subtree of B ends, it returns to the right subtree of A. And so on.

Output: ABDEHCFG

In-order traversal

In-order traversal is a traversal method that first visits the left subtree, then the root, and finally the root.

What is the output of this binary tree in-order traversal? How to traverse

When A is encountered, no output is performed first, and the left subtree B of A is found. If B is encountered, the left subtree D is not traversed. The left subtree D of B is first searched. When D is encountered, the left subtree is not traversed, and the left subtree of D is found. The left subtree of D is Empty, end, return to D, output D, then find the right subtree of D, encounter the right subtree E of D, find E without outputting it, first find the left subtree of E, return empty, output E, continue Find the right subtree of E. The rest of the operations can be deduced…

So the output result is: DBEHAFCG

Postorder traversal

Postorder traversal is a traversal method that first visits the left subtree, then the right subtree, and finally visits the root.

Take this picture for example.

Since we have the basis of pre-sequence and mid-sequence analysis, we will not explain the analysis process too much.

Output result: DHEBFGCA

Level-order traversal

Level-order traversal visits nodes layer by layer.

For example, in this binary tree, the output result of level-order traversal is: ABCDEFGH

So how is the layer sequence implemented?

The layer sequence needs to be implemented with the queue. First, the root is put into the queue, and then dequeued. When dequeuing, the left and right children of the dequeued element are brought into the queue, and the cycle is repeated. The output result is the layer sequence traversal.

Number of nodes and height

We knew earlier that the number of nodes in a full binary tree is 2^h-1. So if it is an ordinary binary tree and we want to know the number of nodes, what should we do?

The number of nodes in a binary tree = root + the number of nodes in the left subtree + the number of nodes in the right subtree

Recursive operations like traversal are used. If it is empty, it returns 0. If it is not empty, it returns one. Use recursion to calculate the number of all nodes.

The kth level node of a binary tree

Number of points

How to calculate the number of kth level of binary tree. Still using recursion

The number of nodes in the kth layer. The left subtree of the k-1th layer plus the right subtree

Tree height calculation

The height of a binary tree is equal to the tallest subtree of the left subtree or the right subtree.

Use recursion, + 1 each time, and get the result.

Find a value in a binary tree

Creation of binary tree

For details, please refer to the exercises on Niuke.com. Binary tree traversal_NiukeTiba_Niuke.com (nowcoder.com)

How do we determine whether a tree is a complete binary tree.

Let’s first look at the comparison between complete binary trees and ordinary binary trees.

Here we use the idea of layer-order traversal to put the root into the queue, and when dequeuing, bring its child nodes into the queue. When the elements dequeued are empty, it is the condition for the complete binary tree to end. However, when it is not a complete binary tree, a null pointer is output, and there are elements behind it, but there are no elements in a complete binary tree.

For example, in the ordinary binary tree above, when 2 comes out, 3, NULL, is brought in.

Then out 4, bring in 5, 6

Out 3, bring in NULL NULL

After that, the queue lists NULL. At this time, if it is a complete binary tree, there are NULLs behind it. If it is an ordinary binary tree, there are nodes behind it.

Calculation of the number of leaves of a binary tree

When encountering a leaf, their left and right children are both empty. This is the condition for judging the leaf and it can be combined with recursion to find the number of leaves.

Destruction of binary trees

Use recursive operation to destroy one node at a time

Recurse first and then destroy the house to find the child node.

After destruction, manually set root to NULL in the main function

Source code

#pragma once

#include
#include
#include
#include

typedef struct BinaryTreeNode* QDatatype;

typedef struct QueueNode
{
struct QueueNode* next;
QDatatype data;
}QNode;

typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;

// 10:40
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDatatype x);
void QueuePop(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
QDatatype QueueFront(Queue* pq);
QDatatype QueueBack(Queue* pq);



/****************************************************** /
#define _CRT_SECURE_NO_WARNINGS

#include"Queue.h"

void QueueInit(Queue* pq)
{
assert(pq);

pq->head = pq->tail = NULL;
pq->size = 0;
}

void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}

pq->head = pq->tail = NULL;
pq->size = 0;
}

void QueuePush(Queue* pq, QDatatype x)
{
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = x;
newnode->next = NULL;

if (pq->head == NULL)
{
assert(pq->tail == NULL);

pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}

pq->size + + ;
}

void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head != NULL);

/*QNode* next = pq->head->next;
free(pq->head);
pq->head = next;

if (pq->head == NULL)
pq->tail = NULL;*/

if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}

pq->size--;
}

int QueueSize(Queue* pq)
{
assert(pq);

return pq->size;
}

bool QueueEmpty(Queue* pq)
{
assert(pq);

return pq->size == 0;
}

QDatatype QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));

return pq->head->data;
}

QDatatype QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));

return pq->tail->data;
}




/**********************************/
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include "Queue.h"

typedef int BTDataType;

typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
BTNode* temp = (BTNode*)malloc(sizeof(BTNode));
if (temp == NULL)
{
perror("malloc fail");
return NULL;
}

temp->data = x;
temp->left = temp->right = NULL;
return temp;
}

BTNode*CreatTree()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);

node1->left = node2;
node1->right = node4;

node2->left = node3;

node4->left = node5;
node4->right = node6;

return node1;

}

void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}

printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);

}

void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}

InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}

void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}

PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}

int TreeSize(BTNode* root)
{
return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

int TreeHeight(BTNode* root)
{
if (root == NULL)
{
return 0;
}

int left = TreeHeight(root->left);
int right = TreeHeight(root->right);

return left > right ? left + 1 : right + 1;
}

int TreeKLevel(BTNode* root, int k)
{
assert(k > 0);

if (root == NULL)
{
return 0;
}

if(k==1)
{
return 1;
}

return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}

BTNode* TreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}

if (root->data == x)
{
return root;
}

BTNode* lret = TreeFind(root->left, x);
if (lret != NULL)
{
return lret;
}

BTNode* rret = TreeFind(root->right, x);
if (rret != NULL)
{
return rret;
}

return NULL;
}

void LevelOrder(BTNode* root)
{
Queue q;
QueueInit( & amp;q);

if(root)
QueuePush( & amp;q, root);

while (!QueueEmpty( & amp;q))
{
BTNode* temp = QueueFront( & amp;q);
QueuePop( & amp;q);

printf("%d ", temp->data);

if (temp->left != NULL)
{
QueuePush( & amp;q, temp->left);
}

if (temp->right != NULL)
{
QueuePush( & amp;q, temp->right);
}
}

QueueDestroy( & amp;q);

}

bool BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit( & amp;q);

if(root)
QueuePush( & amp;q, root);

while (!QueueEmpty( & amp;q))
{
BTNode* temp = QueueFront( & amp;q);
QueuePop( & amp;q);

if (root == NULL)
{
break;
}
else
{
QueuePush( & amp;q, root->left);
QueuePush( & amp;q, root->right);

}
}

while (!QueueEmpty( & amp;q))
{
BTNode* temp = QueueFront( & amp;q);
QueuePop( & amp;q);

if (temp != NULL)
{
QueueDestroy( & amp;q);
return false;
}
}

QueueDestroy( & amp;q);
return true;
}



void BinaryTreeDestory(BTNode* root)
{
if (root == NULL)
return;
BinaryTreeDestory(root->left);
BinaryTreeDestory(root->right);

free(root);

}

int BinaryTreeLeafSize(BTNode* root,int* pi)
{
if(root)
{
\t\t
\t\t
BinaryTreeLeafSize(root->left, pi);
BinaryTreeLeafSize(root->right, pi);
if (root->left == NULL & amp; & amp; root->right == NULL)
{
(*pi) + + ;
}
}
}

int main()
{
\t
return 0;
}

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57447 people are learning the system