Shulou(Shulou.com)06/02 Report--

This article mainly introduces "what is the principle of C language chain binary tree structure". In daily operation, I believe that many people have doubts about the principle of C language chain binary tree structure. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubts about "what is the principle of C language chain binary tree structure?" Next, please follow the editor to study!

Binary tree node declares traversal of typedef char BTDataType; typedef struct BinaryTreeNode {BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right;} BTNode; binary tree

Traversal of binary tree is an important part of learning binary tree structure. The traversal of binary tree is mainly divided into three kinds: 1. Preorder traversal 2. Traversal in the middle order 3. Traversal in post-order. First of all, we need to know that a binary tree is divided into root, left subtree and right subtree. And the three traversal methods are also realized around the root.

Build a binary tree

Let's build a binary tree according to the picture above.

BTNode* CreatTreeNode (BTDataType x) {BTNode* node = (BTNode*) malloc (sizeof (BTDataType)); node- > data = x; node- > right = NULL; node- > left = NULL; return node;} int main () {BTNode* A = CreatTreeNode ('A'); BTNode* B = CreatTreeNode ('B'); BTNode* C = CreatTreeNode ('C'); BTNode* D = CreatTreeNode ('D') BTNode* E = CreatTreeNode ('E'); BTNode* F = CreatTreeNode ('F'); A-> left = B; A-> right = C; B-> left = D; C-> left = E; C-> right = F;} 1. Preorder traversal

The order of preorder traversal is the root left subtree, the right subtree, as its name implies, first visits the root node, then visits the left node, and finally visits the right node.

Traversing according to the previous order, the traversal order of the above figure is: A B D NULL NULL NULL C E NULL NULL F NULL NULL

/ / A binary tree preorder traversal void BinaryTreePrevOrder (BTNode* root) {if (root = = NULL) / / equals NULL returns {printf ("NULL"); return;} printf ("% c", root- > data); / / print node BinaryTreePrevOrder (root- > left); / / Recursive to the left subtree BinaryTreePrevOrder (root- > right) / / Recursive to the right subtree} 2. Mid-order traversal

The order of traversal in the middle order is that the root of the left subtree, as the name implies, visits the left node first, then the root node, and finally the right node.

If you traverse according to the middle order, the traversal order of the above figure is: NULL D NULL B NULL A NULL E NULL C NULL F NULL

/ / if you traverse void BinaryTreeInOrder (BTNode* root) {if (root = = NULL) / / equals NULL, you will directly return {printf ("NULL"); return;} BinaryTreePrevOrder (root- > left); / / Recursive to the left subtree printf ("% c", root- > data); / / print node BinaryTreePrevOrder (root- > right) / / Recursive to the right subtree} 3. Post-order traversal

The order of traversal is that the root of the right subtree of the left subtree, as its name implies, visits the left node first, then the right node, and finally the root.

Traversing in the following order, the traversal order of the above figure is: NULL NULL D NULL B NULL NULL E NULL NULL F C A

/ / traversing void BinaryTreePostOrder (BTNode* root) {if (root = = NULL) / equals NULL returns {printf ("NULL") directly; return;} BinaryTreePostOrder (root- > left); / / recursively to the left subtree BinaryTreePostOrder (root- > right); / / recursively to the right subtree printf ("% c", root- > data) / / print nodes} the number of binary tree nodes

Finding the number of binary tree nodes is similar to the above traversal, which is realized by recursive functions. The number of nodes of a binary tree is mainly composed of three parts: the root node + the number of nodes of the left subtree + the number of nodes of the right subtree. Knowing this formula, we can implement the code.

/ / number of binary tree nodes int BinaryTreeSize (BTNode* root) {if (root = = NULL) / / if empty returns zero {return 0;} return BinaryTreeSize (root- > left) + BinaryTreeSize (root- > right) + 1;} number of binary tree leaf nodes

The left and right subtrees of the leaf node are empty. To know this, we only need to change the above code slightly.

/ / number of leaf nodes in binary tree int BinaryTreeLeafSize (BTNode* root) {if (root = = NULL) {return 0;} if ((root- > left = = NULL) & & (root- > right = = NULL) {return 1;} return BinaryTreeLeafSize (root- > left) + BinaryTreeLeafSize (root- > right);} number of nodes in layer K of binary tree

If you specify a binary tree and find the number of nodes in its layer K, you can also use the idea of recursion. When the given K is zero, it is to find the number of root nodes, obviously, it is to return 1; and K is not 00:00, we can find the sum of the number of nodes in layer 1 of the left and right subtree of root.

/ / number of k-level nodes of binary tree int BinaryTreeLevelKSize (BTNode* root, int k) {if (root = = NULL) {return 0;} if (k = = 1) {return 1;} return BinaryTreeLevelKSize (root- > left, k-1) + BinaryTreeLevelKSize (root- > right, k-1); height / depth of binary tree

The height of the binary tree refers to the maximum node hierarchy of the binary tree, that is, the maximum height of the left and right subtrees + 1.

/ / binary tree depth / height int BinaryTreeDepth (BTNode* root) {if (root = = NULL) {return 0;} int leftDepth = BinaryTreeDepth (root- > left); int rightDepth = BinaryTreeDepth (root- > right); return leftDepth > rightDepth? LeftDepth + 1: rightDepth + 1;} binary tree lookup node with value x / / binary tree lookup node BTNode* BinaryTreeFind (BTNode* root, BTDataType x) {if (root = = NULL) / / root is empty, directly return NULL {return NULL;} if (root- > data = = x) / / find the direct return node {return root } BTNode* leftRet = BinaryTreeFind (root- > left, x); if (leftRet) {return leftRet; / / if found in the left subtree, return directly without recursion to the right subtree} BTNode* rightRet = BinaryTreeFind (root- > right, x); if (rightRet) {return rightRet;} return NULL / / if none are found, return NULL} overall code # pragma once#include#include#includetypedef char BTDataType; typedef struct BinaryTreeNode {BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right;} BTNode; BTNode* CreatTreeNode (BTDataType x); / / number of binary tree nodes int BinaryTreeSize (BTNode* root); / / number of binary tree leaf nodes int BinaryTreeLeafSize (BTNode* root) / / number of nodes in the k layer of the binary tree int BinaryTreeLevelKSize (BTNode* root, int k); / / binary tree search node BTNode* BinaryTreeFind (BTNode* root, BTDataType x); / / binary tree preorder traversal void BinaryTreePrevOrder (BTNode* root); / / binary tree order traversal void BinaryTreeInOrder (BTNode* root); / / binary tree post order traversal void BinaryTreePostOrder (BTNode* root); / / binary tree depth / height int BinaryTreeDepth (BTNode* root) # include "BinarryTree.h" BTNode* CreatTreeNode (BTDataType x) {BTNode* node = (BTNode*) malloc (sizeof (BTDataType)); assert (node); node- > data = x; node- > right = NULL; node- > left = NULL; return node;} / / preorder traversal of void BinaryTreePrevOrder (BTNode* root) {if (root = NULL) {printf ("NULL") Return;} printf ("% c", root- > data); BinaryTreePrevOrder (root- > left); BinaryTreePrevOrder (root- > right);} / / void BinaryTreeInOrder (BTNode* root) {if (root = = NULL) {printf ("NULL"); return;} BinaryTreePrevOrder (root- > left) Printf ("% c", root- > data); BinaryTreePrevOrder (root- > right);} / / binary tree post-order traversal void BinaryTreePostOrder (BTNode* root) {if (root = = NULL) {printf ("NULL"); return;} BinaryTreePostOrder (root- > left); BinaryTreePostOrder (root- > right); printf ("% c", root- > data) } / / number of binary tree nodes int BinaryTreeSize (BTNode* root) {if (root = = NULL) {return 0;} return BinaryTreeSize (root- > left) + BinaryTreeSize (root- > right) + 1;} / / binary tree leaf nodes int BinaryTreeLeafSize (BTNode* root) {if (root = = NULL) {return 0 } if ((root- > left = = NULL) & & (root- > right = = NULL) {return 1;} return BinaryTreeLeafSize (root- > left) + BinaryTreeLeafSize (root- > right);} / / the number of nodes in the k layer of the binary tree int BinaryTreeLevelKSize (BTNode* root, int k) {if (root = NULL) {return 0 } if (k = = 1) {return 1;} return BinaryTreeLevelKSize (root- > left, k-1) + BinaryTreeLevelKSize (root- > right, k-1);} / / binary tree lookup node BTNode* BinaryTreeFind (BTNode* root, BTDataType x) {if (root = = NULL) {return NULL } if (root- > data = = x) {return root;} BTNode* leftRet = BinaryTreeFind (root- > left, x); if (leftRet) {return leftRet;} BTNode* rightRet = BinaryTreeFind (root- > right, x); if (rightRet) {return rightRet } return NULL;} / / destroy void BinaryTreeDestory (BTNode** root) {if (* root) {BinaryTreeDestory (& (* root)-> left); BinaryTreeDestory (& (* root)-> right); free (* root); * root = NULL }} / / binary tree depth / height int BinaryTreeDepth (BTNode* root) {if (root = = NULL) {return 0;} int leftDepth = BinaryTreeDepth (root- > left); int rightDepth = BinaryTreeDepth (root- > right); return leftDepth > rightDepth? LeftDepth + 1: rightDepth + 1;} # include "BinarryTree.h" int main () {BTNode* A = CreatTreeNode ('A'); BTNode* B = CreatTreeNode ('B'); BTNode* C = CreatTreeNode ('C'); BTNode* D = CreatTreeNode ('D'); BTNode* E = CreatTreeNode ('E'); BTNode* F = CreatTreeNode ('F'); A-> left = B A-> right = C; B-> left = D; C-> left = E; C-> right = F; return 0;} at this point, the study of "what is the principle of the chain binary tree structure of C language" is over, hoping to solve everyone's doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.