Implementation of binary tree structure

1. Binary tree related operations
2. Storage structure of binary tree
- 2.1. Sequential storage structure of binary tree
- 2.2. Binary linked list storage structure
- 2.3 Three-fork linked list storage structure
3. Operation of traversal of binary tree
- 3.1. Recursively traverse a binary tree
- 3.2. Non-recursive traversal of a binary tree
- - 3.2.1. Non-recursive algorithm for binary tree traversal based on task analysis
  - 3.2.2. Non-recursive algorithm for binary tree traversal based on search path analysis
- 3.3. Binary tree level traversal algorithm
4. Application of binary tree traversal algorithm
- 4.1. Create binary linked list storage structure of binary tree
- - 4.1.1. A recursive algorithm to create a binary linked list by reading node values in the string form of “root left subtree right subtree”
  - 4.1.2. Non-recursive algorithm creates binary chain structure of binary tree
- 4.2. Create an expression binary linked list with arithmetic expressions (application of post-order traversal)
- 4.3. Other applications of binary tree traversal algorithm
- - 4.3.1. Find the depth of binary tree
  - 4.3.2. Find the number of leaf nodes of the binary tree
  - 4.3.3. Displaying a binary tree as a concave table
  - 4.3.4. Displaying a binary tree as a generalized table
  - 4.3.5. Find the ancestor of any node

1. Binary tree related operations

(1) Initialize an empty binary tree;
(2) Destroy the binary tree rooted at T;
(3) Insert a node with parent as the parent and x as the left child;
(4) Delete the left subtree with parent as the parent;
(5) Find the node whose node value is x on the binary tree;
(6) Preorder traversal of the binary tree;
(7) In-order traversal of the binary tree;
(8) Post-order traversal of the binary tree;
(9) Hierarchical traversal of the binary tree.

2. Storage structure of binary tree

2.1. Sequential storage structure of binary tree

The sequential storage structure is to open up a continuous space to store the data of the binary tree. Judging from the property 5 of the binary tree, the full binary tree and the complete binary tree can be numbered, and the operation of the number can easily find the relationship between the nodes. For a general binary tree, it can be “completed” by adding nodes without data, and then numbered. But at this time, the space will be wasted to a certain extent, and the worst case is the case of the right single branch tree.
Conclusion: The sequential storage structure is suitable for storing complete binary trees, which is convenient for finding parents and children.

2.2. Binary linked list storage structure

Find the storage addresses of the left and right children of the node through the pointers of the left and right children in the pointer field.
Properties: In a binary linked list containing n nodes, there are n + 1 null pointer fields
Conclusion: Binary linked list is convenient to find children, but not convenient to find parents.

2.3 Three-fork linked list storage structure

On the basis of the binary linked list, add a pointer to the parent node.
Conclusion: It is convenient to find child and parent nodes.

3. Traversal operation of binary tree

The traversal of the binary tree is to traverse each node in the binary tree in a certain order, so that each node is visited only once. Traversal operations can convert nonlinear structures into linear structures

3.1. Recursively traverse the binary tree

(1) Pre-order traversal; (2) In-order traversal; (3) Post-order traversal

//Recursively traverse the binary tree
void preorder(BiTree T)//traversal DLR in preorder
{<!-- -->
if (T)//End when T is an empty tree - recursion end sign
{<!-- -->
printf("%c", T->data);//Access the root node
preorder(T->lchild);//traverse the left subtree in preorder
preorder(T->rchild);//Traverse right subtree in preorder
}

}
void inorder(BiTree T)//In-order traversal LDR
{<!-- -->
if (T)//End when T is an empty tree - recursion end sign
{<!-- -->
inorder(T->lchild);//traverse the left subtree in order
printf("%c", T->data);//Access the root node
inorder(T->rchild);//traversing the right subtree in order
}
}
void postorder(BiTree T)//post-order traversal LRD
{<!-- -->
if (T)//End when T is an empty tree - recursion end sign
{<!-- -->
inorder(T->lchild);//post-order traversal of the left subtree
inorder(T->rchild);//post-order traversal of the right subtree
printf("%c", T->data);//Access the root node
}
}

3.2. Non-recursive traversal of binary trees

3.2.1. Non-recursive algorithm for binary tree traversal based on task analysis

The root node of each subtree is responsible for three tasks: the traversal of the left subtree, the visit of the root node and the traversal of the right subtree. Take inorder traversal as an example:
The task of the root node is divided into according to nature: traversal and access, represented by 1 and 0.
When pushing into the stack, assign tasks to non-empty nodes according to the in-order; when popping out of the stack, process the tasks according to the nature of the tasks.
【Algorithm implementation】

//Non-recursive traversal of the binary tree
void InOrder_iter(BiTree T)
{<!-- -->
//Using the stack to implement in-order traversal of the binary tree, T is the head pointer pointing to the root node of the binary tree
Stack S;
StackInit( &S);
STDataType e;
e.ptr = T; e.task = 1;//e is a structure variable of a stack element
if (T)StackPush( & amp;S, e);//arrange the initial task
while (!StackEmpty( & amp;S))//in-order traversal
{<!-- -->
e = StackTop( &S);
StackPop( & S);
if (e.task == 0)printf("%c", e.ptr->data);//e.task == 0 processing access tasks
else
{<!-- -->
BiTree p = e.ptr;
e.ptr = p->rchild;
if (e.ptr)StackPush( & amp;S, e);//traverse the right subtree
e.ptr = p; e.task = 0;
StackPush( & amp;S, e);//Access the root node
e.ptr = p->lchild; e.task = 1;
if (e.ptr)StackPush( & amp;S, e);//traverse the left subtree
}//end_else
}//end_while
}

3.2.2. Non-recursive algorithm for binary tree traversal based on search path analysis

From the traversal of the binary tree, we can know that each node has three chances to meet during the traversal process. Take postorder traversal as an example: the first encounter is before the stack is pushed, if the left subtree of the node is not empty, the node is pushed into the stack; if the left subtree traversal ends, it returns to the top of the stack, and the second time Meet; if the right subtree of the top node of the stack is not empty, start traversing the right subtree. After the traversal of the right subtree ends, return to the top of the stack and meet for the third time. At this time, the data of the node at the top of the stack is accessed and popped up. Mark the character array, mark the first encounter as L, and mark the second encounter as R. When the mark array is R, it means that the node traversal is over, accessed and popped up.
(1) Push into the stack: the address of the node encountered for the first time is pushed into the stack, marked L
(2) Modify the mark: the second encounter, change the mark L to R
(3) Pop out and access.
【Algorithm Implementation】

//Find the bottom left node of the subtree
BiTree PriGoFarLeft(BiTree T, Stack* S, char c[])
{<!-- -->
if (!T) return NULL;
while (T->lchild)//find
{<!-- -->
StackPush(S, T); c[S->_top] = 'L';//The first encounter, push into the stack
T = T->lchild;
}
return T;
}
void NrPostorder(BiTree T)//Non-recursive algorithm for postorder traversal based on path analysis
{<!-- -->
BiTree t;
Stack S;
StackInit( &S);
char lrtag[STACK_INITMAXSIZE] = {<!-- --> 0 };//tag array
t = PriGoFarLeft(T, &S, lrtag);
while (t)
{<!-- -->
lrtag[S._top] = 'R';//The second encounter, modify the tag
//Find the bottom left node of the right subtree of t
if (t->rchild)t = PriGoFarLeft(t->rchild, &S, lrtag);
else
{<!-- -->
while (!StackEmpty( & amp;S) & amp; & amp; lrtag[S._top] == 'R')//The third encounter, pop the stack, and output
{<!-- -->
StackPop( & S);
printf("%c", t->data);
}
}
if (!StackEmpty( & amp;S))t = StackTop( & amp;S);
else t = NULL;
}//end_while
}

3.3. Binary tree hierarchy traversal algorithm

Hierarchical traversal is to traverse the binary tree from top to bottom and from left to right. This is in line with the principle of first-in first-out, which is a queue structure, and the nodes can be put into the queue one by one and out of the queue one by one.
【Algorithm implementation】

//Hierarchical traversal of the binary tree
void LayerBitree(BiTree T)
{<!-- -->
Queue Q;
InitQueue( & amp;Q);//Initialize the queue
if (T)EnQueue( & amp;Q, T);//Enter the queue
while (!QueueEmpty( & amp;Q))
{<!-- -->
BiTree p = DeQueue( & amp;Q); printf("%c", p->data);//Exit the queue and access the node
if (p->lchild)EnQueue( & amp;Q, p->lchild);//The left subtree root enters the queue
if (p->rchild)EnQueue( & amp;Q, p->rchild);//The right subtree root enters the queue
}//end_while
}

4. Application of binary tree traversal algorithm

4.1. Create a binary linked list storage structure of a binary tree

4.1.1. A recursive algorithm to create a binary linked list by reading node values in the string form of “root left subtree right subtree”

Read the value of each node in the order of preorder traversal (empty nodes are represented by #), and change the statement of accessing nodes in the preorder traversal algorithm to create a new node.
【Algorithm implementation】

void crt_tree(BiTree* T)//recursive form
{<!-- -->
char ch = getchar();
if (ch == '#')*T = NULL;
else
{<!-- -->
//Create root node
*T = (BiTree)malloc(sizeof(BiNode));
if (*T == NULL)
{<!-- -->
perror("malloc fail");
return;
}
(*T)->data = ch;
//Create left subtree
crt_tree( & amp;((*T)->lchild));
//Create right subtree
crt_tree( & amp;((*T)->rchild));
}//end_else
}

4.1.2. Non-recursive algorithm creates binary chain structure of binary tree

(1) The strings of the generalized table of the binary tree create a binary linked list
The order in which node values appear is consistent with preorder traversal. If both the left and right subtrees are empty, the subtree is of the form “root”. Since the parent node is created before the left child node, it is represented by the flag quantity tag. When encountering a left parenthesis, first push the previously created parent node into the stack, set key=1, and start creating the left subtree; encounter a comma, indicating that the left child node has been created, set key=2, and start creating the right child tree; when a right parenthesis is encountered, it means that the subtree is created and the root of the subtree is popped out of the stack. When a letter is encountered, a leaf node is created. If key=1, link the leaf node as the left child of the parent node; if key=2, link the leaf node as the right child of the top node of the stack until the stack is empty.
【Algorithm Implementation】

void CreateBiTree(BiTree* BT, char* s)//The character string of the generalized table of the binary tree creates a binary linked list
{<!-- -->
char ch;
int i, key;
structure
{<!-- -->
BiTree node[50];
int top;
}ptrNode;//The sequence stack is used to store the address of the root of the subtree in the creation process
ptrNode. top = -1;
BiTree p = NULL;
*BT = NULL;
ch = s[0];
i = 1;
while (ch != '0')
{<!-- -->
switch (ch)
{<!-- -->
case '(':
ptrNode.node[ + + ptrNode.top] = p;//Encounter a left parenthesis, the node address is pushed into the stack
key = 1;//mark to create the root of the left subtree
break;
case ')':
ptrNode.top--;//Encountered the right bracket, indicating that the creation of the right subtree is completed
break;
case ',':
key = 2;//price to create the root of the right subtree
break;
default:
//Create a leaf node
p = (BiTree)malloc(sizeof(BiNode));
if (p == NULL)
{<!-- -->
perror("malloc fail");
return;
}
p->data = ch;
p->lchild = p->rchild = NULL;
//Create root node
if (*BT == NULL)*BT = p;
else
{<!-- -->
if (key == 1)//Create the root of the left subtree
ptrNode.node[ptrNode.top]->lchild = p;
else if (key == 2)//Create the right subtree
ptrNode.node[ptrNode.top]->rchild = p;
}
}//end_switch
ch = s[i + + ];
}//end_while
}

(2) A non-recursive algorithm that reads in edges to create a binary linked list (application of hierarchical traversal)
Input the edges of the binary tree in order from top to bottom and from left to right. The edge information is (father, child, lrflag), where father is the father node, child is the child node, and lrflag is 0 for the left child. 1 means right child. This algorithm needs a queue to save the created node addresses.
Algorithm Core:
① Every time an edge is read, a child node is generated and used as a leaf node, and then the pointer of the node is saved in the queue.
② Find the parent node pointer of the node from the head of the queue. If the head of the queue is not, go out of the queue until the head of the queue is the parent node pointer of the node. Then, according to the value of lrflag, establish the relationship between the left and right children of the parent node.
【Algorithm Implementation】

void Create_BiTree(BiTree* T)//Read in the edge to create a binary linked list - the application of hierarchical traversal
{<!-- -->
Queue Q;
InitQueue(Q);
*T = NULL;
char fa, ch;
int lrflag;
scanf("%c%c%d", &fa, &ch, &lrflag); getchar();
while (ch != '#')
{<!-- -->
BiTree p = (BiTree)malloc(sizeof(BiNode));
if (p == NULL)
{<!-- -->
perror("malloc fail");
return;
}
p->data = ch;//Create a child node
p->lchild = p->rchild = NULL;//Make a child node
EnQueue(Q, p);//pointer into the queue
if (fa == '#')*T = p;//Create root node
else
{<!-- -->
BiTree s = GetHead(Q);//Get the queue head element (pointer value)
while (s->data != fa)//find the parent node in the queue
{<!-- -->
DeQueue(Q);
s = GetHead(Q);
}
if (lrflag == 0)s->lchild = p;//link left child node
else s->rchild = p;//link right child node
}
scanf("%c%c%d", &fa, &ch, &lrflag); getchar();
}//end_while
}

(3) Determine the binary tree by the traversal sequence of the binary tree (application of pre-order traversal)
Question: Knowing the traversal sequence of the binary tree, how to determine the binary tree?

Knowing the pre-order sequence and in-order sequence of the binary tree, a binary tree can be uniquely determined.
Proof: Through the root node + inorder sequence, the nodes of the left and right subtrees of the root node and the preorder relationship and inorder relationship of the left and right subtree nodes can be known. Through the recursive algorithm, a binary tree can be uniquely determined

The process of constructing the binary tree:
①Create a root node according to the first element of the preorder sequence.
②Find the element in the inorder sequence, and determine the inorder sequence of the left and right subtrees of the root node.
③ Determine the preorder sequence of the left and right subtrees in the preorder sequence.
④ Establish the left subtree from the preorder sequence and inorder sequence of the left subtree.
⑤ Establish the right subtree from the preorder sequence and inorder sequence of the right subtree.

void CrtBT(BiTree* T, char pre[], char ino[], int ps, int is, int n)//Determine the binary tree by the traversal sequence of the binary tree (application of pre-order traversal)
{<!-- -->
//pre[ps..ps + n-1] is the preorder sequence of the binary tree, n is the number of characters in the sequence
//ino[is..is + n-1] is the inorder sequence of the binary tree
//ps is the position of the first character of the preorder sequence, the initial value is 0, is is the position of the first character of the inorder sequence, the initial value is 0
if (n == 0)*T = NULL;
else//Query the root in the inorder sequence, k is -1, not found, otherwise k is the position of the root in the inorder sequence
{<!-- -->
int k = Search(ino, pre[ps]);
if (k == -1)*T = NULL;
else
{<!-- -->
if (!(*T = (BiTree)malloc(sizeof(BiNode))))exit(0);
(*T)->data = pre[ps];//Establish root node
if (k == is)(*T)->lchild = NULL;//No left subtree
//Create left subtree
else CrtBT( & amp;((*T)->lchild), pre, ino, ps + 1, is, k - is);//k-is represents the number of nodes in the left subtree
if (k == is + n - 1)(*T)->rchild = NULL;//No right subtree
//Create right subtree
else CrtBT( & amp;((*T)->rchild), pre, ino, ps + 1 + (k-is), k + 1,n-(k-is)-1);

}
}
}

A binary tree can be uniquely determined by the post-order sequence and in-order sequence of the binary tree
A binary tree cannot be uniquely determined by the preorder sequence and postorder sequence of the binary tree

4.2. Create an expression binary linked list with arithmetic expressions (application of post-order traversal)

A preorder sequence is a prefix expression of a primitive expression; an inorder sequence is an infix expression represented by a primitive expression; a postorder sequence is a postfix expression of a primitive expression.
The characteristics of the expression binary tree are as follows.
(1) All leaf nodes are operands.
(2) All branch nodes are operators, the calculation result of the left subtree is the first operand of the branch node operator, and the calculation result of the right subtree is the second operand of the branch node operator .
(3) The calculation order of the value of the expression is performed in the order of the post-order traversal.
Use two stacks, one for storing operators and one for storing the address of the root node of the subtree.
【Algorithm Implementation】

void CrtExptree(BiTree* T, char exp[])//main function: create expression binary linked list
{<!-- -->
SubTreeStack PTR;//PTR is the subtree stack
SqCharStack PND;//PND is the operator stack
char* p = exp;
char ch, c;
ch = p[0];
int_CharStack_exp( & amp;PND); pushChar( & amp;PND, '#');//Initialize operator stack
int_SubtreeStack_exp( & amp;PTR);//Initialize the subtree stack
while ((c = getChar_top(PND)) != '#' || ch != '#')
{<!-- -->
if (!IN(ch))CrtNode(T, & amp;PTR, ch);//ch is not an operator, create a child node and enter the PTR stack
else
{<!-- -->
switch (ch)//ch is an operator
{<!-- -->
case '('://'(' operator into the operator stack
pushChar( &PND, ch); break;
case ')'://')' operator, pop out until the operator'(' ends the stack
popChar( &PND, &c);
while (c != '(')
{<!-- -->
CrtSubtree(T, & amp;PTR, c);//Build a binary tree and merge it into the PTR stack
popChar( &PND, &c);
}
break;
default://other operators
while ((c != getChar_Top(PND)) != '#' & amp; & amp; precede(c, ch))
{<!-- -->
//When the operator at the top of the stack is not #
//And when the current operator has a lower priority than the operator on the top of the stack
//Take the operator at the top of the stack to build a subtree, and then pop it out of the stack
CrtSubtree(T, &PTR, c);
popChar( &PND, &c);
}
if (ch != '#')pushChar( & amp;PND, ch);
}//end_switch
}//end_else
if (ch != '#')
{<!-- -->
p++;
ch = *p;
}
}//end_while
popSubtree( & amp;PTR, T);// pop the binary tree root address from the stack
}
void CrtNode(BiTree* T, SubTreeStack* PTR, char ch)//subfunction: function to create leaf nodes
{<!-- -->
//Create a child node and enter the PTR stack
if (!(*T = (BiTree)malloc(sizeof(BiNode))))exit(0);
(*T)->data = ch; (*T)->lchild = (*T)->rchild = NULL;
pushSubtree(PTR, *T);
}
void CrtSubtree(BiTree* T, SubTreeStack* PTR, char c)//subfunction: create subtree function
{<!-- -->
//Create a subtree and merge it into the PTR stack
BiTree lc, rc;
if (!(*T = (BiTree)malloc(sizeof(BiNode))))exit(0);
(*T)->data = c;
popSubtree(PTR, &rc); (*T)->rchild = rc;
popSubtree(PTR, &lc); (*T)->lchild = rc;
pushSubtree(PTR, *T);
}

4.3. Other applications of binary tree traversal algorithm

4.3.1. Find the depth of the binary tree

Analysis: Based on the post-order traversal of the binary tree, if the binary tree is empty, its depth is 0; otherwise, you can find the maximum depth of the left subtree and the right subtree and add 1.
【Algorithm implementation】

int depth(BiTree T)//Find the depth of binary tree
{<!-- -->
if (T == NULL) return 0;
else
{<!-- -->
int depl = depth(T->lchild);//Left subtree depth
int depr = depth(T->rchild);//right subtree depth
if (depl > depr) return depl + 1;
else return depr + 1;
}
}

4.3.2. Find the number of leaf nodes of the binary tree

Analysis: Based on the in-order traversal of the binary tree, if the binary tree is empty, the number of leaf nodes is 0; otherwise, determine whether a node is a leaf node, if it is a calculator, add 1
【Algorithm implementation】

void leafcount(BiTree T, int* count)//find the number of leaf nodes of the binary tree
{<!-- -->
if (T == NULL) return;
else
{<!-- -->
leafcount(T->lchild, count);
if (T->lchild == NULL & amp; & amp; T->rchild == NULL)(*count) + + ;//Remove the judgment condition, and calculate the number of nodes in the entire binary tree
leafcount(T->rchild, count);
}
}

4.3.3. Display binary tree in form of concave table

Analysis Based on the pre-order traversal of the binary tree, the length of the line segment is determined for each node and the layer it is in.
【Algorithm Implementation】

void dispBitree(BiTree T, int level, char c)//Display the binary tree in the form of concave table
{<!-- -->
int i, k;
if (T)
{<!-- -->
for (i = 1; i < level; i ++ )putchar(' ');
printf("%c(%c) + ", T->data, c);//Display nodes and labels
for (k = i + 4; k < 20; k ++ )putchar('-');
putchar('\
');
dispBitree(T->lchild, level + 2, 'L');
dispBitree(T->rchild, level + 2, 'R');
}
}

4.3.4. Display binary tree as generalized table

Analysis: The node order of the generalized table form of the binary tree is consistent with the preorder traversal of the binary tree. It is only necessary to judge when to output the left and right parentheses and commas based on the preorder traversal algorithm. Can.
【Algorithm Implementation】

void gListBiTree(BiTree T)//Display the binary tree in the form of a generalized table
{<!-- -->
if (T)
{<!-- -->
printf("%c", T->data);
if (T->lchild != NULL || T->rchild != NULL)
{<!-- -->
printf("(");
gListBiTree(T->lchild);
if (T->rchild)
{<!-- -->
printf(",");
gListBiTree(T->rchild);
}
printf(")");
}
}
}

4.3.5. Find the ancestor of any node

Analysis: Traversing in post-order, once you find a specified node, you only need to push all its nodes into the stack in order from near to far.
【Algorithm implementation】

int an_BitreeNode(BiTree T, char x, STACK* S)// Find the ancestor of any node in the binary tree
{<!-- -->
// Find the ancestor of x
if (T == NULL) return 0;
if (T->data == x) return 1;
if (an_BitreeNode(T->lchild, x, S) == 1 || an_BitreeNode(T->rchild, x, S) == 1)
{<!-- -->
//Once x is found on the left or right subtree of T, the parents of x are pushed onto the stack
push(S, T->data);//ancestor advanced stack
return 1;
}
return 0;
}