Shulou(Shulou.com)05/31 Report--

This article mainly explains "the operation method of C language binary tree". Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Next let the editor to take you to learn "C language binary tree operation method" it!

Binary tree classification

Full binary tree

Except for the last layer without any child nodes, all nodes on each layer have a binary tree with two child nodes. It can also be understood as a binary tree in which the number of nodes in each layer reaches the maximum.

Complete binary tree

A binary tree with n nodes in depth k, the nodes in the tree are numbered from top to bottom and from left to right. If the node numbered I (1 ≤ I ≤ n) and the node numbered I in the full binary tree have the same position in the binary tree, the binary tree is called a complete binary tree.

To put it simply, a complete binary tree is a full binary tree in the last layer that can be missing (a complete binary tree is a special full binary tree), and it is missing from right to left.

Binary tree property

If it is specified that the number of layers of the root node is 1, there will be at most 2 ^ (iMel 1) nodes on the level I of a non-empty binary tree.

If the number of layers of root nodes is specified as 1, the maximum number of nodes of a binary tree with depth h is 2 ^ h − 1.

For any binary tree, if the number of leaf nodes (nodes with degree 0) is n 0 and the number of nodes with degree 2 is n 2, then n 0 = n 2 + 1.

If the number of layers of root nodes is specified as 1, the depth of the full binary tree with N nodes is the largest integer less than (log_2) Numeric 1.

The use of nature

In a complete binary tree with 2n nodes, the number of leaf nodes is ()

A n

B n + 1

CN-1

D n / 2

Analysis:

There are x0 nodes with a degree of 0.

There are x1 nodes with degree 1.

There are x2 nodes with degree 2.

X0 + x1 + x2 = 2n

X0 = x2 + 1

It can be deduced from the above two formulas: 2 * 2x2 + x1 + 1 = 2n

Because it is a complete binary tree, x1 may be 0J1, but to make the result of the above expression even, x1 can only be 1, so x2 equals n, choose A.

Traversal of binary tree

First, let's create a simple binary tree.

Typedef char BTDataType;typedef struct BinaryTreeNode {struct BinaryTreeNode* left; struct BinaryTreeNode* right; BTDataType data;} BTNode;int main () {BTNode* A = (BTNode*) malloc (sizeof (BTNode)); A-> data ='A'; A-> left = NULL; A-> right = NULL; BTNode* B = (BTNode*) malloc (sizeof (BTNode)); B-> data ='B' B-> left = NULL; B-> right = NULL; BTNode* C = (BTNode*) malloc (sizeof (BTNode)); C-> data = 'Clover; C-> left = NULL; C-> right = NULL; BTNode* D = (BTNode*) malloc (sizeof (BTNode)); D-> data =' Downs; D-> left = NULL; D-> right = NULL BTNode* E = (BTNode*) malloc (sizeof (BTNode)); E-> data = 'eyed; E-> left = NULL; E-> right = NULL; A-> left = B; A-> right = C; B-> left = D; B-> right = E; LevelOrder (A);} preorder traversal

Preorder (preorder): root-> left subtree-> right subtree

Expected result: A B D E C

/ / preorder void PrevOrder (BTNode* root) {if (root = = NULL) {/ / print NULL printf ("NULL") for more intuitive results; return;} / / print root data printf ("% c", root- > data) first; / / traverse the left subtree PrevOrder (root- > left) / / iterate through the right subtree PrevOrder (root- > right);}

Compilation result:

Mid-order traversal

Middle order: left subtree-> root-> right subtree

Expected result: D B E A C

Void MidOrder (BTNode* root) {/ / for more intuitive results, print NULL if (root = = NULL) {printf ("NULL"); return;} MidOrder (root- > left); printf ("% c", root- > data); MidOrder (root- > right);}

Compilation result:

Post-order traversal

Follow: left subtree-> right subtree-> root

Expected result: D E B C A

Void PostOrder (BTNode* root) {if (root = = NULL) {printf ("NULL"); return;} PostOrder (root- > left); PostOrder (root- > right); printf ("% c", root- > data);}

Compilation result:

Sequence traversal

Void LevelOrder (BTNode* root) {/ / create queue q Queue q; / / initialize queue QueueInit (& Q); / / if the root node is not empty, queue if (root) QueuePush (& Q, root) / / cycle until the queue column is empty while (! QueueEmpty (& Q)) {/ / get the first data of the queue and print QDataType front = QueueFront (& Q); printf ("% c", front- > data); / / header data out of queue QueuePop (& Q) / / if the left subtree is not empty, the left subtree queues if (front- > left! = NULL) {QueuePush (& Q, front- > left) } / / if the right subtree is not empty, the right subtree queues if (front- > right! = NULL) {QueuePush (& Q, front- > right) } find the number of binary tree nodes int BTSize (BTNode* root) {return root = = NULL? 0: 1 + BTSize (root- > left) + BTSize (root- > right);} calculate the number of binary tree leaf nodes int BTLeafSize (BTNode* root) {if (root = = 0) return 0; return root- > left = NULL & & root- > right = NULL? 1: BTLeafSize (root- > right) + BTLeafSize (root- > left) } find the maximum depth of the binary tree int maxDepth (BTNode* root) {if (root = = NULL) return 0; return 1 + fmax (maxDepth (root-> left), maxDepth (root-> right)); the destruction of the binary tree / / the destruction of the binary tree / / the secondary pointer is to change the pointer to void DistoryTree (BTNode** root) {if (* root = = NULL) {return } DistoryTree (& (* root)-> left); DistoryTree (& (* root)-> right); free (* root); * root = NULL;} so far, I believe you have a deeper understanding of "the operation of C language binary tree". You might as well do it in practice! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.