408 Data Structure Tree Algorithm

## Chapter 4: The Tree ##

### 4.1 Sequential storage of binary trees

```C
#define MAXSIZE 16
typedef int ElemType;
typedef struct {
ElemType data[MAXSIZE];
int size;
}Tree;

//Initialize the binary tree
void initTree(Tree& T) {
for (int i = 0; i < MAXSIZE; i++) {
[i] = 0; //assume 0 means empty node
}
= 0;
}
//Creating a binary tree
void createTree(Tree& T) {
ElemType x;
scanf("%d", &x);
int i = 0;
while (x != 999) {
[i++] = x;
++;
scanf("%d", &x);
}
}
//Print binary tree
void printTree(Tree T) {
for (int i = 0; i < ; i++) {
printf("%d ", [i]);
}
printf("\n");
}

```

01. A binary tree is known to be stored in a sequential storage structure, design an algorithm to find the two numbered i and j respectively
The value of the node's nearest common ancestor node.

```C
ElemType findCommonAncestors(Tree T, int i, int j) {
if ([i] ! = 0 && [j] ! = 0) { // both nodes are present in the subsequent operation
// the parent node has a subscript of x/2
/*
1 Corresponding array [1,2,3,4,5,6,7]
/ \ Corresponding to subscripts [0,1,2,3,4,5,6]
2 3
/ \ / \ Note: If the subscript starts from 0.
4 5 6 7 The left child subscript of i is i*2 +1 The right child subscript is i*2+2
The parent of i is (i-1)/2
If the subscript starts at 1
i's left child is i*2,right child is i*2+1
The parent of i is i/2
*/
while (i != j) {
if (i > j) {
i /= 2;
}
else {
j /= 2;
}
}
return [i];
}
return 0; //0 means empty
}
```

### 4.2 Chained storage of binary trees

Structure of a binary tree

```C
typedef int ElemType;
typedef struct BiTNode {
ElemType data; //data field
BiTNode* lchild; // left child pointer
BiTNode* rchild; // right child pointer
}BiTNode,*BiTree;
```

Creating a binary tree

```C
//Pre-order creation of binary trees
void createTree(BiTree& T) {
ElemType x;
scanf("%d", &x);
if (x == 0) { // use 0 for null node
return;
}
else {
T = (BiTNode *)malloc(sizeof(BiTNode)); //create node structure
T->data = x;
T->lchild = NULL;
T->rchild = NULL;
createTree(T->lchild); // recursively create the left subtree
createTree(T->rchild); //recursively create the right subtree
}
}
```

Pre-middle-post-order traversal of binary trees (recursion)

```C
// Pre-order traversal recursion
void preOrder(BiTree T) {
if (T == NULL) {
return;
}
printf("%d ", T->data);
preOrder(T->lchild);
preOrder(T->rchild);
}

//Middle order traversal recursion
void inOrder(BiTree T) {
if (T == NULL) {
return;
}
inOrder(T->lchild);
printf("%d ", T->data);
inOrder(T->rchild);
}

// Posterior order traversal recursion
void postOrder(BiTree T) {
if (T == NULL) {
return;
}
postOrder(T->lchild);
postOrder(T->rchild);
printf("%d ", T->data);
}
```

You can find that only the print position is different when traversing in the pre-intermediate and post-intermediate order, and the other code is exactly the same, so why do you get 3 correct traversal results when printing in different positions? For this reason, we first understand the recursive order.

```C
void f(BiTree T) {
if (T == NULL) {
return;
}
/*
Recursive order: each function will come three times.
The first time to print the first order, the second time to print the middle order, and the third time to print the last order.
*/
//Precedence
f(T->lchild);
//Middle order
f(T->rchild);
// Post-sequence
}
```

![image-20240119190904833](typora-user-images\)

If you print in all three positions, the output is: A B D D D D B E E E E E B A C F F F F C G G G G C A

Precedence traversal: print on first pass, precedence sequence: A B D E C F G

Medium order traversal: print on second pass, medium order sequence: d b e a f c g

Posterior traversal: print on third pass, posterior sequence: d e b f g c a

Pre-order traversal of a binary tree (non-recursive)

```C
// Pre-order traversal non-recursive
void preOrderNoRecursion(BiTree T) {
SqStack S;
initStack(S);
BiTNode* p = T; //p as a traversal pointer to the tree
while (p || !isEmpty(S)) { // if p is not empty or there are elements on the stack
if (p) {
printf("%d ", p->data); //print the value of the current node
push(S, p); //current element
p = p->lchild; // go all the way to the left subtree first
}
else {
//If the traversal reaches an empty node at this point, it proves that the path has gone all the way to the end, and pops up and then goes back to traversing the right subtree.
BiTNode* top = pop(S);
p = top->rchild;
}
}
}
```

Middle-order traversal of a binary tree (non-recursive)

```C
//Middle-order traversal non-recursive
void inOrderNoRecursion(BiTree T) {
SqStack S;
initStack(S);
BiTNode* p = T;
while (p || !isEmpty(S)) { // if p is not empty or there are elements on the stack
if (p) {
push(S, p); //still all the way to the left
p = p->lchild;
}
else {
BiTNode* top = pop(S); // left to head, pop the top stack element and print it
printf("%d ", top->data);
p = top->rchild; //then go the way of the right subtree of the popped element
}
}
}
```

Posterior order traversal of a binary tree (non-recursive)

```C
// Post-order traversal non-recursive
void postOrderNoRecursion(BiTree T) {
SqStack S;
initStack(S);
BiTNode* p = T;
BiTNode* last = NULL; // used to record the most recent element out of the stack
while (p || !isEmpty(S)) {
if (p) {
push(S, p); //go all the way to the left and enter the stack element, go straight to the top
p = p->lchild;
}
else{
BiTNode* top = peek(S); //get top stack element
// When there is no right child at the top of the stack or the right child at the top of the stack is the most recent element to exit the stack.
if (top->rchild == NULL||top->rchild == last) {
last = pop(S); // exit the stack and update the most recent element to exit the stack
printf("%d ", top->data); //print out the stack elements
}
//On the contrary
else {
p = top->rchild; // go and make the right child go the same way
}
}
}
}
```

Pre-order traversal of a binary tree (non-recursive idea 2)

```C
void preOrderNoRecursion2(BiTree T) {
SqStack S;
initStack(S);
BiTNode* p = T;
if (p) {
push(S, p); //first put the first element on the stack
while (!isEmpty(S)) {
BiTNode* top = pop(S); //pop the top stack element
printf("%d ", top->data); //print the top element of the stack
if (top->rchild ! = NULL) { // if there is a right child put the right child on the stack
push(S,top->rchild);
}
if (top->lchild ! = NULL) { // have left child then put left child on stack
push(S, top->lchild);
}
}
}
}
```

Posterior order traversal of a binary tree (non-recursive idea 2)

```C
//Post-order traversal non-recursive idea 2
void postOrderNoRecursion2(BiTree T) {
SqStack S,S2;
initStack(S);
initStack(S2);
BiTNode* p = T;
if (p) {
push(S, p);
while (!isEmpty(S)) { //first get the head, right, left traversal order, the head of the right-left elements in turn into the stack to the auxiliary stack S2, the final S2 is saved in the head of the right-left of the inverse order of the right-left of the head of the left-right head of the order of the traversal of the results of the latter order
BiTNode* top = pop(S);
push(S2,top);
if (top->lchild != NULL) {
push(S, top->lchild);
}
if (top->rchild != NULL) {
push(S, top->rchild);
}
}
}
while (!isEmpty(S2)) { // take the elements in S2 out of the stack in turn
BiTNode* p = pop(S2);
printf("%d ", p->data);
}
}
```

Hierarchical traversal of a binary tree

```C
// Hierarchical traversal
void levelOrder(BiTree T) {
Queue Q;
initQueue(Q);
BiTNode* p = T;
if (p) {
enQueue(Q, p); //first queue the root node element
while (!isEmpty(Q)) {
BiTNode* head = deQueue(Q); // out of queue
printf("%d "T, head->data); //print out the queue elements
if (head->lchild) { // if the outgoing element has a left child first put the left child into the queue
enQueue(Q, head->lchild);
}
if (head->rchild) { // if the outgoing element has a right child then put the left child into the queue
enQueue(Q, head->rchild);
}
}
}
}
```

### 4.3 Binary Tree Topics

01.Try to give the algorithm for hierarchical traversal of a binary tree from bottom up and right to left. .

```C
void inverLevelOrder(BiTree T) {
// Use the results of the hierarchical traversal into the stack, in order to print the elements of the stack can be
Queue Q;
SqStack S;
initQueue(Q);
initStack(S);
BiTNode* p = T;
if (p) {
enQueue(Q, p);
while (!isEmpty(Q)) {
BiTNode* head = deQueue(Q);// head out of queue
push(S, head);
if (head->lchild) {
enQueue(Q, head->lchild); //with left child left child into queue
}
if (head->rchild) {
enQueue(Q, head->rchild); //with right child right child into queue
}
}
}
while (!isEmpty(S)) { // the inverse sequence of the traversal level traversal that exists in the stack at this point, just print it in order
BiTNode* cur = pop(S);
printf("%d ", cur->data);
}
printf("\n");
}
```

02. Assuming that the binary tree is stored in a binary linked table storage structure, design a non-recursive algorithm to find the height of the binary tree.

```C
//Non-recursive
int getTreeHigh2(BiTree T) {
if (T == NULL) { // if it is an empty tree directly return 0
return 0;
}
// Count the height of the tree when doing hierarchical traversal of the tree.
Queue Q;
initQueue(Q);
BiTNode* p = T;
enQueue(Q, p);
int count = 0; //count is the size of the final tree to be returned
while (!isEmpty(Q)) {
int size = ; // Get the length of the current queue, indicating how many nodes are in the layer. The for loop indicates the end of the layer traversal, and the number of layers count+1 after the end.
for (int i = 0; i < size; i++) {
BiTNode* head = deQueue(Q);
if (head->lchild) {
enQueue(Q, head->lchild);
}
if (head->rchild) {
enQueue(Q, head->rchild);
}
}
count++;
}
return count;
}
```

```C
//recursive
int getTreeHigh(BiTree T) {
if (T == NULL) { // if it is an empty tree directly return 0
return 0;
}
if (T->lchild == NULL && T->rchild == NULL) { // if it is a leaf node height 1
return 1;
}
int lhigh = getTreeHigh(T->lchild); // recursively find the height of the left subtree
int rhigh = getTreeHigh(T->rchild); // recursively find the height of the right subtree
//Total height equals the maximum height of the left and right subtrees + their own height1
return lhigh >= rhigh ? lhigh + 1 : rhigh + 1;
}
```

03. Find the minimum depth of a tree

```C
/*
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes on the shortest path from the root node to the nearest leaf node.
Note: A leaf node is a node that has no children.
Example 3 Minimum depth of 2
/ \
9 20
/ \
15 7

10 Minimum depth of 3
/ \
15 20
/ \
25 30
*/
// Recursive version
int minDepth(BiTree T) {
if (T == NULL) {
return 0;
}
// if it is a leaf node height is 1
/*if (T->lchild == NULL && T->rchild == NULL) {
return 1;
}*/
int lhigh = getTreeHigh2(T->lchild);
int rhigh = getTreeHigh2(T->rchild);
if (lhigh == 0) {
return rhigh + 1;
}
if (rhigh == 0) {
return lhigh + 1;
}
return lhigh <= rhigh ? lhigh + 1 : rhigh + 1;

}
// Non-recursive implementation using hierarchical traversal
int minDepth2(BiTree T) {
if (T == NULL) {
return 0;
}
Queue Q;
initQueue(Q);
BiTNode* p = T;
enQueue(Q, p);
int count = 0; // used to record the number of layers (height)
while (!isEmpty(Q)) {
int size = ;
count++;
for (int i = 0; i < size; i++) {
BiTNode* head = deQueue(Q);
if (head->lchild == NULL && head->rchild == NULL) {
return count;
}
if (head->lchild) {
enQueue(Q, head->lchild);
}
if (head->rchild) {
enQueue(Q, head->rchild);
}
}
}
return count;
}
```

04. Determine if two trees are the same

```C
/*
04.Given two binary trees with root nodes T1 and T2, write a function to check if the two trees are the same.
Two trees are considered identical if they are structurally identical and the nodes have the same value.
1 1
/ \ / \
2 3 2 3

20 20
/ \ / \
30 30
*/
bool isSameTree(BiTree T1, BiTree T2) {
if (T1 == NULL && T2 == NULL) {
return true;
}
if (T1 == NULL && T2 != NULL || T1 != NULL && T2 == NULL) {
return false;
}
if (T1->data != T2->data) {
return false;
}
return isSameTree(T1->lchild, T2->lchild) && isSameTree(T1->rchild, T2->rchild);
}
```

05. Determine if a binary tree is symmetric

![image-20240120111605764](typora-user-images\)

```C
//05. Determining whether a binary tree is symmetric or not
bool checkSymmetricTree(BiTree T) {
if (T == NULL) { // consider the empty tree to be symmetric
return true;
}
return check(T->lchild, T->rchild);
}
bool check(BiTree left, BiTree right) {
if (left == NULL && right == NULL) { // if left and right children are null return true
return true;
}
// Return false if one of the left and right children is empty and one is not.
if (left == NULL && right != NULL || left != NULL && right == NULL) {
return false;
}
// If the values of the left and right children are not equal return false
if (left->data != right->data) {
return false;
}
return check(left->lchild, right->rchild) && check(left->rchild, right->lchild);
}
```

06. Flipping a binary tree

```C
/*
06.Given the root node T of a binary tree , flip the binary tree.
Example:
4 4
/ \ / \
2 7 -> 7 2
/ \ / \ / \ / \
1 3 6 9 9 6 3 1

2 2
/ \ -> / \
1 3 3 1

*/
void invertTree(BiTree& T) {
if (T == NULL) {
return;
}
BiTNode* temp = T->lchild;
T->lchild = T->rchild;
T->rchild = temp;
invertTree(T->lchild);
invertTree(T->rchild);
}
```

07. Determine if it is a balanced binary tree

```C
/*
07.Given a binary tree, determine if it is a highly balanced binary tree.
A height-balanced binary tree is defined as a binary tree in which the absolute value of the difference between the heights of the left and right subtrees of each node does not exceed 1
Example:

3 1
/ \ / \
9 20 2 2
/ \ / \
15 7 3 3
/ \
4 4

bool isBalanced(BiTree T) {
if (T == NULL) {
return true;
}
int d1 = getTreeHigh2(T->lchild);
int d2 = getTreeHigh2(T->rchild);
return d1 - d2 <= 1 && d1 - d2 >= -1 && isBalanced(T->lchild) && isBalanced(T->rchild);
}
```

08. Construct a binary tree using the result of the forward traversal and the result of the middle traversal.

```C
//Preceding traversal of the array is from [L1,R1], intermediate traversal of the array is from [L2,R2].
BiTree f(ElemType pre[], int L1, int R1, ElemType in[], int L2, int R2) {
if (L1 > R1 || L2 > R2) {
return NULL;
}
BiTNode* head = (BiTNode*)malloc(sizeof(BiTNode));
head->data = pre[L1];
int find = L2;
while (in[find] != pre[L1]) {
find++;
}
head->lchild = f(pre, L1 + 1, L1 + find - L2, in, L2, find - 1);
head->rchild = f(pre, L1 + find - L2 + 1, R1, in, find + 1, R2);
return head;
}
/**
Given two arrays of integers pre and in, where pre is a prior traversal of a binary tree and in is a mid-order traversal of the same tree, and the size of the arrays is n
*/
BiTree buildTree(ElemType pre[], ElemType in[], int n) {
if (n == 0) {
return NULL;
}
return f(pre, 0, n - 1, in, 0, n - 1);
}
```

9. Construct a binary tree using the result of the middle-order traversal and the result of the back-order traversal

```C
BiTree f(ElemType pre[], int L1, int R1, ElemType in[], int L2, int R2) {
if(L1>R1){
return NULL;
}
BiTNode* head = (BiTNode* )malloc(sizeof(BiTNode));
head->val = post[R1];
int find = L2;
while(in[find]!=post[R1]){
find++;
}
head->left = f(post,L1,L1+find-1-L2,in,L2,find-1);
head->right = f(post,L1+find-L2,R1-1,in,find+1,R2);
return head;
}

BiTree buildTree(ElemType pre[], ElemType in[], int n) {
if (n == 0) {
return NULL;
}
return f(pre, 0, n - 1, in, 0, n - 1);
}
```

10. A binary tree is stored in the form of a binary linked list, try to write an algorithm to determine whether a given binary tree is a complete binary tree.

```C

bool isComplete2(BiTree T) {
if (T == NULL) {
return true;
}
Queue Q;
initQueue(Q);
BiTNode* p = T;
enQueue(Q, p);
while(!isEmpty(Q)){
BiTNode* head = deQueue(Q);
if (head) {
enQueue(Q, head->lchild);
enQueue(Q, head->rchild);
}
else {
while (!isEmpty(Q)) {
head = deQueue(Q);
if (head) {
return false;
}
}
}
}
return true;
}
```

11. Assuming that binary trees are stored using a binary linked list storage structure, try to design an algorithm to compute - all of the binary trees in a given binary tree
The number of double branch nodes.

```C
int getDNodesCount(BiTree T) {
/*if (T == NULL) {
return 0;
}

int d1 = getDNodesCount(T->lchild);
int d2 = getDNodesCount(T->rchild);
if (T->lchild && T->rchild) {
return 1 + d1 + d2;
}
else {
return d1 + d2;
}*/

}

int getDNodesCount2(BiTree T) {
Stack S;
initStack(S);
BiTNode* p = T;
int count = 0;
while (p || !isEmpty(S)) {
if (p) {
if (p->lchild && p->rchild) {
count++;
}
push(S, p);
p = p->lchild;
}
else {
BiTNode* top = pop(S);
p = top->rchild;
}
}
return count;
}
```

12. Assuming that the binary tree is stored using a binary chain storage structure, design an algorithm that seeks to traverse the sequence in prior order the kth (1<=k<=
Number of nodes in a binary tree) the value of a node.

```C
//recursive
int count = 1;
ElemType prefindK(BiTree T, int k) {
if (T == NULL) {
return -1;
}
if (k == count) {
return T->data;
}
count++;
ElemType x= prefindK(T->lchild, k);
if (x != -1) {
return x;
}
return prefindK(T->rchild, k);
}
//Non-recursive
ElemType prefindK2(BiTree T, int k) {
Stack S;
initStack(S);
BiTNode* p = T;
int count = 0;// used to record the current traversal to the number of
while (p || !isEmpty(S)) {
if (p) {
count++;
if (count == k) {
return p->data;
}
push(S, p);
p = p->lchild;
}
else {
BiTNode* top = pop(S);
p = top->rchild;
}
}
return -1;
}
```

13. A binary tree is known to be stored as a binary chained table, write an algorithm to accomplish this:For each node in the tree whose element has a value of x, delete the subtree that is rooted by it and free the corresponding space.

```C
//13. A binary tree is known to be stored in a binary linked table, write an algorithm to accomplish this:For each node in the tree whose element value is x, delete the subtree rooted at it and free the corresponding space.
void freeNode(BiTNode* root) {
if (root) {
freeNode(root->lchild);
freeNode(root->rchild);
free(root);
}
}

void delX(BiTree& T, ElemType x) {
if (T == NULL) {
return;
}
if (T->data == x) {
freeNode(T);
return;
}
Queue Q;
initQueue(Q);
BiTNode* p = T;
enQueue(Q, p);
while (!isEmpty(Q)) {
BiTNode* head = deQueue(Q);
if (head->lchild) {
if (head->lchild->data == x) {
freeNode(head->lchild);
head->lchild = NULL;
}
else {
enQueue(Q, head->lchild);
}
}
if (head->rchild) {
if (head->rchild->data == x) {
freeNode(head->rchild);
head->rchild = NULL;
}
else {
enQueue(Q, head->rchild);
}
}
}
}
```

14. Find the node with value x in a binary tree, try to write an algorithm (in C) to print all the ancestors of the node with value x, assuming that there is not more than one node with value x.

```C
//14. Find the node with value x in a binary tree and try to write an algorithm (in C) to print all the ancestors of the node with value x. Assume that there is not more than one node with value x.
// Algorithm idea 1
ElemType* pre = (ElemType *)malloc(sizeof(ElemType)*16);
ElemType* post = (ElemType*)malloc(sizeof(ElemType)*16);
void g(BiTree T,int *i,int *j) {
if (T == NULL) {
return;
}
pre[(*i)++] = T->data; // store the result of the prior traversal
g(T->lchild,i,j);
g(T->rchild,i,j);
post[(*j)++] = T->data; // store the result of the post order traversal
}
void findAncestors(BiTree T, ElemType x) {
int n = 0, m = 0;
g(T,&n,&m);
int i = 0;
int j = 0;
for (; i < n && pre[i] != x; i++);
for (; j < n && post[j] != x; j++);
for (int p = 0; p < i; p++) {
for (int q = j + 1; q < n; q++) {
if (pre[p] == post[q]) {
printf("%d ", pre[p]);
}
}
}
printf("\n");
}
// Algorithm idea 2, after using backward traversal to find x, the element saved in the stack is the ancestor node
void findAncestors2(BiTree T,ElemType x) {
if (T == NULL) {
return;
}
Stack S;
initStack(S);
BiTNode* p = T;
BiTNode* last = NULL;
while (p || !isEmpty(S)) {
if (p) {
push(S, p);
p = p->lchild;
}
else {
BiTNode* top = peek(S);
if (top->rchild == NULL || top->rchild == last) {
last = pop(S);
if (top->data == x) {
while (!isEmpty(S)) {
last = pop(S);
printf("%d ", last->data);
}
}
}
else {
p = top->rchild;
}
}
}
}

```

15. Assuming that the binary tree has a two-and-chained table storage structure, design an algorithm to find the width of the non-empty binary tree b (i.e., the number of nodes in the layer with the highest number of nodes).

```C
//15. Assuming that the binary tree is in a two again linked list storage structure, design an algorithm to find the width of the non-empty binary tree b (i.e., the number of nodes in the layer with the highest number of nodes).
int getTreeWidth(BiTree T) {
if (T == NULL) {
return 0;
}
Queue Q;
initQueue(Q);
int max = 0;
BiTNode* p = T;
enQueue(Q, p);
while (!isEmpty(Q)) {
int size = ;
max = size >= max ? size:max;
for (int i = 0; i < size; i++) {
BiTNode *head = deQueue(Q);
if (head->lchild) {
enQueue(Q,head->lchild);
}
if (head->rchild) {
enQueue(Q,head->rchild);
}
}
}
return max;
}
```

16. There is a full two-by-two tree (all nodes have different values), and it is known that its precedence sequence is pre.
Design an algorithm to solve for its posterior
Sequence post

```C
void findPost(ElemType pre[], int L1, int R1, ElemType post[], int L2, int R2) {

if (R1 >= L1) {
post[R2] = pre[L1];
int mid = (R1-L1) / 2;
findPost(pre, L1 + 1, L1 + mid, post, L2, L2 + mid - 1);
findPost(pre, L1 + mid + 1, R1, post, L2 + mid, R2 - 1);
}

//if (R1 >= L1) {
// post[R2] = pre[L1];
// int mid = (L1 + R1) / 2; // calculate mid correctly
// int leftLength = mid - L1; // length of the left subtree
// // Recursive call to left subtree
// findPost(pre, L1 + 1, L1 + leftLength, post, L2, L2 + leftLength - 1);

// // Recursive call to right subtree
// findPost(pre, L1 + leftLength + 1, R1, post, L2 + leftLength, R2 - 1);
//}
}
```

17.Design an algorithm to link the leaf nodes of a binary tree into a single linked table in left to right order, with the head pointer at the head of the table.The binary tree is stored as a binary chained table, and the linking is done by using the right pointer field of the leaf nodes to store the single linked table pointer.

```C
// Recursive version preorder
BiTNode* head = NULL, * prior = NULL;
BiTNode* findAllLeafNodes(BiTree T){
if (T == NULL) {
return NULL;
}
if (T->lchild == NULL && T->rchild == NULL) {
if (prior == NULL) {
head = T;
prior = T;
}
else {
prior->rchild = T;
prior = T;
}
}
findAllLeafNodes(T->lchild);
findAllLeafNodes(T->rchild);
return head;
}
//Print Test
void printAllLeafNodes(BiTNode* root) {
BiTNode* p = root;
while (p) {
printf("%d->", p->data);
p = p->rchild;
}
printf("\n");
}

// Non-recursive middle order
BiTNode* findAllLeafNodes(BiTree T){
BiTNode* head =NULL, * pre = NULL;
Stack S;
initStack(S);
BiTNode* p = T;
while (p || !isEmpty(S)) {
if (p) {
push(S, p);
p = p->lchild;
}
else {
BiTNode* top = pop(S);
if (top->lchild == NULL && top->rchild == NULL) {
if (pre == NULL) {
head = top;
pre = top;
}
else {
pre->rchild = top;
pre = top;
}
}
p = top->rchild;
}
}
return head;
}
```

18. Determine if two trees are similar

```C
bool isSimilar(BiTree T1, BiTree T2) {
if (T1 == NULL && T2 == NULL) {
return true;
}
if (T1 == NULL && T2 != NULL || T1 != NULL && T2 == NULL) {
return false;
}
return isSimilar(T1->lchild, T2->lchild) && isSimilar(T1->rchild, T2->rchild);
}
```

19. Design an algorithm to determine whether a binary tree is a binary sorted tree or not

```C
ElemType min = -32767; // denotes -∞
//Design algorithms for determining whether a binary tree is a binary sorted tree
bool isBinarySortTree(BiTree T) {
bool b1, b2;
if (T == NULL) { // if it is the empty tree, consider it a binary sorted tree
return true;
}
else {
b1 = isBinarySortTree(T->lchild); // determine if the left subtree is a binary sort tree
if (b1 == false || min >= T->data) { // one condition that does not hold does not satisfy the definition of a binary sort tree return false
return false;
}
min = T->data; // let the minimum be the root node of the current left subtree for comparison with the right subtree
b2 = isBinarySortTree(T->rchild);
return b2;
}
}
//Method 2, middle-order traversal non-recursively determines if a binary tree is a binary sorted tree
bool isBinarySortTree2(BiTree T) {
if (T == NULL) {
return true;
}
BiTNode* p = T;
Stack S;
initStack(S);
while (!isEmpty(S) || p) {
if (p) {
push(S, p);
p = p->lchild;
}
else {
BiTNode* top = pop(S);
if (top->data <= min) {
return false;
}
min = top->data;
p = top->rchild;
}
}
return true;
}
```

20.Design the algorithm to find the level of a node in a binary sorted tree

```C
//Design an algorithm to find the level of a node in a binary sorted tree.
int getNodeHigh(BiTree T, ElemType x) {
if (T == NULL) {
return 0;
}
Queue Q;
initQueue(Q);
BiTNode* p = T;
enQueue(Q, p);
int height = 0; // used to record the number of layers (height)
while (!isEmpty(Q)) {
int size = ;
height++;
for (int i = 0; i < size; i++) {
BiTNode* head = deQueue(Q);
if (head->data == x) {
return height;
}
if (head->lchild) {
enQueue(Q, head->lchild);
}
if (head->rchild) {
enQueue(Q, head->rchild);
}
}
}
return 0; //0 means no x-node found.
}
//Design an algorithm to find the level of a node in a binary sorted tree2
int getNodeHigh2(BiTree T, ElemType x) {
if (T ==NULL) {
return 0;
}
int height = 0;
BiTNode* p = T;
while (p) {
count++;
if (x < p->data) {
p = p->lchild;
}
else if (p->data < x) {
p = p->rchild;
}
else {
return height;
}
}
return 0;
}
//Design recursive ideas for finding the level of a node in a binary sorted tree3
int getNodeHigh3(BiTree T, ElemType x,int height) {
if (T == NULL) {
return 0;
}
if (x < T->data) {
return getNodeHigh3(T->lchild, x, height+1);
}
else if (T->data < x) {
return getNodeHigh3(T->rchild, x, height+1);
}
else {
return height;
}
}
```

21.Design an algorithm for counting the number of binary tree nodes on chained storage constructs.

```C
//Design an algorithm for counting the number of binary tree nodes on a chained storage construct (recursive idea 1)
int nodeCount = 0;
int getCount(BiTree T) {
if (T == NULL) {
return 0;
}
getCount(T->lchild);
getCount(T->rchild);
nodeCount++;
return nodeCount;
}
//Design an algorithm for counting the number of binary tree nodes on a chained storage construct (recursive idea 2)
int getCount2(BiTree T) {
if (T == NULL) {
return 0;
}
return getCount2(T->lchild) + getCount2(T->rchild) + 1;
}
```

22.Design an algorithm to find node X in a binary sorted tree

```C
//Design an algorithm to find node X in a binary sorted tree
BiTNode* getX(BiTree T, BiTNode* x) {
if (T == NULL) {
return NULL; // tree is empty, node X not found
}
if (x->data == T->data) {
return T; // node X found
}
else if (x->data < T->data) {
return getX(T->lchild, x); // lookup in left subtree
}
else {
return getX(T->rchild, x); // lookup in right subtree
}
}
```

23. Create a binary sorted tree

```C
//Creating a binary sorted tree
void insertNode(BiTree& T, ElemType data) {
if (T == NULL) {
// If the tree is empty, a new node is created as the root node
BiTNode* newNode = (BiTNode*)malloc(sizeof(BiTNode));
newNode->data = data;
newNode->lchild = NULL;
newNode->rchild = NULL;
T = newNode;
}
else {
// If the tree is not empty, insert nodes according to the nature of a binary sorted tree
if (data < T->data) {
insertNode(T->lchild, data); // insert into left subtree
}
else {
insertNode(T->rchild, data); // insert into right subtree
}
}
}
```

24. Assuming that the binary tree is stored using a chained storage structure, with root as the root node and p as the node at any given point, write a non-recursive algorithm to find the path from the root node to p. [Xi'an Electronic Science and Technology University]& lt;/b>

```C
void getPathToNode(BiTree root, BiTNode* p) {}
//Implementation using backward traversal of binary trees
void getPathToNode(BiTree root, ElemType p) {
if (root == NULL) {
return;
}
Stack S,S2;
initStack(S);
initStack(S2); //S2 is used to store the path
BiTNode* cur = root;
BiTNode* last = NULL;

while (!isEmpty(S) || cur) {
if (cur) {
push(S, cur);
cur = cur->lchild;
}
else {
BiTNode* top = peek(S);

if (top->rchild == NULL || top->rchild == last) {
if (top->data == p) {
while (!isEmpty(S)) {
push(S2, pop(S));
}
break;
}
last = pop(S);

}
else {
cur = top->rchild;
}
}
}
//print path
while (!isEmpty(S2)) {
BiTNode* top = pop(S2);
printf("%d->", top->data);
}
printf("\n");
}
```

25.Knowing that there is a binary tree represented by a binary linked table, write a program that outputs all the nodes on the longest branch from the root node to the leaf node (assuming it is unique) and write the algorithmic idea. [NUAA 2006 VI (10 points)]

Let the node structure of a binary tree be (lchild,data,rchild), where lchild and rchild are pointers to the roots of the left and right subtrees respectively, and data is character data. Write an algorithm to find the length of the first longest path in any binary tree and output the values of the nodes on this path. Beijing University of Posts and Telecommunications 1997 VIII (20 points)] .

```C

void findLongestPath(BiTree root) {
if (root == NULL) {
return;
}
Stack S;
initStack(S);
BiTNode* p = root;
BiTNode* last = NULL;
BiTNode* longNode = NULL;
int max = 0;
while (p || !isEmpty(S)) {
if (p) {
push(S, p);
p = p->lchild;
}
else {
BiTNode* top = peek(S);
if (top->rchild == NULL || top->rchild == last) {
if (top->lchild == NULL && top->rchild == NULL) {
if ( > max) {
max = ;
longNode = top;
}
}
last = pop(S);
}
else {
p = top->rchild;
}
}
}
getPathToNode(root, longNode->data);
}
```

26. Let the nodes of a binary tree have the following structure: (lchild,data,rchild), the pointer variable T is pointing to the root node of the tree, try to design an algorithm to print all the paths that arrive at the leaf nodes from the root node .

```C
// Recursion 1
void printAllPaths(BiTree T, int path[], int pathLen) {
if (T == NULL) {
return;
}
path[pathLen++] = T->data;
if (T->lchild == NULL && T->rchild == NULL) {
printf("Path： ");
for (int i = 0; i < pathLen; i++) {
printf("%d ", path[i]);
}
printf("\n");
}
else {
printAllPaths(T->lchild, path, pathLen);
printAllPaths(T->rchild, path, pathLen);
}
}
//Thought 2 Recursive Understanding of Backtracking Processes
int len = 0;
void printAllPaths2(BiTree T, int path[]) {
if (T == NULL) {
return;
}
path[len++] = T->data;
if (T->lchild == NULL && T->rchild == NULL) {
printf("Path： ");
for (int i = 0; i < len; i++) {
printf("%d ", path[i]);
}
printf("\n");
}
else {
printAllPaths2(T->lchild, path);
printAllPaths2(T->rchild, path);
}
len--;
}
//thought 3 non-recursive
void printAllPaths2(BiTree T) {
if (T == NULL) {
return;
}
Stack S;
initStack(S);
int path[100];
int len = 0;
BiTNode* p = T;
BiTNode* last = NULL;
while (!isEmpty(S) || p) {
if (p) {
push(S, p);
path[len++] = p->data;
p = p->lchild;
}
else {
BiTNode* top = peek(S);
if (top->rchild == NULL || top->rchild == last) {
last = pop(S);
if (top->lchild == NULL && top->rchild == NULL) {
for (int i = 0; i < len; i++) {
printf("%d ", path[i]);
}
printf("\n");
}
len--;
}
else {
p = top->rchild;
}
}
}
}
```

27.Design an algorithm to return a pointer to the last node of the precedence sequence of a binary tree T. Require that it be in a non-recursive form and that it not allow the use of a stack. .

```C
BiTNode* getLastPreNode(BiTree T) {
BiTNode* p = T;
while (p) {
if (p->rchild) {
p = p->rchild;
}
else if (p->lchild) {
p = p->lchild;
}
else {
return p;
}
}
return NULL;
}
```

28. Given an integer n, how many varieties of binary search trees are there consisting of exactly n nodes with nodes of different values from 1 to n? Return the number of species of binary search trees that satisfy the question. .

![image-20240411003420630](C:\Users\asus\AppData\Roaming\Typora\typora-user-images\)

```C
//different binary search trees
int numTrees(int n) {
int* dp = (int*)malloc(sizeof(int) * (n + 1));
for (int i = 0; i < n + 1; i++) {
dp[i] = 0;
}
dp[0] = 1;
dp[1] = 1;
for (int j = 2; j < n + 1; j++) {
for (int i = 0; i < j; i++) {
dp[j] += dp[i] * dp[j - 1 - i];
}
}
/*for (int i = 0; i < n; i++) {
printf("(%d,%d)\n", i, n - 1-i);
}*/
return dp[n];
}
```

29. Give you the root node of a binary tree, root, and an integer targetSum representing the target sum. Determine whether there exists a path from the root node to the leaf nodes in the tree, where the sum of the values of all the nodes in the path equals the target sum targetSum. If so, returns true; otherwise, returns false.

```C
// Recursive thought 1
bool hasPathSum(BiTree root, int targetSum) {
if (root == NULL) {
return false;
}
targetSum -= root->data;
if (root->lchild == NULL && root->rchild == NULL) {
return targetSum == 0;
}
return hasPathSum(root->lchild, targetSum) || hasPathSum(root->rchild, targetSum);
}

// Recursive thought 2
bool res = false;
int sum = 0;
void process(BiTree root, int targetSum) {
if (root == NULL) {
return;
}
sum += root->data;
if (root->lchild == NULL && root->rchild == NULL && sum == targetSum) {
res = true;
}
process(root->lchild, targetSum);
process(root->rchild, targetSum);
sum -= root->data;
}
bool hasPathSum2(BiTree root, int targetSum) {
if (root == NULL) {
return false;
}
process(root, targetSum);
return res;
}

// Non-recursive idea 1
bool hasPathSum3(BiTree root, int targetSum) {
if (root == NULL) {
return false;
}
Stack S;
initStack(S);
BiTNode* p = root;
BiTNode* last = NULL;
int sum = 0;
while (!isEmpty(S) || p) {
if (p) {
sum += p->data;
if (p->lchild == NULL && p->rchild == NULL && sum == targetSum) {
return true;
}
push(S, p);
p = p->lchild;
}
else {
BiTNode * top = peek(S);
if (top->rchild == NULL || top->rchild == last) {
last = pop(S);
sum -= last->data;
}
else {
p = top->rchild;
}
}
}
return false;
}

// Non-recursive idea 2
bool hasPathSum4(BiTree root, int targetSum) {
if (root == NULL) {
return false;
}
Stack S;
initStack(S);
BiTNode* p = root;
BiTNode* last = NULL;
while (!isEmpty(S) || p) {
if (p) {
targetSum -= p->data;
if (p->lchild == NULL && p->rchild == NULL && 0 == targetSum) {
return true;
}
push(S, p);
p = p->lchild;
}
else {
BiTNode* top = peek(S);
if (top->rchild == NULL || top->rchild == last) {
last = pop(S);
targetSum += last->data;
}
else {
p = top->rchild;
}
}
}
return false;
}
```

30.A binary tree is a single-valued binary tree if every node of the tree has the same value.
Returns true only if the given tree is a single-valued binary tree; otherwise returns false.

```C
/*
30. A binary tree is a single-valued binary tree if each node has the same value.
Returns true only if the given tree is a single-valued binary tree; otherwise returns false.
*/

int val = 0;
bool res = true;
void process(BiTree root) {
if (root == NULL) {
return;
}
if (root->data != val) {
res = false;
}
process(root->lchild);
process(root->rchild);
}
bool isUnivalTree(BiTree root) {
if (root == NULL) {
return true;
}
val = root->data;
process(root);
return res;
}
// Recursive thought 2
bool process(BiTree T,int val) {
if (T == NULL) {
return true;
}
if (T->data != val) {
return false;
}
return process(T->lchild, val) && process(T->rchild, val);
}
bool isUnivalTree(BiTree root) {
if (root == NULL) {
return true;
}
return process(root, root->data);
}
```

31. Write a recursive program to rotate a binary tree 90 degrees counterclockwise to print it out .

![image-20240411222216088](C:\Users\asus\AppData\Roaming\Typora\typora-user-images\)

```C
void printTreeSideways(BiTree root, int depth) {
if (root == NULL) {
return;
}
printTreeSideways(root->rchild, depth + 1);
for (int i = 0; i < depth; i++) {
printf(" ");
}
printf("%d\n", root->data);
printTreeSideways(root->lchild, depth + 1);
}
```

32. It is known that the left and right children of a node in a binary tree are lchild and rchild, and p points to a node in the binary tree. Please write a non-recursive function postfirst(p), the first postfirst traversal of the subtree corresponding to p node. Zhejiang University 1998 VI (10 points)]

```C
BiTNode* postfirst(BiTree T, BiTNode *p) {
if (p == NULL) {
return NULL;
}
BiTNode* cur = p;
while (cur) {
if (cur->lchild) {
cur = cur->lchild;
}
else if (cur->rchild) {
cur = cur->rchild;
}
else {
return cur;
}
}
return NULL;
}
```

33.The balance factor (bf) of a binary tree node is defined as the ratio of the height of the left subtree of that node to the height of the
The difference in height of the right subtree. Let the structure of the binary tree node be:(lchild,data,bf,rchild), the
lchild,rchild are the left and right son pointers; data is the data element; bf is the balancing factor, write recursive and non-recursive algorithms to compute the balance of each node in a binary tree.
Heng Factor [China University of Petroleum].

```C
int computeHeightAndBF(BiTree& root) {
if (root == NULL) {
return 0;
}
int leftHeight = computeHeightAndBF(root->lchild);
int rightHeight = computeHeightAndBF(root->rchild);
root->bf = leftHeight - rightHeight;
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
// determine whether a binary tree is a balanced binary tree based on the bf attribute
bool isBalanced2(BiTree root) {
if (root == NULL) {
return true;
}
if (root->bf > 1 || root->bf < -1) {
return false;
}
bool lchildInfo = isBalanced2(root->lchild);
if (lchildInfo == false) {
return false;
}
return isBalanced2(root->rchild);
}
```

```C
int getHeight2(BiTree root) {
if (root == NULL) {
return 0;
}
int leftHeight = getHeight2(root->lchild);
int rightHeight = getHeight2(root->rchild);
// return the greater height of the left and right subtrees plus the height of the current node (1)
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// Idea 2 Non-recursive
void computeBF(BiTree& root) {
Stack S;
initStack(S);
BiTNode* p = root;
BiTNode* last = NULL; //record the most recently accessed element (most recent out of the stack)
while (p || !isEmpty(S)) {
if (p) {
push(S, p);
p = p->lchild;
}
else {
BiTNode* top = peek(S);
// If the right subtree of the top stack node is empty or has already been visited.
if (top->rchild == NULL || top->rchild == last) {
last = pop(S);
int leftHeight = (top->lchild == NULL) ? 0 : getHeight2(top->lchild);
int rightHeight = (top->rchild == NULL) ? 0 : getHeight2(top->rchild);
top->bf = leftHeight - rightHeight;
}
else {
p = top->rchild;
}
}
}

}
```

34. Let T be a given search tree, try to write a program to delete a subtree with root node a in the tree, and release the storage space occupied by all the nodes of the subtree during the process of deletion, assuming that the storage space occupied by the nodes of the tree is obtained through dynamic storage allocation. The nodes in the tree T are assumed to be obtained by dynamic storage allocation, and their nodes are of the form: (lchild,data,rchild) [Fudan University 1999 VII (15 points)] .

```C
/*
34. Let T be a given search tree, try to write a program to delete a subtree with root node a in the tree, requesting to release the storage space occupied by all nodes of the subtree during the deletion process, assuming that the storage space occupied by the nodes in the tree T is obtained by dynamic storage allocation, and its nodes are of the form: (lchild,data,rchild) [Fudan University 1999 VII (15 points)
*/

void freeBiTNodes(BiTNode* node) {
if (node == NULL) {
return;
}
freeBiTNodes(node->lchild);
freeBiTNodes(node->rchild);
free(node);
}
void delteSubtree(BiTree& T, ElemType a) {
if (T == NULL) {
return;
}
if (T->data == a) {
freeBiTNodes(T);
T = NULL;
return;
}
if (T->data > a) {
delteSubtree(T->lchild, a);
}
else {
delteSubtree(T->rchild, a);
}
}
```

35. Write an algorithm that uses the null pointer field in the leaf nodes to link all the leaf nodes into a doubly linked table with a header node, and the algorithm returns the address of the header node (which must not be opened up to a new space, and is modified in the original tree). [Tohoku University 1999 IV (13 points)] .

```C
typedef int ElemType;
typedef struct BiTNode{
ElemType data;
BiTNode* lchild;
BiTNode* rchild;
bool ltag = true;
bool rtag = true;
}BiTNode,*BiTree;
BiTNode* dummyhead = NULL;
BiTNode* dummytail = NULL;
void initHead() {
dummyhead = (BiTNode*)malloc(sizeof(BiTNode));
dummyhead->lchild = NULL;
dummyhead->rchild = NULL;
dummytail = dummyhead;
}
void createLeafList(BiTree& T) {
if (T == NULL) {
return;
}
// Recursively process the left subtree
if (T->ltag) {
createLeafList(T->lchild);
}
// Handling leaf nodes
if (T->lchild == NULL && T->rchild == NULL) {
if (T->rchild != NULL) {
dummyhead->rchild->lchild = T;
}
T->rchild = dummyhead->rchild;
T->lchild = dummyhead;
dummyhead->rchild = T;
T->ltag = false;
T->rtag = false;
}
// Recursively process the right subtree
if (T->rtag) {
createLeafList(T->rchild);
}

}
void createLeafList2(BiTree& T) {
if (T == NULL) {
return;
}
createLeafList(T->rchild);
createLeafList(T->lchild);
// Handling leaf nodes
if (T->lchild == NULL && T->rchild == NULL) {
dummytail->rchild = T;
T->lchild = dummytail->rchild;
dummytail = T;
}
}
void createLeafList3(BiTree& T) {
if (T == NULL) {
return;
}

createLeafList(T->lchild);
// Handling leaf nodes
if (T->lchild == NULL && T->rchild == NULL) {
dummytail->rchild = T;
T->lchild = dummytail->rchild;
dummytail = T;
}
createLeafList(T->rchild);
}
//Print the results
void printCreateLeafList(BiTree T) {
initHead();
createLeafList(T);
BiTNode* p = dummyhead->rchild;
while (p) {
printf("%d->", p->data);
p = p->rchild;
}
printf("\n");
}

```

36. Add a row to a binary tree, given a binary tree with root root and two integers, val and depth, and a row of nodes with the value val at the given depth depth. Note that the root node, root, is at depth 1 .

![image-20240417000815993](C:\Users\asus\AppData\Roaming\Typora\typora-user-images\)

![image-20240417000830979](C:\Users\asus\AppData\Roaming\Typora\typora-user-images\)

```C
/*
36. Add a row to a binary tree Given a binary tree root root and two integers val and depth, add a row of nodes with the value val at the given depth depth. Note that the root node root is at depth 1
*/
void addOneRow(BiTree &T, int val, int depth) {
if (depth < 1) {
return;
}
// If you want to join at the first level, request a new root node to store the val value, so that the original root node becomes the left child of the new root node
if (depth == 1) {
BiTNode* head = (BiTNode*)malloc(sizeof(BiTNode));
head->data = val;
head->lchild = T;
head->rchild = NULL;
T = head;
return;
}
int cur = 1;
Queue Q;
initQueue(Q);
BiTNode* p = T;
enQueue(Q, p);
while (!isEmpty(Q)) {
int size = ;
for (int i = 0; i < size; i++) {
BiTNode* top = deQueue(Q);
if (cur == depth - 1) {
BiTNode* left = (BiTNode*)malloc(sizeof(BiTNode));
BiTNode* right = (BiTNode*)malloc(sizeof(BiTNode));
left->data = val;
right->data = val;
left->lchild = top->lchild;
left->rchild = NULL;
right->rchild = top->rchild;
right->lchild = NULL;
top->lchild = left;
top->rchild = right;
}
else {
if (top->lchild) {
enQueue(Q, top->lchild);
}
if (top->rchild) {
enQueue(Q, top->rchild);
}
}
}
cur++;
}
}
// Recursive thinking
int d, v;
void dfs(BiTree& T, int cur) {
if (T == NULL) {
return;
}
if (cur == d - 1) {
BiTNode* left = (BiTNode*)malloc(sizeof(BiTNode));
BiTNode* right = (BiTNode*)malloc(sizeof(BiTNode));
left->data = v;
right->data = v;
left->lchild = T->lchild;
left->rchild = NULL;
right->rchild = T->rchild;
right->lchild = NULL;
T->lchild = left;
T->rchild = right;
}
else {
dfs(T->lchild, cur + 1);
dfs(T->rchild, cur + 1);
}
}

void addOneRow2(BiTree& T, int val, int depth) {
d = depth;
v = val;
if (d == 1) {
BiTNode* head = (BiTNode*)malloc(sizeof(BiTNode));
head->data = v;
head->lchild = T;
head->rchild = NULL;
T = head;
return;
}
dfs(T, 1);
}

```

### 4.4 Rootlet Stacks

```C
#define InitSize 128
typedef int ElemType;
// Define the rootlet heap structure
typedef struct MinHeap {
int capacity; // Maximum capacity of the heap
int size; // number of current elements in the heap
ElemType elements[InitSize]; // array of elements in the heap, implemented as an array of pointers
} MinHeap;

// Create a rootlet stack
MinHeap* createMinHeap() {
MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));
heap->capacity = InitSize;
heap->size = 0;
return heap;
}

// Swap two nodes
void swap(ElemType arr[], int i, int j) {
ElemType temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

// Adjust the function downwards to preserve the rootlet heap property
void down(MinHeap* heap, int index) {
int smallest = index;
int left = 2 * index + 1;
int right = left + 1;

if (left < heap->size && heap->elements[left] < heap->elements[smallest])
smallest = left;
if (right < heap->size && heap->elements[right] < heap->elements[smallest])
smallest = right;

if (smallest != index) {
swap(heap->elements, smallest, index);
down(heap, smallest);
}
}

// Insert new node
void insertNode(MinHeap* heap, ElemType x) {
if (heap->size == heap->capacity) {
printf("Heap is full. \n").
return;
}
int i = heap->size;
heap->size++;
heap->elements[i] = x;

while (i != 0 && heap->elements[(i - 1) / 2] > heap->elements[i]) {
swap(heap->elements, i, (i - 1) / 2);
i = (i - 1) / 2;
}
}
// Determine if the rootlet pile is empty
bool isEmpty(MinHeap* heap) {
return heap->size == 0;
}
// pops the top element of the heap and maintains the remaining elements as a rootlet heap.
ElemType poll(MinHeap* heap) {
if (isEmpty(heap)) {
return NULL;
}
swap(heap->elements, 0, heap->size - 1);
heap->size--;
down(heap, 0);
return heap->elements[heap->size];
}

int main() {
MinHeap* heap = createMinHeap();
insertNode(heap, 10);
insertNode(heap, 7);
insertNode(heap, 8);
insertNode(heap, 5);
insertNode(heap, 6);
while (!isEmpty(heap)) {
ElemType x = poll(heap);
printf("%d ", x);
}
printf("\n");
return 0;
}
```

### 4.5 huffman tree

37. Given a set of terms and their weights, assuming that the terms are stored in the leaf nodes of a binary tree, the tree with the minimum weighted external path length is called a huffman tree. (1) Give an algorithm for constructing a huffman tree. (2) Given the terms and their corresponding weights in the following table, draw the huffman tree obtained after executing the above algorithm. (3) Find the WPL (weighted path length). (4) Write a program in c to construct the huffman tree. Zhejiang University 2000 VII (18 marks)]

![image-20240412012254573](C:\Users\asus\AppData\Roaming\Typora\typora-user-images\)

```C
#define InitSize 128
typedef struct TreeNode {
int id; //number
int weight; // weight
char value; //value
TreeNode* left;
TreeNode* right;
}TreeNode,*HuffmanTree ;

// Define the rootlet heap structure
typedef struct MinHeap {
int capacity; // Maximum capacity of the heap
int size; // number of current elements in the heap
TreeNode* elements[]; // array of elements in the heap, implemented as an array of pointers
} MinHeap;

// Create a rootlet stack
MinHeap* createMinHeap() {
MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap) + sizeof(TreeNode*) * InitSize);
heap->capacity = InitSize;
heap->size = 0;
return heap;
}

// Swap two nodes
void swap(TreeNode* arr[], int i, int j) {
TreeNode* temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

// Adjust the function downwards to preserve the rootlet heap property
void down(MinHeap* heap, int index) {
int smallest = index;
int left = 2 * index + 1;
int right = left + 1;

if (left < heap->size && heap->elements[left]->weight < heap->elements[smallest]->weight)
smallest = left;
if (right < heap->size && heap->elements[right]->weight < heap->elements[smallest]->weight)
smallest = right;

if (smallest != index) {
swap(heap->elements, smallest, index);
down(heap, smallest);
}
}

// Insert new node
void insertNode(MinHeap* heap, TreeNode* node) {
if (heap->size == heap->capacity) {
printf("Heap is full. \n").
return;
}
int i = heap->size;
heap->size++;
heap->elements[i] = node;

while (i != 0 && heap->elements[(i - 1) / 2]->weight > heap->elements[i]->weight) {
swap(heap->elements, i, (i - 1) / 2);
i = (i - 1) / 2;
}
}
// Determine if the rootlet pile is empty
bool isEmpty(MinHeap* heap) {
return heap->size == 0;
}
// pops the top element of the heap and maintains the remaining elements as a rootlet heap.
TreeNode* poll(MinHeap* heap) {
if (isEmpty(heap)) {
return NULL;
}
swap(heap->elements, 0, heap->size - 1);
heap->size--;
down(heap, 0);
return heap->elements[heap->size];
}

// Functions that create Huffman trees
HuffmanTree buildHuffmanTree(int weights[], char values[], int n) {
MinHeap* heap = createMinHeap();

// Create the initial leaf node and insert it into the rootlet pile
for (int i = 0; i < n; ++i) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->id = i + 1;
newNode->weight = weights[i];
newNode->value = values[i];
newNode->left = NULL;
newNode->right = NULL;
insertNode(heap, newNode);
}
for (int i = 0; i < heap->size; i++) {
printf("%d ", heap->elements[i]->weight);
}
printf("\n");

// Cycle through the Huffman tree
while (heap->size > 1) {
TreeNode* left = poll(heap);
TreeNode* right = poll(heap);

// Create new nodes as their parents
TreeNode* parent = (TreeNode*)malloc(sizeof(TreeNode));
parent->id = -1; // to distinguish non-leaf nodes
parent->weight = left->weight + right->weight;
parent->value = ' ';
parent->left = left;
parent->right = right;

// Insert a new node into the rootlet heap
insertNode(heap, parent);
}
// Pop the last node in the heap, which is the root of the Huffman tree.
TreeNode* root = poll(heap);
// Free heap memory
free(heap);
return root;
}

// Print the Huffman tree
void printTree(TreeNode* root) {
if (root == NULL) return;
printf("(%d, %d,%c)\n", root->id, root->weight, root->value);
printTree(root->left);
printTree(root->right);
}

// Recursively compute the WPL of a Huffman tree
int calculateWPL(TreeNode* root, int depth) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) {
return root->weight * depth;
}
return calculateWPL(root->left, depth + 1) + calculateWPL(root->right, depth + 1);
}

int main() {
int weights[] = { 15,6,7,12,25,4,6,1,15 };
char values[] = { 'A','B','C','D','E','F','G','H','I' };
HuffmanTree T = buildHuffmanTree(weights, values, 9);
int res = calculateWPL(T, 0);
printTree(T);
printf("WPL = %d\n", res);
return 0;
}
```

### 4.4 Precedence Clue Binary Trees

```C
typedef int ElemType;
typedef struct ThreadNode{
ElemType data; //data field
ThreadNode* lchild;
ThreadNode* rchild; // pointer to left and right children
int ltag, rtag; //preceding and succeeding clues
}ThreadNode,*ThreadBinaryTree;
//Initialize the binary tree
void initTree(ThreadBinaryTree& T) {
T = NULL;
}
//Creating a binary tree
void createTree(ThreadBinaryTree& T) {
ElemType x;
scanf("%d", &x);
if (x == 0) {
return;
}
else {
T = (ThreadNode*)malloc(sizeof(ThreadNode));
T->data = x;
T->lchild = NULL;
T->rchild = NULL;
T->ltag = 0;
T->rtag = 0;
createTree(T->lchild);
createTree(T->rchild);
}
}

//Prior-order traversal of ordinary binary trees
void printPreTree(ThreadBinaryTree T) {
if (T != NULL) {
printf("%d ", T->data);
printPreTree(T->lchild);
printPreTree(T->rchild);
}
}
//Prior-order traversal clues the binary tree
void preThread(ThreadBinaryTree& p, ThreadBinaryTree& pre){
if (p != NULL) {
if (p->lchild == NULL) {
p->lchild = pre;
p->ltag = 1;
}
if (pre != NULL && pre->rchild == NULL) {
pre->rchild = p;
pre->rtag = 1;
}
pre = p;
if (p->ltag == 0) {
preThread(p->lchild, pre);
}
if (p->rtag == 0) {
preThread(p->rchild, pre);
}
}
}
//Creating a Priority Search Binary Tree
void createPreThreadTree(ThreadBinaryTree& T) {
ThreadNode* pre = NULL;
if (T != NULL) {
preThread(T, pre);
pre->rchild = NULL;
pre->rtag = 1;
}
}

Priority traversal (recursion) of //clue binary trees
void printPreThreadTree(ThreadBinaryTree T) {
if (T != NULL) {
printf("%d ", T->data);
if (T->ltag == 0) {
printPreThreadTree(T->lchild);
}
else {
printPreThreadTree(T->rchild);
}
}
}
Precedence traversal (non-recursive) of //clue binary trees
void printPreThreadTree2(ThreadBinaryTree T) {
ThreadNode* p = T;
while (p != NULL) {
printf("%d ", p->data);
if (p->ltag == 0) {
p = p->lchild;
}
else {
p = p->rchild;
}
}
}

```

### 4.5 Middle-order clue binary trees

```C
//Middle-order traversal clues the binary tree
void inThread(ThreadBinaryTree& p, ThreadBinaryTree& pre) {
if (p != NULL) {
inThread(p->lchild, pre);
if (p->lchild == NULL) {
p->ltag = 1;
p->lchild = pre;
}
if (pre != NULL && pre->rchild == NULL) {
pre->rtag = 1;
pre->rchild = p;
}
pre = p;
inThread(p->rchild, pre);
}
}
//Creating a Priority Search Binary Tree
void createInThreadTree(ThreadBinaryTree& T) {
ThreadNode* pre = NULL;
if (T != NULL) {
inThread(T, pre);
pre->rtag = 1;
pre->rchild = NULL;
}
}

Precedence traversal (non-recursive) of //clue binary trees
void printPreThreadTree2(ThreadBinaryTree T) {
ThreadNode* first = T;
while (first->ltag == 0) {
first = first->lchild;
}
ThreadNode* p = first;
while (p != NULL) {
printf("%d ", p->data);
if (p->rtag == 0) {
p = p->rchild;
while (p->ltag == 0) {
p = p->lchild;
}
}
else {
p = p->rchild;
}
}
}
```

Topic 1: Write an algorithm to find the predecessor node of a specified node in a backward order in a medium order clue binary tree.

```C
ThreadNode* inpostPre(ThreadBinaryTree T, ThreadBinaryTree p) {
ThreadNode* q = NULL; // the final p to be found is in the backorder of the precursor node
//p node has a right child when
if (p->rtag == 0) {
q = p->rchild;
}
When //p node has no right child but has a left child
else if (p->ltag == 0) {
q = p->lchild;
}
//At the same time there is no left or right child
else {
while (p->ltag == 1 && p->lchild != NULL) {
p = p->lchild;
}
if (p->ltag == 0) {
q = p->lchild;
}
}
return q;
}
```