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

This article mainly explains "what is the common operation of binary tree in C language". The content of the explanation in this article is simple and clear, and it is easy to learn and understand. let's study and learn "what is the common operation of binary tree in C language"?

I. basic concepts

Each node has at most two subtrees, the left subtree and the right subtree, and the order cannot be reversed.

Nature:

1. There are at most 2 ^ (nmur1) elements on the nth layer of the non-empty binary tree.

2. A binary tree with a depth of h has at most 2 ^ h-1 nodes.

Full binary tree: all terminals are at the same level, and the degree of non-terminal nodes is 2.

If the depth of a full binary tree is h, then the number of nodes it contains must be 2 ^ h-1.

Complete binary tree: except for the largest level, that is, it becomes a full binary tree and all the nodes on the largest level are aligned to the left, that is, they are concentrated on the left side, and there can be no vacant positions.

For a complete binary tree, if a node is I, then the parent node is I, then I is the left child, and 2i+1 is the right child.

Second, storage structure

Sequential storage:

Store the data structure in a fixed array.

# define LENGTH 100typedef char datatype;typedef struct node {datatype data; int lchild,rchild; int parent;} Node;Node tree [LENGTH]; int length;int root

Although it has some advantages in traversing speed, it is a non-mainstream binary tree because of its large space. Binary trees are usually stored in chains.

Chain storage:

Typedef char datatype;typedef struct BinNode {datatype data; struct BinNode* lchild; struct BinNode* rchild;} BinNode;typedef BinNode* bintree; / / bintree itself is a pointer to a node

3. Traversal of binary tree

Traverse all node accesses of the upcoming tree and visit them only once. According to the different location of the root node, it is divided into pre-order traversal, middle-order traversal, post-order traversal.

Preorder traversal: root node-> left subtree-> right subtree

Traversal in the middle order: left subtree-> root node-> right subtree

Traversal in the following order: left subtree-> right subtree-> root node

For example: find three kinds of traversal of the following tree

Preorder traversal: abdefgc

Traversal in the middle order: debgfac

Traversal after order: edgfbca

Fourth, the realization of traversal

Recursive implementation (previous order traversal as an example, others are just slightly different in the location of the output)

Void preorder (bintree t) {if (t) {printf ("% c", t-> data); preorder (t-> lchild); preorder (t-> rchild);}}

Non-recursive implementation

Because you have to come back after traversing the root node, you must save it. Considering the characteristics of last-in, first-out, stack storage is selected. The quantity is determined and stored in a sequential stack.

# define SIZE 100typedef struct seqstack {bintree data [SIZE]; int tag [SIZE]; / / int top; / / top for subsequent traversal is the subscript of the array} seqstack;void push (seqstack * top bintree t) {if (s-> top = = SIZE) {printf ("the stack is full\ n");} else {s-> top++; s-> data [s-> top] = t }} bintree pop (seqstack * s) {if (s-> top = =-1) {return NULL;} else {s-> top--; return s-> data [s-> top+1];}}

1. Preorder traversal

Void preorder_dev (bintree t) {seqstack s; s.top =-1; / / because top represents the position in the array here, it is empty-1 if (! t) {printf ("the tree is empty\ n") } else {while (t | | s.stop! =-1) {while (t) {/ / as long as the node is not empty, it should be stored in the stack, independent of its left and right nodes ("% c", t-> data); push (& sMagnum t); tactit> lchild;} t=pop (& s); tweet-> rchild;}

2. Traversal of intermediate order

Void midorder (bintree t) {seqstack s; s.top =-1; if (! t) {printf ("the tree is empty!\ n");} else {while (t | | s.top! =-1) {while (t) {push (& lchild;); printf ("% c", t-> data); tweak-> rchild;}

3. Post-order traversal

Because the root node is visited once at the end of the post-order traversal, the root node is visited twice. The method of clamping the mark bit is adopted to solve this problem.

This code is very tangled, friends who have confidence in themselves can try to write it on their own. Anyway, I've been writing for a long time. Logic is not difficult. I drew a logic diagram:

Code:

Void postorder_dev (bintree t) {seqstack s; s.top =-1; if (! t) {printf ("the tree is empty!\ n");} else {while (t | | s.top! =-1) {/ / empty stack while t is empty. While (t) {push (& s.top); s.tag [s.top] = 0; / / set the access flag. 0 is the first visit, 1 is the second visit t = t-> lchild;} if (s.tags.top = = 0) {/ / the first visit, turn to the same layer right node t = s.data [s.top] / / t is empty when you go to the bottom on the left, there must be this step! S.tag [s.top] = 1; pop-> rchild;} else {while (s.tag [s.top] = = 1) {/ / find the next first access node in the stack, and there is no pop when exiting the loop, so it is its left child node t = pop (& s); printf ("% c", t-> data);} t = NULL; / / must be empty. Skip to the left and go straight to the right.

4. Hierarchical traversal: that is, each layer outputs from left to right

Elements need to be stored on a first-in-first-out basis, so queue storage is chosen.

Definition of the queue:

# define MAX 1000typedef struct seqqueue {bintree data [MAX]; int front; int rear;} seqqueue;void enter (seqqueue * Q bintree) {if (Q-> rear = = MAX) {printf ("the queue is full!\ n");} else {Q-> data [Q-> rear] = t; Q-> rear++;}} bintree del (seqqueue * Q) {if (Q-> front = = Q-> rear) {return NULL;} else {Q-> front++ Return Q-> data [Q-> front-1];}}

Ergodic implementation

Void level_tree (bintree t) {seqqueue q; bintree temp; q.front = q.rear = 0; if (! t) {printf ("the tree is empty\ n"); return;} enter (& Q enter); while (q.front! = q.rear) {t=del (& Q); printf ("% c", t-> data); if (t-> lchild) {enter (& Q q.rear t-> lchild) } if (t-> rchild) {enter (& Q _ rchild);}

5. Generate a binary tree using the results of preorder traversal.

/ / Recursive call, do not save a point, focus on only one point when you want to, because it will come back, do not track the program running, otherwise it is easy to add cycle void createtree (bintree * t) {datatype c; if ((c=getchar ()) = ='#') * t = NULL; else {* t = (bintree) malloc (sizeof (BinNode)); (* t)-> data = c; createtree (& (* t)-> lchild) Createtree (& * t)-> rchild);}}

6. Search of binary tree

Bintree search_tree (bintree search_tree datatype x) {if (! t) {return NULL;} if (t-> data = = x) {return t;} else {if (! search_tree (t-> datatype)) {return search_tree (t-> rchild,x);} return t;}}

7. Count the number of nodes

Int count_tree (bintree t) {if (t) {return (count_tree (t-> lchild) + count_tree (t-> rchild) + 1);} return 0;}

8. Compare whether the two trees are the same

Int is_equal (bintree T1 bintree T2) {if (! T1 & &! T2) {/ / is equal to return 1;} if (T1 & & T2 & & T1-> data = = T2-> data) {/ / if (is_equal (T1-> lchild,t2- > lchild)) if (is_equal (T1-> rchild,t2- > rchild)) {return 1;}} return 0;}

9. Find the depth of the binary tree

Int hight_tree (bintree t) {int if (! t) {return 0;} left = hight_tree (t-> lchild); right = hight_tree (t-> rchild); h = (left > right?left:right) + 1; return h } Thank you for your reading. the above is the content of "what is the common operation of binary tree in C language". After the study of this article, I believe you have a deeper understanding of what is the common operation of binary tree in C language. the specific use also needs to be verified by practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

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.