Data Structures Principles and Implementation of Sequential and Chained Binary Trees (10,000 words)

I. Tree concept and structure

Tree concepts

A tree is a nonlinear data structure that consists of n (n>=0) finite nodes that form a set with hierarchical relationships. It is called a tree because it looks like an upside-down tree, that is, it is rooted up and has leaves facing down.

• There is a special node, called the root node, which has no predecessor nodes

• Except for the root node, the remaining nodes are divided into M(M>0) mutually disjoint sets T1, T2, ......, Tm, where each set Ti(1<= i
  <= m) is again a subtree with a structure similar to that of a tree. Each subtree has one and only one predecessor at the root node and can have zero or more successors

Thus, the tree is recursively defined.

Note: In a tree structure, there can be no intersection between subtrees, otherwise it is not a tree structure

Concepts related to trees

• Degree of a node: the number of subtrees a node contains is called the degree of the node; e.g. above: A's is 6
• Leaf nodes or terminal nodes: nodes with degree 0 are called leaf nodes; e.g. above: B, C, H, I... etc. nodes are leaf nodes
• Non-terminal nodes or branch nodes: nodes whose degree is not 0; e.g. above: nodes D, E, F, G... etc. are branching nodes
• Biparent or parent node: if a node contains children, this node is called the parent of its children; e.g. above: A is the parent of B
• Child node or child node: the root node of the subtree contained in a node is called the child node of that node; e.g. above: B is the child node of A
• Sibling nodes: nodes with the same parent are called sibling nodes to each other; e.g. above: B, C are sibling nodes
• Tree degree: the degree of the largest node in a tree is called the degree of the tree; e.g. above: the degree of the tree is 6
• Hierarchy of nodes: defined from the root, the root is level 1, the children of the root are level 2, and so on;
• Height or depth of the tree: the maximum level of the nodes in the tree; e.g. above: the height of the tree is 4
• Cousin nodes: nodes with both parents in the same layer are cousins to each other; e.g. above: H and I are brothers to each other
• Ancestors of a node: all nodes on the branch from the root to the node; e.g. above: A is an ancestor of all nodes
• Children: Any node in a subtree rooted at a node is called a child of that node. As in the above figure: all nodes are children of A
• Forest: a collection of m (m>0) trees that do not intersect each other is called a forest;

representation of a tree

Tree structure relative to the linear table is more complex, to store the representation is more cumbersome, since the preservation of the value domain, but also to preserve the nodes and nodes between the
In practice, trees are represented in a variety of ways such as the two-parent representation, the child representation, the two-parent representation of the child, and the child-brother representation.
etc. A brief look at one of the most commonly used child-brother representations.

typedef int DataType; struct Node
struct Node
struct Node* _firstChild1; // first child node; {
    struct Node* _firstChild1; // first child node; struct Node* _pNextBrother; // pointing to its next brother node
    struct Node* _pNextBrother; // point to its next brother node
    DataType _data; // The data field in the node.
}; // The data field in the node.

Use of trees in practice (representing the directory tree structure of a file system)

II. Binary tree concepts and structure

conceptual

A binary tree is a finite set of nodes that.

1. or null
2. consists of a root node plus two binary trees called left and right subtrees.

As you can see from the picture above:

1. Binary trees do not have nodes of degree greater than 2
2. The subtrees of a binary tree are left and right, and the order cannot be reversed, so a binary tree is an ordered tree

For any binary tree is a composite of the following:

Special binary trees

1. Full Binary Tree: A binary tree is full if the number of nodes at each level is maximized. That is
   Say that a binary tree is full binary if its number of levels is K and the total number of nodes is , then it is a full binary tree.
2. Complete Binary Tree: Complete binary trees are very efficient data structures, complete binary trees are derived from full binary trees. For a depth of K
   of a binary tree with n nodes, if and only if each of its nodes is paired with a node numbered from 1 to n in a full binary tree of depth k
   It is called a full binary tree when it should be. It is important to note that a full binary tree is a special kind of complete binary tree.

Properties of binary trees

1. A non-empty binary tree has at most one node on the i-th level if the number of levels of the root node is specified to be one.

2. If the number of layers of the root node is specified to be 1, the maximum number of nodes of a binary tree of depth h is .

3. For any binary tree, if the number of leaf nodes of degree 0 is , and the number of branch nodes of degree 2 is , then we have = + 1

4. If the number of layers of the root node is specified to be 1, the depth of a full binary tree with n nodes, h= . (ps: is log in terms of 2
   is the base and n+1 is the logarithm)

5. For a complete binary tree with n nodes, if all nodes are numbered from 0 in top-to-bottom left-to-right array order, the numbering for the
   on the node with serial number i has:

   1. If i>0, biparent number of node at position i: (i-1)/2; i=0, i is the root node number, no biparent node

   2. If 2i+1<n, left child number: 2i+1, 2i+1>=n else no left child

   3. If 2i+2<n, right child number: 2i+2, 2i+2>=n else no right child

Storage structure of a binary tree

Binary trees can generally be stored using two structures, a sequential structure and a chained structure.

1. sequential storage
   Sequential structure storage is to use arrays for storage, generally using arrays is only suitable for representing complete binary trees, because not complete binary trees will have empty
   The heap is the only way to store arrays in real life. In reality, only the heap is used to store arrays, and we will talk about the heap in later chapters. Binary Trees
   The sequential storage is physically an array and logically a binary tree.

chain store
The chained storage structure of a binary tree means that a binary tree is represented by a chained table, i.e., a chain is used to indicate the logical relationships of the elements. The usual way to do this is to
Each node in a linked table consists of three domains, the data domain and the left and right pointer domains, the left and right pointers are used to give the information about the left and right children of the node, respectively.
The storage address of the chain node in the . Chain structure is subdivided into binary chain and trident chain, the current simple binary tree is generally binary chain, red-black tree and so on will use trident chain.

typedef int BTDataType;
// binary chain
struct BinaryTreeNode
struct BinaryTreeNode
struct BinTreeNode* _pLeft; // point to the left child of the current node
    struct BinTreeNode* _pRight; // points to the right child of the current node
    BTDataType _data; // current node value field
}

// Trinomial chain
struct BinaryTreeNode
{
    struct BinTreeNode* _pParent; // points to the parent of the current node
    struct BinTreeNode* _pLeft; // points to the left child of the current node
    struct BinTreeNode* _pRight; // points to the right child of the current node
    BTDataType _data; // The current node value field.

III. Sequential structure and realization of binary trees (heap)

Sequential structure of binary trees

Ordinary binary trees are not suitable for storing in arrays because there can be a lot of wasted space. Instead, full binary trees are more suitable for using sequential knots
The heap is stored in a structured manner. In reality, we usually store the heap (a kind of binary tree) as an array using a sequential structure, and it is important to note that the heap and the operating system here
The heap in the address space of a virtual process is two things, a data structure and an area segment of the operating system that manages memory.

Concept and structure of a heap

If there is a set K = { , , , ..., } of keycodes, store all its elements in the sequential storage of a complete binary tree
in a one-dimensional array and satisfying: <= and <= ( >= and >= ) i = 0, 1, and
2..., then it is called a small (or large) heap. The heap with the largest root node is called the largest heap or big root heap, and the heap with the smallest root node is called the smallest heap or little root heap.
The nature of the heap:

• The value of a node in the heap is always no greater or no less than the value of its parent;
• A heap is always a fully binary tree.

Heap Implementation

heap down adjustment algorithm

Given an array, logically viewed as a fully binary tree. We can adjust it by a downward adjustment algorithm starting at the root node
into a small heap. The downward adjustment algorithm has one prerequisite: the left and right subtrees must be a heap in order to be adjusted.

int array[] = {27,15,19,18,28,34,65,49,25,37};

Heap Creation

Given an array that can logically be viewed as a fully binary tree, but is not yet a heap, we now calculate the number of heaps by counting
method to build it into a heap. The root node's left and right subtrees are not a heap, so how do we adjust for that? Here we start with the first non-leaf node of the countdown of the
The subtrees are adjusted to the heap by starting with the subtree and adjusting all the way to the root node of the tree.

int a[] = {1,5,3,8,7,6}; 

heap building time complexity

Since a heap is a complete binary tree and a full binary tree is also a complete binary tree, the full binary tree is used here for simplicity in the proof (the time complexity would have been looked at
is an approximation, a few more nodes do not affect the final result):

Hence: the time complexity of building a heap is O(N).

Heap insertion

Start by inserting a 10 onto the tail of the array and then proceed to adjust the algorithm upwards until the heap is satisfied.

Heap Deletion

Deleting the heap is deleting the data at the top of the heap, swapping the data at the top of the heap root the last data one for one, and then deleting the last data of the array, and then proceeding downwards
Integrate the algorithm.

Code implementation of the heap

#define _CRT_SECURE_NO_WARNINGS 1


#pragma once

#include<>
#include<>
#include<>
#include<>
#include<>


typedef int HeapDataType;

typedef struct Heap
{
	HeapDataType *a;
	int size;
	int capacity;
	//sequential tableau idea
}Heap;

void HeapPrint(Heap *ps);

void HeapInit(Heap *ps);

void HeapDestroy(Heap *ps);

void HeapPush(Heap *ps,HeapDataType x);

void HeapPop(Heap*ps);

int HeapSize(Heap *ps);

bool HeapEmpty(Heap *ps);

//Accepts a heap，arrays， arrays大小。Build a heap
void HeapCreate(Heap*ps, HeapDataType *a, int size);

void HeapSort(HeapDataType *a, int size);

void AdjustDown(HeapDataType *a, int size, int parent);

void AdjustUp(HeapDataType *a, int child);

void Swap(HeapDataType *p1, HeapDataType *p2);

#include""

void Swap(HeapDataType *p1, HeapDataType *p2)
{
HeapDataType tmp = 0;
tmp = *p1;
*p1 = *p2.
*p2 = tmp.
}

// AdjustUp algorithm: build heap from 0 insertion and insertion in the context of heap // not suitable for direct heap building (build the array from 1 downwards)
void AdjustUp(HeapDataType *a,int child)
{
assert(a);
// small heap changed to a[child] < a[parent]
int parent = (child - 1) / 2;
while (parent >= 0 && child > 0 && a[child] > a[parent]) //throw in the bounds and conditions all over the place
{ //this is fine, there are no two identical if's repeated. you can put the conditions together in the while
Swap(&a[child], &a[parent]);
child = parent.
parent = (child - 1) / 2;
}
}

// AdjustDown algorithm: prerequisite: left and right subtrees are heaps // Suitable for building heaps: recursively start with the smallest father (although it is possible to start with the smallest child)
void AdjustDown(HeapDataType *a, int size, int parent) // small heap
{
//// compare the largest/smallest of the two children for exchange
//int child = parent * 2 + 1;
//if (child < size && parent < size && a[child] < a[child + 1]) //// ------------ This logic is wrong, one outside the while, one inside the while, repeat, when size == child snaps out of one
//{ // If it occurs, make sure to eliminate it, split out the while and if conditions
// child = child + 1;
//}
//// Adjust to the end of the leaf //&& Judge the left side first
//while (child < size && parent < size && a[parent] < a[child]) //child may be out of bounds, make sure child<size first
//{
// Swap(&a[parent], &a[child]);
// parent = child; // child = parent * 2 + 1
// child = parent * 2 + 1; // if (child <)
// if (child < size && parent < size && a[child] < a[child + 1])// ----------------------------------------------------- ------------------
// {
// child = child + 1; }
// }
//}


int child = parent * 2 + 1; while (child < size)
while (child < size)
{
if (child + 1 < size &&a[child] > a[child + 1])
{
a[child] > a[child + 1]) { child++;
}
if (a[child] < a[parent]) // swap if smallest heap is larger than smallest child.
{ // Swap if the big pile is smaller than the biggest child
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
parent = child; child = parent * 2 + 1; }
{
break; } else {
}
}
}

//-------------------------------------------------------------------------

void HeapPrint(Heap *ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
}

void HeapInit(Heap *ps)
{
assert(ps);
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
}


// Accept a heap, an array, an array size
void HeapCreate(Heap *ps, HeapDataType *a, int size)
{
assert(ps);
// Open the array space in the heap
ps->a = (HeapDataType *)malloc(size * sizeof(HeapDataType));
if (ps->a == NULL)
{
perror("malloc fail"); exit(1); {
exit(1);
}
memcpy(ps->a, a, size *sizeof(HeapDataType)); //copy the array over
ps->size = size;
ps->capacity = 2 * size; //build the heap.
//build the heap
// start from the smallest father and work down
//loop until parent/child is not 0
int parent = (size - 1 - 1) / 2;
while (parent >= 0)
{
AdjustDown(ps->a, ps->size, parent);
parent--;
}
}

void HeapDestroy(Heap *ps)
{
assert(ps);
free(ps->a);
ps->capacity = ps->size = 0;
}

void HeapPush(Heap *ps,HeapDataType x)
{
assert(ps);
if (ps->size == ps->capacity)//open/expand
{
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
HeapDataType *tmp = (HeapDataType *)realloc(ps->a, newCapacity * sizeof(HeapDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(-1);
}
ps->a = tmp;
ps->capacity = newCapacity;
}
ps->a[ps->size] = x;
ps->size++;
AdjustUp(ps->a, ps->size - 1);
}

void HeapPop(Heap *ps)
{
assert(ps); } void HeapPop(Heap *ps) {
assert(ps->size > 0); // Ensure that data exists in the heap
Swap(&ps->a[ps->size-1], &ps->a[0]);
ps->size--;.
AdjustDown(ps->a,ps->size, 0);
}


// Pick the number quite fast, just logN times
HeapDataType HeapTop(Heap *ps)
{
assert(ps);
assert(ps->size > 0);
return ps->a[0];
}

int HeapSize(Heap *ps)
{
assert(ps);
return ps->size;
}

bool HeapEmpty(Heap *ps)
{
assert(ps); } bool HeapEmpty(Heap *ps) {
return ps->size == 0;
}

Heap applications

heap sort

Heap sorting i.e. sorting using the idea of heap is divided into two steps in total:

1. build up a pile
   Ascending order: building big piles
   Descending order: building small reactors
2. Sorting using the heap deletion idea

Downward adjustment is used in both heap building and heap deletion, so mastering downward adjustment will allow you to complete heap sorting.

Heap Sort Code Implementation

#include""


void HeapSort(HeapDataType *a, int size)
{
assert(a);
// ---- Adjust the algorithm downwards to build the heap ----
// time complexity O(n)
int parent = (size - 1 - 1) / 2;
while (parent >= 0)
{
AdjustDown(a, size, parent);
parent--;
}
// ---- pick number ----
// Time complexity O(n*logN), it seems to say that n numbers have to be highly subadjusted

//int end = size - 1;//
while (size>0)
{
Swap(&a[0], &a[size-1]);// select the number, after selecting the less one
size--;
AdjustDown(a, size, 0);//
}

}

Time Complexity Analysis

/*
Downward Adjustment Algorithm Heap Building Time Complexity Calculation
Assume that the height of the full binary tree tree h
The number of nodes at each level is
First level 2 ^ 0 ------ downward adjustment h-1 times
Second level 2 ^ 1 ------ downward adjustment h-2 times
Third level 2 ^ 2 ------ adjusted downward h-3 times
...    ...
Layer h - 1 2 ^ (h - 2) ------ adjusted down 1 time
Layer h 2 ^ (h - 1)

The downward adjustment algorithm builds the heap starting with the smallest father, i.e. the last node in layer h - 1 parent = (size-1-1)/2
The worst case number of executions required for all nodes is
f(h) = 2^(h-2)*1 + 2^(h-3)*2 + ... + 2^1*(h-2) + 2^0*(h-1) Displaced subtraction
2*f(h) = 2^(h-1)*1 + 2^(h-2)*2 + ... + 2^2*(h-2) + 2^1*(h-1)
Differentiate and combine to get f(h) = 2^h -h-1
where the number of full binary tree nodes N = 2^h-1, i.e., h = log(N+1) Substitute to get
f(N) = N - 1 - log(N+1), and logN (order of magnitude) is discarded.
So O(n) = n

-------------------------------------------------------------------------------
And the upward adjustment algorithm to build the heap time complexity is more loss, see the figure
Assume that the height of the full binary tree h
The number of nodes at each level is
First level 2 ^ 0
Second level 2 ^ 1 ------ adjust upward 1 time
Third level 2 ^ 2 ------ adjusted upward 2 times
...    ...
Layer h - 1 2 ^ (h - 2) ------ adjusted h-2 times upwards
Layer h 2 ^ (h - 1) ------ adjusted h-1 times upwards
The calculation is still a staggered subtraction, and it is clear from the figure that the number of times the upward adjustment algorithm is performed is significantly higher by an order of magnitude.
No more calculations
O(n) = n*logN



To summarize: the downward adjustment algorithm skips the lowest most node layer and executes fewer times with more nodes starting from the lower layer. Fast.
The upward adjustment algorithm starts from the top and increases the number of executions exponentially from fewer nodes to more nodes, and the previous ones don't add up to the last layer.
*/Slow


// Build a heap - select numbers, put them at the end, exclude them, re-select them

// aggregate time complexity O(n + n*logN) = O(n*logN)

TOP-K issues

TOP-K problem: that is, to find the first K largest elements or smallest elements in the data combination, generally the amount of data is relatively large.
For example: top 10 majors, top 500 in the world, rich list, top 100 active players in the game, etc.
For the Top-K problem, the simplest and most straightforward way to think of is to sort, but: if the amount of data is very large, sorting is less desirable (perhaps
None of the data can be loaded into memory all at once). The best way to solve this is with a heap, the basic idea is as follows:

1. Building a heap with the first K elements of a data set
   The first k largest elements, then build a small heap
   The first k smallest elements, then build a large heap
2. Compare the remaining N-K elements with the top element of the heap in order, and replace the top element if it is not satisfied.

After comparing the remaining N-K elements to the top element of the heap in turn, the remaining K elements in the heap are the first K smallest or largest elements sought.

code example

#define _CRT_SECURE_NO_WARNINGS 1
#include""
#include<>

//Take the first K largest numbers
#define K 10

void TopK()
{

int n = 10000;//int n = 10000;//amount of data
int randMax = 10000;//int randMax = 10000;
int minHeap[K] ;
//int K = 100;

memset(minHeap, 0, sizeof(minHeap));//initialize the array, and use sizeof(arr) - no need to take an address!
srand((size_t)time(0));//don't need to add size_t is fine, NULL will actually be time will be forced to convert to (void) 0

//TopK problem idea s
//build a heap of size K

FILE *fin = fopen("", "w");
if (fin == NULL)
{
perror("fopen fail");
return;
}

// Write data randomly, rand , using fprintf("fout","%d ",)

int randK = K; //int randK = K.
for (int i = 0; i < n ;i++)
{
int val = rand() % randMax; // the maximum value does not exceed randMax
if (val % 3 == 0 && randK-- > 0)
{
val = randMax + randK; //insert custom maximum value
}
fprintf(fin, "%d ", val);
}
//If the inserted maximum is not enough for K, add -------- at the end, the probability of it appearing is small, ignore it
while (randK-- > 0)
{
fprintf(fin, "%d ", randMax+randK); // note the delimiter, separate to the human, use space or \n convenient to identify with fscanf default delimiter
}
fprintf(fin, "%d ", 99999); //--- Verify that it can be inserted and that it is inserted at the end

fclose(fin);


//for (int i = 0 ; i < K; i++)
//{
// AdjustDown(minHeap, K, 0); }
//}

FILE *fout = fopen("", "r");// reset file pointer
if (fout == NULL)
{
perror("fopen fail");
return;
}



int tmp; while (fscanf(fout, "%d", &tmp) !
while (fscanf(fout, "%d", &tmp) ! = EOF) //Note that since scanf's default separator space or \n is set, feel free not to follow the format %d with a separator to recognize it.
{
//Extract data from the file
//To mention one and compare it with the top of the heap once.
//With the file pointer to go on will be compared to all the data in the file
//ASCII file use fscanf("stream", "format", "dest"); if (tmp >tmp >tmp >tmp >tmp)
if (tmp >minHeap[0])
{
minHeap[0] = tmp;
}
AdjustDown(minHeap, K, 0); // change the heap once to adjust it once
}
fclose(fout);

for (int i = 0; i < K; i++)//print the array
{
printf("%d ", minHeap[i]);
}
}

IV. Code implementation of binary tree chaining structure

Traversal of a binary tree

Pre-, mid-, and post-order traversals
The easiest way to learn the structure of a binary tree is to traverse it. The so-called binary tree traversal (Traversal) is according to a particular rule, in order to binary tree
The nodes in the tree are operated accordingly and each node is operated only once. The operations performed by accessing nodes depend on the specific application problem. Iteration
is one of the most important operations on a binary tree and the basis for all other operations on a binary tree.

As a rule, binary trees are traversed with: a recursive structure traversal of preorder/middle order/postorder:

1. Preorder Traversal - The operation of accessing the root node occurs before traversing its left and right subtrees.
2. Inorder Traversal - The operation of accessing the root node occurs within (between) traversing its left and right subtrees.
3. Postorder Traversal - The operation of accessing the root node occurs after traversing its left and right subtrees.

Since the node being accessed must be the root of some subtree, N(Node), L(Left subtree) and R(Right subtree) can again be interpreted as
root, the left subtree of the root, and the right subtree of the root.NLR, LNR, and LRN are also known as root-first traversal, root-middle traversal, and root-second traversal, respectively.

hierarchical traversal

Hierarchical traversal: In addition to prior traversal, intermediate traversal, and posterior traversal, you can also perform hierarchical traversal of a binary tree. Let the root node of a binary tree be
The number of levels is 1. A level-order traversal starts from the root node of the binary tree in which it is located, first visiting the root node of the tree in the first level, and then visiting the 2nd level from left to right
The process of accessing the nodes of the tree layer by layer from top to bottom, left to right, and so on, is hierarchical traversal.

code implementation

#define _CRT_SECURE_NO_WARNINGS 1

#pragma once

#include<>
#include<>
#include<> #include<>

//Tree traversal

// Depending on the recursive traversal method, access the data and the left and right children of each tree (structure).

// Each time you recursively reach a new tree (each node is a tree), you have to first determine if the tree is empty ---- to prevent wild pointer errors


//---- create binary tree ----

typedef int BTDataType.

typedef struct BinaryTreeNode
BTDataType data; typedef struct BinaryTreeNode; {
BTDataType data; struct BinaryTreeNode *left; //left sub-tree
struct BinaryTreeNode *left; //left sub tree
struct BinaryTreeNode *right; //right sub tree
struct BinaryTreeNode *right; //right sub tree; }BTNode.


}BTNode; /* struct BinaryTreeNode *left; //left sub tree
node->data = x.
node->left = NULL;
node->right = NULL.
*/
BTNode* BuyBTNode(BTDataType x); // construct node with value x


/*
printf("%d", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
*/
void PrevOrder(BTNode *root);// root traversal first


/*
PrevOrder(root->left);s
printf("%d", root->data);
PrevOrder(root->right).
*/
void InOrder(BTNode *root); // middle root traversal


/*
PrevOrder(root->left);
PrevOrder(root->right).
printf("%d", root->data);
*/
void PostOrder(BTNode *root); // post root traversal

void LevelOrder(BTNode *root); // level order traversal


//LevelOrder(BTNode *root); //LevelOrder
return BTSize(root->left) + BTSize(root->right) + 1;
*/
int BTSize(BTNode* root); // find the number of nodes in the binary tree.


/**/
int BTLeafSize(BTNode* root); // find the number of leaf nodes of the binary tree


int BTHeight(BTNode *root); //find the height of the binary tree

int BTLevelKSize(BTNode *root, int k); //calculate the kth level node of the binary tree

BTNode *BTFind(BTNode* root, BTDataType x); //binary tree find the address of a node

void BTDestroy(BTNode*root); //binary tree destruction

BTNode * rebuildBinaryTree(BTDataType* str, int *pi); //Build a binary tree, pi is the subscript address of the array.


bool isBTComplete(BTNode *root); //Construct a binary tree, pi is the subscript address of the array.

Building Binary Trees with Basic Functions

#include""


/* Create a binary tree node with value x */
BTNode* BuyBTNode(BTDataType x) //create a node with value x
{

BTNode *node = (BTNode*)malloc(sizeof(BTNode));//use pointer to point to actual space
if (!node)
{
perror("malloc fail!");;
exit(1);
}
node->data = x;
node->left = NULL;
node->right = NULL; } node->data = x
return node; }
}

/* PrevOrder traversal */
void PrevOrder(BTNode *root) //previous order order NLR: Preorder Traversal also known as.
NLR: Preorder Traversal, also known as {
if (!root )
{
printf("NULL ");
return; }
}

printf("%d ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);

}


/* Middle-order traversal */
void InOrder(BTNode *root) // ... In
{

if (!root )
{
printf("NULL ");
return;
}

InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}



/* Subsequent traversal */
void PostOrder(BTNode *root) // post- prefix ... after ... post- ... after
{
if (!root )
{
printf("NULL ");
return;
}

PostOrder(root->left);
PostOrder(root->right); }
printf("%d ", root->data);

}


/* Find the number of all nodes in a binary tree */
int BTSize(BTNode* root)
{
/*
if (root == NULL)
{
return 0;
}

// Idea: sum the number of nodes in the left subtree and the right subtree and itself.
return BTSize(root->left) + BTSize(root->right) + 1;
*/

// The two duplicate syntaxes can be merged
return !root ? 0 : BTSize(root->left) + BTSize(root->right) + 1;

}



/* Find the number of leaf nodes of a binary tree */
int BTLeafSize(BTNode* root)
{
if (!root)
{
return 0; }
}
// Idea: a null left and right node is a leaf
if (!root->left && !root->right)
{
return 1; }
}

return BTLeafSize(root->left) + BTLeafSize(root->right);

}



/* Find the height of a binary tree */
int BTHeight(BTNode *root)
{
if (!root)
{
return 0; }
}



// Idea: compare the heights of the left and right subtrees, not the smaller ones Only the relational operator can do this: compare the two sides and choose one and discard the other.

//Method one:
//return BTHeight(root->left) > BTHeight(root->right)
// ? BTHeight(root->left) + 1
// : BTHeight(root->right) + 1;
/*
Point of view; big problem, after the recursion the stack frame is destroyed and the data is no longer saved, the
Each recursion calculates the subtree height twice, and each subtree height calculation is exponential */


// Optimization: method two:

int leftHeight = BTHeight(root->left);
int rightHeight = BTHeight(root->right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
/* Comment:Avoid double counting by noting the current stack frame data */
}



/* Find the number of nodes at the kth level of a binary tree */
int BTLevelKSize(BTNode *root , int k)
{
/* What to do if it encounters the kth level or null */
if (!root)
{
return 0; }
}

if (k == 1) // last layer, kth layer
{
return 1; }
}

/* What to do if you don't get to the kth level */
return BTLevelKSize(root->left,k-1) + BTLevelKSize(root->right,k-1) ; //not the kth level, keep going deeper to find the kth level
//why k-1, because the pass is k
}



/* Binary tree find */
BTNode *BTFind(BTNode* root, BTDataType x)
{
if (!root )
{
return NULL.
}

if (root->data == x)
return NULL; } if (root->data == x) {
return root; }
}

BTNode*left = BTFind(root->left ,x);
if (left)
{
return left; }
}

BTNode*right = BTFind(root->right,x);
if (right)
{
return right; }
}

// It can be written in the following form to look nice
/*
if (right)
return right;)*/
return NULL; //root ! = NULL, value not x, left and right subtrees not found, return null!
}


/* Build a binary tree */
BTNode *rebuildBinaryTree(BTDataType* str, int *pi) // pi is the address of the subscript of the array.
{
if (str[*pi] == '#')
{
(*pi)++;
return NULL.
}
BTNode*root = (BTNode*)malloc(sizeof(BTNode));
root->data = str[(*pi)++];
root->left = rebuildBinaryTree(str, pi);
root->right = rebuildBinaryTree(str, pi);

return root.

}



/* binary tree destruction */
void BTDestroy(BTNode*root) /* first class pointer pass, need to null root outside function after call */
{
if (!root)
{
return; }
}
BTDestroy(root->left);
BTDestroy(root->right); free(root); }
BTDestroy(root->right); free(root).
root->left = root->right = NULL; }
}


/*
Iteration naming

N(Node), L(Left subtree) and R(Right subtree)

Named according to the location of the node access operation:
NLR: Preorder Traversal (also known as (Pre-order Traversal))
--NLR: Preorder Traversal (also known as (prior order traversal)) - the operation of accessing the root node occurs before traversing its left and right subtrees.
② LNR: Middle Order Traversal (Inorder Traversal)
--The operation of accessing the root node occurs in (between) traversing its left and right subtrees.
LRN: Postorder Traversal (Postorder Traversal)
--Operations that access the root node occur after traversing its left and right subtrees.

The first three orders are symmetric with the last three

*/

hierarchical traversal

#define _CRT_SECURE_NO_WARNINGS 1
#include""
#include""


void LevelOrder(BTNode *root)
{
	//Implemented through a queue
	Queue queue;//no pointer==give space ， pointers==Pointer space only，No space for members
	QueueInit(&queue);
	if (root)
		QueuePush(&queue, root);

	//Iteration via Queue Cache Subtree Scrolling Data
	while (!QueueEmpty(&queue))
	{
		BTNode* front = QueueFront(&queue);//take sth. out of the queue
		printf("%d ", front->data);
		QueuePop(&queue);
		if (front->left)
		{
			QueuePush(&queue, front->left);
		}
		if (front->right)
		{
			QueuePush(&queue, front->right);
		}
	}
	QueueDestroy(&queue);

}


void LevelOrder2(BTNode *root)
{
	if (!root)
	{
		return;
	}
	Queue queue;
	QueueInit(&queue);
	int levelSize = 0;

	QueuePush(&queue, root);
	levelSize = 1;
	while (!QueueEmpty(&queue))
	{
		while (levelSize--)
		{
			BTNode* front = QueueFront(&queue);
			printf("%d ", front->data);
			QueuePop(&queue);
			if (front->left)
				QueuePush(&queue, front->left);
			if (front->right)
				QueuePush(&queue, front->right);
		}
			printf("\n");
			levelSize = QueueSize(&queue);

	}

	QueueDestroy(&queue);
}

Number of nodes

#define _CRT_SECURE_NO_WARNINGS 1
#include""

int TreeSize(struct BinaryTreeNode *root)
{
	return !root ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

void _preorderTraversal(struct BinaryTreeNode *root, int *str, int* pi)
{
	if (!root)
	{
		return ;
	}
	str[(*pi)++] = root->data;
	_preorderTraversal(root->left, str, pi);
	_preorderTraversal(root->right, str, pi);
}

int* preorderTraversal(struct BinaryTreeNode* root, int* returnSize){

	*returnSize = TreeSize(root);
	int *a = (int*)malloc(*returnSize * sizeof(int));
	int i = 0;
	_preorderTraversal(root, a, &i);
	return a;
}

Determining whether a tree is a complete binary

#include""
#include""

bool isBTComplete(BTNode *root)
{
	if (!root)
	{
		return false;
	}
	Queue queue;
	QueueInit(&queue);
	QueuePush(&queue, root);

	while (!QueueEmpty(&queue))
	{
		BTNode* front = QueueFront(&queue);
		QueuePop(&queue);
		if (!front) //There must exist a next level node，So jump right out.，No need to insert all nodes
		{
			QueuePop(&queue);
			break;
		}
		QueuePush(&queue, front->left);
		QueuePush(&queue, front->right);
	}

	while (!QueueEmpty(&queue))
	{
		if (QueueFront(&queue))
		{
			QueueDestroy(&queue);
			return false;
		}
		QueuePop(&queue);
	}
	QueueDestroy(&queue);
	return true;
}

Determine if a subtree

#include<>
struct TreeNode
{
	int val;
	struct TreeNode* left; //left sub tree
	struct TreeNode* right; //right sub tree
};

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
	if (subRoot == NULL)
	{
		return true;
	}

	if (root == NULL)
	{
		return false;
	}

	if (root->val == subRoot->val) //If equal，and are identical subtrees，Return to true
	{
		if (isSameTree(root, subRoot))
		{
			return true;
		}
	}

	return isSubtree(root->left, subRoot)
		|| isSubtree(root->right, subRoot);
}

Determine if two trees are the same same

#include<>
struct TreeNode
struct TreeNode; {
struct TreeNode* left; //left sub-tree
struct TreeNode* left; //left sub tree
struct TreeNode* right; //right sub tree
struct TreeNode* left; //left sub tree; //right sub tree}

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
if (p == NULL && q == NULL)
return 1; {
return 1; }
}
else if (p == NULL && p ! = q || q == NULL && p ! = q)
{ /* Note the order of logical operations, the whole if-else is to determine that there is more than 1 NULL as a prerequisite, the operator requires that the first empty */
// can be optimized to p == NULL && q == NULL, because there is already a premise.
return 0;
}

if (p->val ! = q->val)
return 0; } if (p->val !
return 0; }
}
return isSameTree(p->left, q->left)
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

Are the two trees symmetric

#include ""


bool _isSymmetric(BTNode *root1, BTNode *root2)
{
	if (!root1 &&!root2)
	{
		return true;
	}
	if (!root1 || !root2)
	{
		return false;

	}

	if (root1->data != root2->data)
	{
		return false;
	}

	return _isSymmetric(root1->left, root2->right) && _isSymmetric(root1->right, root2->left);
}


bool isSymmetric(BTNode *root)
{
	return !root || _isSymmetric(root->left, root->right);

}

single-valued binary tree (math.)

If every node of a binary tree has the same value, then the binary tree issingle-valued (math.)binary tree

#include<>
struct TreeNode
{
	int val;
	struct TreeNode* left;  //left sub tree
	struct TreeNode* right; //right sub tree
};

bool isUnivalTree(struct TreeNode* root){

	if (root == NULL)
	{
		return true;
	}

	if (root->left && root->left->val != root->val)
	{
		return false;
	}

	if (root->right && root->right->val != root->val)
	{
		return false;
	}

	return isUnivalTree(root->left) && isUnivalTree(root->right);
}

Queues used

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<>
#include<>
#include<> #include<>
#include<> #include<> #include<>
//#include""

struct BinaryTreeNode; //Type declaration : Types can be declared, as long as the variable name --- principle, search the entire source code


typedef struct BinaryTreeNode* QDataType.

typedef struct QueueNode
{
struct QueueNode *next; struct BinaryTreeNode* QDataType; typedef
QDataType data.
}QNode.

// Control variable structure
// If there is only one value, you don't need to define a structure, if there is more than one, you define a structure question.

typedef struct Queue
{
struct QueueNode *head; //head of the queue, out of the queue, head deletion
struct QueueNode *tail; //tail, in, out, tail insertion
}Queue.
// Pass second-level pointer if it's a pointer variable, first-level if it's a normal variable.

void QueueInit(Queue *pq).
void QueueDestroy(Queue *pq).

void QueuePush(Queue *pq, QDataType x); void QueuePop(Queue *pq, QDataType x).
void QueuePop(Queue *pq); void QueueDestroy(Queue *pq).

QDataType QueueFront(Queue *pq); void QueuePop(Queue *pq); void QueuePop(Queue *pq)
QDataType QueueBack(Queue *pq); void QueuePop(Queue *pq).

int QueueSize(Queue *pq); int QueueSize(Queue *pq); bool QueueEmpty(Queue *pq)
bool QueueEmpty(Queue *pq);

#include ""


void QueueInit(Queue *pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;


}

void QueueDestroy(Queue* pq)
{
assert(pq);
QNode * next = NULL;
QNode * cur = pq->head;
while (cur)
{
next = cur->next; free(cur); { next = pq->head; while (cur) {
free(cur);
next; free(cur); cur = next.
}
pq->head = pq->tail = NULL;
}

void QueuePush(Queue *pq,QDataType x)
{
assert(pq);
QNode *newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail ");
exit(-1);
}
// Initialize before using
newnode->data = x;
newnode->next = NULL;
// Single linked table queue-tail-plug delete.
if (pq->tail == NULL) // head and tail are fine, just judge one
{
pq->head = pq->tail = newnode;
}
else // tail insertion
{
pq->tail->next = newnode; //node pointed to by the tail of the queue is linked to the new node
pq->tail = newnode; //tail of queue points to new node
}
}

void QueuePop(Queue *pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->head->next == NULL)// there is only one node
{
free(pq->head); //free first
pq->tail = pq->head = NULL; //next empty
}
else
{
QNode *next = pq->head->next;//remember next
free(pq->head);//free head node
pq->head = next;//next node becomes new node
}
}

QDataType QueueFront(Queue *pq)
{
assert(pq);
assert(!QueueEmpty(pq));;
return pq->head->data;
}


QDataType QueueBack(Queue *pq)
{
assert(pq);
assert(!QueueEmpty(pq));;
return pq->tail->data;
}

int QueueSize(Queue *pq)
{
assert(pq);
QNode *cur = pq->head;
int size = 0; while (cur); QNode *cur = pq->head
while (cur)
{
cur = cur->next; int size = 0; while (cur) { size++;
cur = cur->next;
cur = cur->next; }
cur = cur->next; }
}

bool QueueEmpty(Queue *pq)
{
assert(pq); //return QueueSize(pq) == 0; }
//return QueueSize(pq) == 0;
return pq->head == NULL ;//as long as there is one
//head is nulltail is also null
}