Traversal of binary tree and common algorithms

Definition of traversal :

​ Access all nodes on a binary tree in a certain order , And each node is accessed only once ;

The importance of traversal :

​ When we need a binary tree , insert , delete , When searching and other operations , It is usually necessary to traverse a binary tree first , All said : Traversal is the basic operation of binary tree ;

Ergodic thinking :

*
The data structure of binary tree is a recursive definition ( Each node may contain children of the same structure ), So recursion can also be used for traversal , That is, if the node is not empty, continue to call recursively

*
Each node has three domains , Data vs , Left child pointer and right child pointer , Each traversal only needs to read data , Recursive left subtree , Recursive right subtree , These three operations

Three ergodic orders :

According to the different order of access to the three domains , There can be many different traversal orders , Generally, the access to subtrees is from left to right ;

set up :L To traverse the left subtree ,D To access the root node ,R To traverse the right subtree , And L Must be at R In front of

Three different traversal orders can be obtained :

Preorder traversal

The order of operation is DLR, First access root , Next ergodic Left subtree of root , Finally, traverse the root right subtree , Press the same for each subtree These three steps ( Primordial root , Rear left , To the right ) conduct

Middle order ergodic

The order of operation is LDR, First traverse the left subtree of the root , secondly Access root , Finally, traverse the root right subtree , Press the same for each subtree These three steps ( First left , Posterior root , To the right ) conduct

Postorder ergodic

The order of operation is LRD, First traverse the left subtree of the root , secondly Right subtree traversing root , Last access root , Same for every subtree Follow these three steps ( First left , Rear right , Last root ) conduct

level traversal

Hierarchical traversal is to traverse all nodes from top to bottom, from left to right , To achieve hierarchical traversal, a queue is usually needed , Add the nodes to be traversed in turn to the queue ;

Ergodic application

“ ergodic ” It is the basis of various operations of binary tree , Can be traversed Various operations on nodes in the process , as : For a known binary tree

* Finding the number of nodes in a binary tree
* Finding the number of leaf nodes in a binary tree ;
* Find the middle of a binary tree as 1 Number of nodes of
* Find the middle of a binary tree as 2 Number of nodes of
* 5 Finding the number of non terminal nodes in binary tree
* Exchange node left and right children
* Determine the level of node
wait ...

C Language implementation :
#include <stdio.h> // Data structure definition of binary linked list typedef struct TNode { char data; struct TNode
*lchild; struct TNode *rchild; } *BinTree, BinNode; // initialization // Pass in a pointer Make the pointer point to NULL
void initiate(BinTree *tree) { *tree = NULL; } // Create tree void create(BinTree *BT) {
printf(" Enter the current node value : (0 Create an empty node )\n"); char data; scanf(" %c",
&data);// Continuous input of shape and character . Character variables will receive line breaks , So add space if (data == 48) { *BT = NULL; return; }
else { // Create root node // Note that the size of the open space is the size of the structure
Instead of structure pointer size , Wrong writing will not cause problems immediately , However, memory access exceptions are likely to occur in the subsequent storage of data ( Tears ....) *BT =
malloc(sizeof(struct TNode)); // Data field assignment (*BT)->data = data; printf(" Input node %c Left child of
\n", data); create(&((*BT)->lchild));// Recursively create left subtree printf(" Input node %c Right child of \n", data);
create(&((*BT)->rchild));// Recursively create right subtree } } // Seeking parents' node ( Parent node ) BinNode *Parent(BinTree
tree, char x) { if (tree == NULL) return NULL; else if ((tree->lchild != NULL
&& tree->lchild->data == x) || (tree->rchild != NULL && tree->rchild->data ==
x)) return tree; else{ BinNode *node1 = Parent(tree->lchild, x); BinNode *node2
= Parent(tree->rchild, x); return node1 != NULL ? node1 : node2; } } // Preorder traversal
void PreOrder(BinTree tree) { if (tree) { // output data printf("%c ", tree->data);
// If it is not empty, continue to recursively judge the two child nodes of the node in order PreOrder(tree->lchild); PreOrder(tree->rchild); } }
// Middle order void InOrder(BinTree tree) { if (tree) { InOrder(tree->lchild); printf("%c
", tree->data); InOrder(tree->rchild); } } // Postsequence void PostOrder(BinTree tree) {
if (tree) { PostOrder(tree->lchild); PostOrder(tree->rchild); printf("%c ",
tree->data); } } // Destruction node recursion free All nodes void DestroyTree(BinTree *tree) { if (*tree
!= NULL) { printf("free %c \n", (*tree)->data); if ((*tree)->lchild) {
DestroyTree(&((*tree)->lchild)); } if ((*tree)->rchild) {
DestroyTree(&((*tree)->rchild)); } free(*tree); *tree = NULL; } } // Find element is X Node of
Using hierarchical traversal BinNode *FindNode(BinTree tree, char x) { if (tree == NULL) { return
NULL; } // queue BinNode *nodes[1000] = {}; // Queue head end position int front = 0, real = 0;
// Insert the root node at the end of the queue nodes[real] = tree; real += 1; // Continue if queue is not empty while (front != real) {
// Take out the output data of the queue header node BinNode *current = nodes[front]; if (current->data == x) { return
current; } front++; // If the current node has children ( Left / right ) Node will join the queue if (current->lchild != NULL) {
nodes[real] = current->lchild; real++; } if (current->rchild != NULL) {
nodes[real] = current->rchild; real++; } } return NULL; } // level traversal // Find element is X Node of
Using hierarchical traversal void LevelOrder(BinTree tree) { if (tree == NULL) { return; } // queue
BinNode *nodes[1000] = {}; // Queue head end position int front = 0, real = 0; // Insert the root node at the end of the queue
nodes[real] = tree; real += 1; // Continue if queue is not empty while (front != real) {
// Take out the output data of the queue header node BinNode *current = nodes[front]; printf("%2c", current->data);
front++; // If the current node has children ( Left / right ) Node will join the queue if (current->lchild != NULL) { nodes[real] =
current->lchild; real++; } if (current->rchild != NULL) { nodes[real] =
current->rchild; real++; } } } // lookup x Left child of BinNode *Lchild(BinTree tree, char x)
{ BinTree node = FindNode(tree, x); if (node != NULL) { return node->lchild; }
return NULL; } // lookup x Right child of BinNode *Rchild(BinTree tree, char x) { BinTree node =
FindNode(tree, x); if (node != NULL) { return node->rchild; } return NULL; }
// Find the number of leaf nodes int leafCount(BinTree *tree) { if (*tree == NULL) return 0;
// If left and right subtrees are empty, the node is a leaf , And we don't need to continue recursion in the future else if (!(*tree)->lchild && !(*tree)->rchild)
return 1; else // If the current node has a subtree , Then recursively left and right subtrees , Add results return leafCount(&((*tree)->lchild)) +
leafCount(&((*tree)->rchild)); } // Find the number of non leaf nodes int NotLeafCount(BinTree *tree) {
if (*tree == NULL) return 0; // If the left and right subtrees of this node are empty , Leaves , And don't continue recursion else if
(!(*tree)->lchild && !(*tree)->rchild) return 0; else
// If the current node has left and right subtrees , Non leaf node ( number +1), Getting non leaf nodes in left and right subtrees recursively , Add results return
NotLeafCount(&((*tree)->lchild)) + NotLeafCount(&((*tree)->rchild)) + 1; }
// Find the height of the tree ( depth ) int DepthCount(BinTree *tree) { if (*tree == NULL) return 0; else{
// Depth if current node is not empty +1 Plus the height of the subtree , int lc = DepthCount(&((*tree)->lchild)) + 1; int rc =
DepthCount(&((*tree)->rchild)) + 1; return lc > rc?lc:rc;// Taking the depth of two subtrees Maximum } }
// Delete left subtree void RemoveLeft(BinNode *node){ if (!node) return; if (node->lchild)
DestroyTree(&(node->lchild)); node->lchild = NULL; } // Delete right subtree void
RemoveRight(BinNode *node){ if (!node) return; if (node->rchild)
DestroyTree(&(node->rchild)); node->rchild = NULL; } int main() { BinTree tree;
create(&tree); BinNode *node = Parent(tree, 'G');
printf("G The parent node of is %c\n",node->data); BinNode *node2 = Lchild(tree, 'D');
printf("D The left child node of is %c\n",node2->data); BinNode *node3 = Rchild(tree, 'D');
printf("D The right child node of is %c\n",node3->data); printf(" The preorder traversal is :"); PreOrder(tree);
printf("\n"); printf(" Middle order traversal is :"); InOrder(tree); printf("\n"); printf(" Subsequent traversal is :");
PostOrder(tree); printf("\n"); printf(" Level traversal is :"); LevelOrder(tree);
printf("\n"); int a = leafCount(&tree); printf(" The number of leaf nodes is %d\n",a); int b =
NotLeafCount(&tree); printf(" The number of non leaf nodes is %d\n",b); int c = DepthCount(&tree);
printf(" Depth is %d\n",c); // lookup F node BinNode *node4 = FindNode(tree,'C');
RemoveLeft(node4); printf(" delete C Left child back traversal of :"); LevelOrder(tree); printf("\n");
RemoveRight(node4); printf(" delete C Right child backward traversal of :"); LevelOrder(tree); printf("\n");
// Destroy trees printf(" Destroy trees \n"); DestroyTree(&tree); printf(" Traverse after destruction :");
LevelOrder(tree); printf("\n"); printf("Hello, World!\n"); return 0; }
test :

The test data is the following binary tree :

Run the program copy and paste the following :
A B D G 0 0 H 0 0 E 0 0 C K 0 0 F I 0 J 0 0 0
Special thanks :iammomo

Technology
©2019-2020 Toolsou All rights reserved,
" Cephalosporin wine Say go and go "? DANGER ! Don't drink alcohol when taking these drugs Programmer Tanabata Valentine's Day confession code China Lunar Rover “ Moon rabbit No.2 ” A strange rock was found on the moon use C++ I want to talk to you “ Prototype mode ” ( copy / copy constructor ) Software testing BUG describe Random forest R Language implementation TP6 Application examples of verifier and correct verification data Google says home office affects work efficiency !2021 Return to offline office in 2010 Message quality platform series | Full link troubleshooting Free download of documents : To introduce you to a few useful free download URL