[C language data structure——Binary tree]

Article directory

  • Article directory

  • 1. What is a tree?

    • tree definition

    • tree type

    • tree depth

    • Basic terminology for trees

  • 2. Full binary tree

    • definition

    • Characteristics of a full binary tree

  • 3. Complete binary tree

    • definition

    • Features

  • 4. Properties of binary trees

  • 5. Storage structure of binary tree

    • sequential storage structure

    • chain storage structure

  • 6. Basic operations of binary trees

  • 7. Creation of Binary Tree

  • 8. Binary tree traversal

    • Preorder traversal

    • inorder traversal

    • Postorder traversal

  • 9. Destruction of binary trees

  • 10. Searching nodes in binary trees

Welcome to the new issue of the C language data structure module–Binary tree

Personal homepage: -_Joker_-

?Column: C language data structure

Code repository: c_code

Welcome the big guys to read and follow us, and follow the comments to return

1. What is a tree

1. Definition of tree

A tree is a finite set of n (n>=0) nodes. When n = 0, it is called an empty tree. In any non-empty tree it should satisfy:

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

2. Types of trees

The types of trees can be divided into the following types

  • Unordered tree: There is no order relationship between the child nodes of any node in the tree. This kind of tree is called an unordered tree, also called a free tree;
  • Ordered tree: There is a sequential relationship between the child nodes of any node in the tree. This kind of tree is called an ordered tree;
  • Binary tree: A tree with each node containing at most two subtrees is called a binary tree;
  • Full binary tree: A tree in which all nodes except leaf nodes contain two subtrees is called a full binary tree;
  • Complete binary tree: A binary tree in which all levels except the last level are full of nodes and the last level lacks consecutive nodes on the right is called a complete binary tree;
  • Huffman tree (optimal binary tree): The binary tree with the shortest weighted path is called Huffman tree or optimal binary tree.

3. Tree depth

Define the root node level of a tree to be 1, and the levels of other nodes to be the level of their parent nodes plus 1. The maximum value of the levels of all nodes in a tree is called the depth of the tree. For example:

?

As shown in the figure, the depth of the tree in the figure is: 3

4.Basic terminology of trees

  • Degree of node: the number of subtrees owned by the node
  • Leaf (terminal) node: node with degree 0
  • Branch (non-terminal) node: a node with a degree other than 0
  • Degree of the tree: the maximum value of the degree of each node in the tree
  • Internal nodes: branch nodes other than the root node
  • Parent and child nodes: The root of the subtree of a node is called the child of the node; the node is called the parent of the child
  • Brothers: Children of the same parents
  • Ancestors of a node: all nodes on the branches from the root to the node
  • Descendants of a node: any node in the subtree of which the node is the root
  • Node level: indicates the relative position of the node in the tree. The root is the first level, and other nodes are pushed down in sequence; if
  • If the node is on level L, then its child is on level L + 1
  • Brother nodes: Nodes whose parents are on the same level are each other’s brothers.
  • Depth (height) of the tree: the maximum level of nodes in the tree
  • Ordered tree: The subtrees of each node in the tree are ordered from left to right and cannot be interchanged. Otherwise, it is called an unordered tree
  • Path length: starting from a certain node Ni in the tree, and being able to reach the node Nj through the nodes in the tree “top-down”, it is said that Ni to Nj exist
  • A path whose length is equal to the number of branches between the two nodes
  • The path length of a tree: the sum of the path lengths from the root to each node.
  • Forest: is a collection of m (m≥0) disjoint trees

Since binary trees are more widely used in data structures, we mainly focus on binary trees for explanation. The following introduces the basic knowledge about binary trees.

2. Full binary tree

Definition:

In a binary tree, if all branch nodes have left subtrees and right subtrees, and all leaf nodes are on the same level, such a binary tree is called a full binary tree.

The picture shows a full binary tree

Characteristics of full binary trees

The characteristics of a full binary tree are:

  1. Leaf nodes can only appear on the lowest level.
  2. The degree of non-leaf nodes must be 2.
  3. Among binary trees of the same depth, a full binary tree has the largest number of nodes and the largest number of leaves.
  4. Assuming the depth of the tree is i, the number of summary points is 2^i -1
  5. A full binary tree is a special kind of complete binary tree
  6. If there are two parents, the parent is i / 2, if there is a left child, the left child is 2i, and if there is a right child, the right child is 2i + 1.

3. Complete binary tree

Definition

The binary tree nodes are numbered from left to right and top to bottom. If the node numbered i is in the same position in the binary tree as the node numbered i in a full binary tree of the same depth, then this binary tree is called a complete binary tree.

The picture shows a complete binary tree

Features
  1. Leaf nodes can only appear on the lowest and next lower levels.
  2. The lowest leaf nodes are concentrated on the left side of the tree.
  3. If there is a leaf node in the penultimate layer, it must be in a continuous position on the right.
  4. If the node degree is 1, then the node has only a left child, that is, there is no right subtree.
  5. For a binary tree with the same number of nodes, a complete binary tree has the smallest depth.
  6. A full binary tree must be a complete binary tree, but the converse is not necessarily true.

4. Properties of binary trees

  • There are at most 2^(i-1) (i≥1) nodes on the i-th level of the binary tree
  • A binary tree with depth k has at most 2^k-1 nodes (k≥1)
  • For any binary tree T, if the number of terminal nodes is N0 and the number of nodes with degree 2 is N2, then N0=N2 + 1
  • The depth of a complete binary tree with n nodes is [log2(n)] + 1
  • A complete binary tree (also called a sequential binary tree) with n nodes has its nodes numbered from top to bottom (from left to right for each layer) from 1 to n, then for any node i (1 ≤i≤n) have:
  • If i>1, then i’s parents are [i/2]; if i=1, then i is the root and has no parents.
  • If 2i≤n, then the left child of i is 2i; otherwise, i has no left child
  • If 2i + 1 ≤ n, then the right child of i is 2i + 1; otherwise, i has no right child

5. Storage structure of binary tree

The storage structure of binary tree is divided into sequential storage structure and chain storage structure.

Sequential storage structure

The sequential storage of a binary tree refers to using a set of storage units with consecutive addresses to store the node elements on the complete binary tree from top to bottom and from left to right, that is, the node elements numbered i ii on the complete binary tree are stored in a one-dimensional array. In the component with subscript i ? 1.
According to the nature of binary trees, it is more appropriate to use sequential storage for complete binary trees and full binary trees. The sequence numbers of nodes in the tree can uniquely reflect the logical relationship between nodes. This can save storage space as much as possible and make use of the array elements. The subscript value determines the position of the node in the binary tree and the relationship between the nodes.
But for a general binary tree, in order for the array subscript to reflect the logical relationship between the nodes in the binary tree, we can only add some empty nodes that do not exist, so that each node can be compared with the node on the complete binary tree. , and then stored in the corresponding component of the one-dimensional array. However, in the worst case, a single tree with height h and only h nodes needs to occupy nearly 2h-1 storage units. The sequential storage structure of the binary tree is as shown in the figure, where 0 represents an empty node that does not exist.

Chain storage structure

Since sequential storage structures are very inconvenient, we usually use chained storage structures to implement binary trees. The chain storage structure opens up a space (node) and stores the left child, right child nodes and data through pointers.

Since the sequential structure is inconvenient to operate, we usually use a chained storage structure to implement the binary tree through recursion, which is defined as follows

typedef struct BinaryTree
{
    int val;
    struct BinaryTree *left;
    struct BinaryTree *right;
}BT;

6. Basic operations of binary trees

  • CreateTree(): Create a binary tree
  • PreOrder(BT* root): Preorder traversal of binary tree
  • InOrder(BT* root): In-order traversal of binary tree
  • BackOrder(BT* root): Post-order traversal of binary tree
  • DestoryTree(BT* root): Destroy the binary tree
  • FindTree(BT* root, int x): Find the node with value x in the binary tree

7. Creation of binary tree

The following is the algorithm for creating a binary tree

BTNode* CreatNode(int x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc fail");
exit(-1);
}
node->val = x;
node->left = NULL;
node->right = NULL;
return node;
}

8. Binary tree traversal

Preorder traversal

The preorder traversal order of a binary tree is root – left – right

That is, visit the root node first

Then access its left child node

Finally access its right child node

For example, in the figure above, the preorder traversal sequence is: A -> B -> D -> E -> C -> F

The algorithm is as follows

void PreOrder(BT* root)
{
if (root == NULL)
{
return;
}
    printf("%d",root->val);
    PreOrder(root->left);
    PreOrder(root->right);
}

In-order traversal

The order of preorder traversal of a binary tree is left – root – right

That is, visit the left child node first

Then access its root node

Finally access its right child node

For example, in the figure above, the preorder traversal sequence is: D -> B -> E -> A -> F -> C

The algorithm is as follows

void InOrder(BT* root)
{
if (root == NULL)
{
return;
}
InOrder(root->left);
printf("%d ", root->val);
InOrder(root->right);
}

Post-order traversal

The order of preorder traversal of a binary tree is left – right – root

That is, visit the left child node first

Then access its root node

Finally access its right child node

For example, in the figure above, the preorder traversal sequence is: D -> E -> B -> F -> C -> A

The algorithm is as follows

void BackOrder(BT* root)
{
if (root == NULL)
{
return;
}
BackOrder(root->left);
BackOrder(root->right);
printf("%d ", root->val);
}

9. Destruction of binary trees

The destruction of binary trees is also achieved through recursion:

void DestoryTree(BT* root)
{
if (root == NULL)
{
return;
}
DestoryTree(root->left);
DestoryTree(root->right);
free(root);
}

10. Searching nodes in binary trees

BT* FindTree(BT* root, int x)
{
if (root == NULL)
{
return;
}
if (root->val == x)
return root;
FindTree(root->left, x);
FindTree(root->right, x);
return NULL;
}

The above is the introduction to binary trees and the implementation of basic operations. Don’t forget to give me your support

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