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

This article introduces the knowledge of "the method of binary tree recursion of C language data structure". In the operation of actual cases, many people will encounter such a dilemma. Next, let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Traversal algorithm of unary and binary trees

The essence of binary tree is traversing. After I have mastered it all over, the remaining problems can be easily solved.

1. Construct binary tree

"if you want to do good work, you must sharpen its tools."

1. So create a structure first.

two。 Manually construct a binary tree as shown in the figure.

Typedef int BTDataType;// defines a binary tree structure typedef struct BinaryTreeNode {int data;// node data struct BinartTreeNode* left;// left subtree struct BinartTreeNode* right;// right subtree} BTNode;// to construct a binary tree BTNode* BuyBTNode (BTDataType x) {BTNode* node = (BTNode*) malloc (sizeof (BTNode)); if (node = = NULL) {printf ("malloc fail\ n"); exit (- 1);} node- > data = xscape Node-> left = NULL;node- > right = NULL;return node } BTNode* CreatBinaryTree () {BTNode* node1 = BuyBTNode (1); BTNode* node2 = BuyBTNode (2); BTNode* node3 = BuyBTNode (3); BTNode* node4 = BuyBTNode (4); BTNode* node5 = BuyBTNode (5); BTNode* node6 = BuyBTNode (6); node1- > left = node2;node1- > right = node4;node2- > left = node3;node4- > left = node5;node4- > right = node6;return node1;} int main () {BTNode* tree = CreatBinaryTree (); return 0;} typedef int BTDataType / / define binary tree structure typedef struct BinaryTreeNode {int data;// node data struct BinartTreeNode* left;// left subtree struct BinartTreeNode* right;// right subtree} BTNode;// construct a binary tree BTNode* BuyBTNode (BTDataType x) {BTNode* node = (BTNode*) malloc (sizeof (BTNode)); if (node = = NULL) {printf ("malloc fail\ n") Exit (- 1);} node- > data = x; node- > left = NULL; node- > right = NULL; return node;} BTNode* CreatBinaryTree () {BTNode* node1 = BuyBTNode (1); BTNode* node2 = BuyBTNode (2); BTNode* node3 = BuyBTNode (3); BTNode* node4 = BuyBTNode (4) BTNode* node5 = BuyBTNode (5); BTNode* node6 = BuyBTNode (6); node1- > left = node2; node1- > right = node4; node2- > left = node3; node4- > left = node5; node4- > right = node6; return node1 } int main () {BTNode* tree = CreatBinaryTree (); return 0;} 2. Preorder traversal (recursive graph is the key point.)

Traversal order: root left subtree right subtree

Train of thought:

1. Think of each node as a tree.

two。 When the tree is empty.

3. When the tree is not empty, first traverse the left subtree, then traverse the right subtree

Note: the front, middle and back order traverses the differences only in the order in which the printf prints.

/ / binary tree preorder traversal void PreOrder (BTNode* root) {if (root = = NULL) {printf ("NULL"); return;} / / print before printf ("% d", root- > data); PreOrder (root- > left); PreOrder (root- > right);}

Print the results:

1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL

Recursive analysis diagram:

An omnipotent solution to recursive problems. Is to draw a recursive graph.

All the problems of the binary tree, if you can't, draw a recursive graph as soon as possible.

Because the recursion is too large and the picture is too small to see clearly, I separated the left subtree from the right subtree and took a picture.

1. The red line represents stack recursion.

two。 The green line represents the return.

Left subtree

Right subtree

3. Mid-order traversal

Traversal order: left subtree root right subtree

Void InOrder (BTNode* root) {if (root = = NULL) {printf ("NULL"); return;} InOrder (root- > left); / / print in the middle printf ("% d", root- > data); InOrder (root- > right);}

Print the result

NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL

4. Post-order traversal

Traversal order: left subtree right subtree root

Void PostOrder (BTNode* root) {if (root = = NULL) {printf ("NULL"); return;} PostOrder (root- > left); PostOrder (root- > right); / / print on the last printf ("% d", root- > data);}

Print the result

NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1

5. Sequence traversal

Train of thought:

With the help of the first-in-first-out nature, when the node of the upper layer comes out, the node of the next layer is brought in.

1. Put the root in the queue first.

two。 When the root node comes out, move the child in.

/ / sequence traverses void LevelOrder (BTNode* root) {/ / initialize the queue. Note that the pointer type is stored in the queue. Queue q; QueueInit (& Q); / / if the tree is not empty, start queuing if (root) {QueuePush (& Q, root);} / / if the tree is not empty, and start queuing left and right subtrees until the queue is empty. While (! QueueEmpty (& Q)) {BTNode* front = QueueFront (& Q); QueuePop (& Q); printf ("d", front- > data) / / if there are left and right subtrees, continue to join the team, otherwise do not join the team if (front- > left) {QueuePush (& Q, front- > left);} if (front- > right) {QueuePush (& Q, front- > right) }} / / remember to destroy queue printf ("\ n"); QueueDestory (& Q);} application of binary and binary tree traversal algorithm 1. Count the number of nodes

Idea: gradually divide the big problem into sub-problems.

Train of thought:

1. Returns 0 nodes when the tree is empty. (an empty tree does not mean that it is empty at the beginning, but recursively returns to the last tree for NULL)

two。 Returns its own 1 node + the number of nodes returned by the previous tree when the tree is not empty.

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

two。 Calculate the number of leaf nodes

Train of thought:

1. When the tree is NULL, 0. 0 is returned.

two。 Returns 1. 0 when neither of the subtrees is NULL.

3. Do not meet the above two situations, continue to recursive left and right subtrees.

/ / number of binary tree leaf nodes int BinaryTreeLeafSize (BTNode* root) {/ / if (root = = NULL) return 0 when the tree is empty; / / if (root- > left = = NULL & & root- > right = = NULL) return 1 when both subtrees are empty / * programs all come to this line, which means that the tree is not satisfied with the return situation, so continue to recurse the left and right subtrees. * / return BinaryTreeLeafSize (root- > left) + BinaryTreeLeafSize (root- > right);} 3. Find the number of nodes in the k layer

Idea: find the number of nodes in the third layer of the figure above.

1. From the point of view of the first layer, it is to find the number of nodes in the third layer.

two。 From the point of view of layer 2, it is to find the number of nodes in layer 2.

3. From the point of view of layer 3, it is to calculate the number of nodes in layer 1.

Train of thought:

1. Returns 0 when the tree is empty

two。 Returns 1 when k is 1.

3. If you are not satisfied with 1 and 2, continue to recurse the left and right subtrees.

/ / the number of nodes in the k layer of the binary tree int BinaryTreeLevelKSize (BTNode* root, int k) {/ / when the tree is empty, if (root = = NULL) return 0; / / when k is 1, if (k = 1) return 1; / / the program can go to this line, which means that the tree is not empty and k is not 1. Continue recursive return BinaryTreeLevelKSize (root- > left, KMUI 1) + BinaryTreeLevelKSize (root- > right, KMUI 1);} 4. Find a node with a value of x

Thoughts:

1. Write the smallest problem at the front as a limitation

two。 If the problem does not meet the minimum scale, it will continue to be recursive. Divide the problem into indivisible sub-problems step by step.

/ / binary tree looks for nodes with a value of x BTNode* BinaryTreeFind (BTNode* root, BTDataType x) {/ / when the tree is empty, if (root = = NULL) return NULL; / / when the value of the tree equals x, if (root- > data = = x) return root; / * walks to this line, indicating that the above conditions are not met. Start recursive left and right subtrees. If you find them, go back to * / BTNode* a = BinaryTreeFind (root- > left, x) step by step; if (a) {return a;} BTNode* b = BinaryTreeFind (root- > right, x); if (b) {return b } / / if there is no x, empty return NULL;} 5. Binary tree destruction

Idea: equivalent to the post-order traversal of a binary tree.

First, after traversing the left and right subtrees, begin to traverse the roots and free the roots.

/ / destroy void BinaryTreeDestory (BTNode* root) {if (root = = NULL) return; BinaryTreeDestory (root- > left); BinaryTreeDestory (root- > right); / / free free (root);} 6. Preorder traversal to build a binary tree

Train of thought:

Preorder traverses a string of characters, recursively traverses the binary tree, and returns the connection tree when it meets #.

To construct a binary tree by preorder traversing array "ABD##E#H##CF##G##"

# include # include typedef struct BTNodeTree {struct BTNodeTree* left; struct BTNodeTree* right; char val;} BTNode;// create a binary tree BTNode* CreateTree (char* a, int* pi) {/ / return null if (a [* pi] = ='#') {(* pi) +; return NULL if the tree is # } / / otherwise, build the node and let pi++, continue recursive BTNode* root = (BTNode*) malloc (sizeof (BTNode)); root- > val = a [(* pi) + +]; / / build the left and right subtree root- > left = CreateTree (a, pi); root- > right = CreateTree (a, pi); / / return the root node after construction. Return root;} / / traversal printing in the middle order. Void inorder (BTNode* root) {if (root = = NULL) return; inorder (root- > left); printf ("% c", root- > val); inorder (root- > right);} int main () {char a [100]; scanf ("% s", a); int I = 0; BTNode* tree = CreateTree (a, & I); inorder (tree); return 0;} 7. Judge whether a binary tree is a complete binary tree

Train of thought:

1. The sequence is traversed and the empty nodes are also queued.

two。 After going out to the empty node, all the data out of the queue will be a complete binary tree if all data is empty.

8. Find the depth of the binary tree

Idea: the maximum depth of the binary tree is equivalent to the maximum depth of the left and right subtrees + 1

Int maxDepth (struct TreeNode* root) {if (root = = NULL) {return 0;} size_t left = maxDepth (root- > left) + 1; size_t right = maxDepth (root- > right) + 1; if (right > left) {return right;} return left;} / / determine whether the binary tree is a complete binary tree bool BTreeComplete (BTNode* root) {Queue q; QueueInit (& Q) If (root) QueuePush (& Q, root); while (! QueueEmpty (& Q)) {BTNode* front = QueueFront (& Q); QueuePop (& Q); if (front = = NULL) break; QueuePush (& Q, front- > left) QueuePush (& Q, front- > right);} while (! QueueEmpty (& Q)) {BTNode* front = QueueFront (& Q); QueuePop (& Q); / / it is not a complete binary tree if (front) return false. } / / otherwise it is a complete binary tree return true;} triple and binary tree LeetCode topic

The following topics are simple topics for LeetCode

1. Single-valued binary tree

If each node of the binary tree has the same value, then the binary tree is a single-valued binary tree.

True; is returned only if the given tree is a single-valued binary tree, otherwise false is returned.

Thoughts:

1. See if the three parts of a tree are the same, and then continue to recurse the next tree until the tree is empty.

Bool isUnivalTree (struct TreeNode* root) {/ / when the tree is empty. If (root = = NULL) {return true;} / / when the right tree is not empty and the root! = left tree / / when the right tree is not empty and root! = right tree if (root- > left! = NULL & & root- > val! = root- > left- > val) return false; if (root- > right! = NULL & & root- > val! = root- > right- > val) return false / / if you can get to this line, it means that the value of the first-level tree is the same. Then recursive left and right subtrees. Return isUnivalTree (root- > left) & & isUnivalTree (root- > right); 2. Check whether the two trees are the same

Give you the root nodes p and Q of two binary trees and write a function to verify whether the two trees are the same.

Bool isSameTree (struct TreeNode* p, struct TreeNode* Q) {/ / when both trees are empty, if (p = = NULL & & Qtrees = NULL) return true; / / when one of the trees is empty, if (p = = NULL | | qtrees = NULL) return false; / / come here to show the existence of the two trees, compare the values of the two trees if (p-> val! = Q-> val) return false / / go here to show that the root nodes of the two trees are the same, and continue recursion until the left and right subtrees are judged. Return isSameTree (p-> left, Q-> left) & & isSameTree (p-> right, Q-> right);} 3. Symmetric binary tree

Give you a root of the root node of the binary tree and check whether it is axisymmetric.

Bool isSym (struct TreeNode* Q, struct TreeNode* p) {/ / when there is only one root node, if (Q = = NULL & & p = = NULL) return true; / / when one of the subtrees is empty, if (Q = = NULL | | p = = NULL) return false; / / the program walks to this line, indicating that the left and right nodes exist. When the two root nodes are not equal, if (Q-> val! = p-> val) return false; / / when this step shows that the left and right nodes are the same, the left and right subtrees return isSym (Q-> left, p-> right) & & isSym (Q-> right, p-> left);} bool isSymmetric (struct TreeNode* root) {/ / if (root = NULL) return true; return isSym (root- > left, root- > right) } 4. A subtree of another tree.

Train of thought:

The idea of judging whether two trees are the same is used in the previous question.

Bool isSameTree (struct TreeNode* p, struct TreeNode* Q) {/ / when both trees are empty, if (p = = NULL & & Qtrees = NULL) return true; / / when one of the trees is empty, if (p = = NULL | | qtrees = NULL) return false; / / come here to show the existence of the two trees, compare the values of the two trees if (p-> val! = Q-> val) return false / / go here to show that the root nodes of the two trees are the same, continue recursive return isSameTree (p-> left, Q-> left) & & isSameTree (p-> right, Q-> right);} bool isSubtree (struct TreeNode* root, struct TreeNode* subRoot) {/ / recursive end condition. When the root is empty, it does not mean that there are no nodes, but that all the subtrees have been traversed. Then unequally returns false if (root = = NULL) return false;// to indicate that the subtree is not empty and begins to compare whether the subtree is the same as sub. Bool a = isSameTree (root, subRoot); if (a) return a; / / go here to explain the difference, continue to recurse the left subtree and the right subtree, and return true if one is the same. Return isSubtree (root- > left, subRoot) | | isSubtree (root- > right, subRoot);}

5. Preorder traversal of binary tree

Topic thinking

1. Calculate the number of nodes and open up the size of the array.

two。 Preorder traversal is stored in an array

Int treeSize (struct TreeNode* root) {if (root = = NULL) return 0; return treeSize (root- > left) + treeSize (root- > right) + 1;} void preorder (int* a, struct TreeNode* root, int* I) {if (root = NULL) {return;} a [(* I) + +] = root- > val; preorder (AMR root-> left, I); preorder (ather root-> right, I) } int* preorderTraversal (struct TreeNode* root, int* returnSize) {/ / Compute tree has several nodes, and then open up the corresponding space int size = treeSize (root); int* a = (int*) malloc (sizeof (int) * size); int I = 0 X int / set subscript I * returnSize = size;// the array size / / preorder traversal to be returned is stored in the array. Preorder (a, root, & I); return a;} 6. Reverse binary tree

Give you the root node root of a binary tree, flip the binary tree, and return to its root node.

My BUG: just swap the values in the binary tree, but can't avoid null pointers. It's always a null pointer error, because root is always null and root- > data always encounters a null pointer.

So try to think more about exchanging addresses in the future.

Void _ invertTree (struct TreeNode* root) {if (root) {struct TreeNode* tmp = root- > left; root- > left = root- > right; root- > right = tmp; _ invertTree (root- > left); _ invertTree (root- > right);} struct TreeNode* invertTree (struct TreeNode* root) {_ invertTree (root); return root } "C language data structure binary tree recursion method" content is introduced here, thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.