当前位置：网站首页>Basic operation of binary tree (C language version)
Basic operation of binary tree (C language version)
2022-07-03 02:24:00 【Can't write code full】
1 The definition of binary tree
The graph of a binary tree looks like this ：
A binary tree is a tree structure in which each node has at most two subtrees , It is often used to implement binary lookup tree and binary heap . Binary tree is a chain storage structure , Using a binary chain , It's essentially a linked list . Binary trees are usually defined in the form of structures , as follows , The structure consists of three parts ： The value stored in this node 、 Pointer to the left child node 、 Pointer to the right child node .
struct TreeNode {// The node of the tree
int data;// Data fields
struct TreeNode* lchild;// Point to the left child node
struct TreeNode* rchild;// Point to the right child node
};Of course , We can also redefine the name of our tree node structure , Use C In language typedef The method is ok .
struct TreeNode {// The node of the tree
int data;// Data fields
struct TreeNode* lchild;// Point to the left child node
struct TreeNode* rchild;// Point to the right child node
} BiNode, *BiTree;2 The establishment of binary tree
The operation of binary tree usually uses recursive method , Binary tree operations can be divided into two categories , One is to change the structure of binary tree , For example, the creation of binary tree 、 Node deletion, etc , This kind of operation , The node parameter of the binary tree passed in is the address of the binary tree pointer , This kind of participation is introduced into , It is convenient to change the pointer of binary tree structure （ The address ）.
The following is the function created by binary number , Here we stipulate that , Node value must be greater than 0 The numerical , If not greater than 0 Number of numbers , It means that the operation of continuing to create child nodes is over . Then we use recursive method to create left subtree and right subtree .
for instance , Build this binary tree ：
5 / \ 3 8 / / \ 2 6 9
First, according to this binary tree , Let's simulate ：
Pre order input ：5 3 2 0 0 0 8 6 0 0 9 0 0
Preorder traversal output ：5 3 2 8 6 9
Middle order traversal output ：2 3 5 6 8 9
Post order traversal output ：2 3 6 9 8 5
Hierarchical traversal output ：5 3 8 2 6 9
Let's establish a binary tree in the way of preorder ：
The first is to establish a binary tree ： Use the first level pointer
// First establish a binary tree
BiTree CreateTree() {
int data;
scanf("%d", &data);// Root node data
BiTree root;
if (data <= 0) {
return NULL;
} else {
root = (BiTree)malloc(sizeof(BiNode));
root->data = data;
root->lchild = CreateTree();
root->rchild = CreateTree();
}
return root;
}Test use ：
// test
int main() {
//BiTree root;
//CreateTree(&root);
BiTree root = NULL;
root = CreateTree();// Create trees
PreOrderTraverse(root);// Preorder traversal output
return 0;
}The second is to establish a binary tree ： Use the secondary pointer
// First establish a binary tree
void CreateTree(BiTree* root) {
int data;
scanf("%d", &data);// Root node data
if (data <= 0) {
*root = NULL;
} else {
(*root) = (BiTree)malloc(sizeof(BiNode));
(*root)->data = data;
CreateTree(&((*root)->lchild));
CreateTree(&((*root)->rchild));
}
} Test use ：
// test
int main() {
BiTree root;
CreateTree(&root);
//BiTree root = NULL;
//root = CreateTree();// Create trees
PreOrderTraverse(root);// Preorder traversal output
return 0;
}If not required , I prefer the first ！
3 Traversal of binary tree
3.1 The first sequence traversal
The idea of preorder traversal ：
The process of preorder traversal is to visit the root node first , Traverse the root of the left subtree first and then , Finally, first traverse the right subtree of the root . For the left subtree and right subtree of the root , The process of traversal is the same .
Scheme 1 ： recursive
Use recursion to achieve ：
// Traversing a binary tree in order : Recursive implementation
void PreOrderTraverse(BiTree root) {
if (root) {
printf("%d ", root->data);
PreOrderTraverse(root->lchild);
PreOrderTraverse(root->rchild);
}
}Option two ： Non recursive
Non recursive implementation ： Introducing auxiliary stack
// Traversing a binary tree in order : Non recursive implementation
void PreOrderTraverseNonRec(BiTree root) {
BiTree stack[MaxSize];
BiTree p;
int top = -1;
if (root != NULL) {
// Root node stack
top++;
stack[top] = root;
// Stack not empty time loop
while (top > -1) {
// Get out of the stack and access the node
p = stack[top];
top--;
printf("%d ", p->data);
// Right child in the stack
if (p->rchild != NULL) {
top++;
stack[top] = p->rchild;
}
// Left child in the stack
if (p->lchild != NULL) {
top++;
stack[top] = p->lchild;
}
}
}
}3.2 In the sequence traversal
The idea of middle order traversal
The process of middle order traversal is to traverse the left subtree first , Then access the root node , Finally, the middle order traverses the right subtree of the root . For the left subtree and right subtree of the root , The process of traversal is the same .
Scheme 1 ： recursive
Use recursion to achieve ：
// Middle order ergodic binary tree : Recursive implementation
void InOrderTraverse(BiTree root) {
if (root) {
InOrderTraverse(root->lchild);
printf("%d ", root->data);
InOrderTraverse(root->rchild);
}
} Option two ： Non recursive
Non recursive implementation ： Introducing auxiliary stack
// Middle order ergodic binary tree : Non recursive implementation
void InOrderTraverseNonRec(BiTree root) {
BiTree stack[MaxSize];
BiTree p;
int top = -1;
if (root != NULL) {
p = root;
while (top > -1 || p != NULL) {
// scanning p All left nodes of are merged into the stack
while (p != NULL) {
top++;
stack[top] = p;
p = p->lchild;
}
if (top > -1) {
// Get out of the stack and access the node
p = stack[top];
top--;
printf("%d ", p->data);
// Scan right child
p = p->rchild;
}
}
}
}3.3 After the sequence traversal
The idea of post order traversal
The process of post order traversal is to traverse the left subtree first , Then traverse the right subtree of the root in order , Finally, visit the root node .
Scheme 1 ： recursive
Use recursion to achieve ：
// Post order traversal binary tree : Recursive implementation
void PostOrderTraverse(BiTree root) {
if (root) {
PostOrderTraverse(root->lchild);
PostOrderTraverse(root->rchild);
printf("%d ", root->data);
}
} Option two ： Non recursive
Non recursive implementation ： Introducing auxiliary stack
// Post order traversal binary tree : Non recursive implementation
void PostOrderTraverseNonRec(BiTree root) {
BiTree stack[MaxSize];
BiTree p;
int top = -1;
int sign;
if (root != NULL) {
do {
//root Nodes on the stack
while (root != NULL) {
top++;
stack[top] = root;
root = root->lchild;
}
//p Point to the previous visited node at the top of the stack
p = NULL;
// Set up root For visited
sign = 1;
while (top != -1 && sign) {
// Take out the top node of the stack
root = stack[top];
// If the right child does not exist or the right child has been accessed, access root
if (root->rchild == p) {
printf("%d ", root->data);
top--;
//p Point to the accessed node
p = root;
} else {
//root Point to the right child node
root = root->rchild;
// Set no access flag
sign = 0;
}
}
} while (top != -1);
}
}3.4 Level traversal
The idea of hierarchical traversal ：
Ideas ： When traversing the hierarchy , After accessing the first level nodes, access the left and right children of each node in order according to their access order , In this way, one layer after another , First encountered node first visited , The hierarchical traversal sequence of this binary tree is 5 3 8 2 6 9, First up and down , First left to right . It is convenient to use queue to realize hierarchical traversal , Because it's first in, first out （FIFO）. First turn on the 5 The team , Then output the first element of the team , And join the left node and right node of the team head element into the team （ If any ）, And so on , The output sequence is hierarchical traversal
It is realized in a non recursive way ： Introduction queue
// Level traversal : Non recursive implementation
void LevelOrderTraverseNonRec(BiTree root) {
BiTree p;
Push(root);
while (!empty()) {//empty() Determines if the queue is empty
p = Pop();// Out of the team
printf("%d ", p->data);// Output the first node of the team
if (p->lchild) {// hold Pop The left child of the dropped node joins the queue
Push(p->lchild);
}
if (p->rchild) {// hold Pop The right child of the dropped node joins the queue
Push(p->rchild);
}
}
} The code of queue part is attached ：
// Queue structure
typedef struct queue {
struct TreeNode* numQueue[MaxSize];
int front;
int rear;
} Queue;
Queue queue;// Declare global variables
// Initialize queue
void initQueue() {
queue.front = 0;
queue.rear = 0;
}
// The team
void Push(BiTree root) {
queue.numQueue[++queue.rear] = root;
}
// Out of the team
BiTree Pop() {
return queue.numQueue[++queue.front];
}
// Determines if the queue is empty
int empty() {
return queue.rear == queue.front;
} 4 Find the maximum depth of a binary tree
The maximum depth of a tree , Maximum depth of left subtree and right subtree + 1 that will do .
Use recursion to achieve ：
// The maximum depth of a binary tree
int maxDepth(BiTree root) {
if (root) {
int maxLeft = maxDepth(root->lchild);
int maxRight = maxDepth(root->rchild);
if (maxLeft > maxRight) {
return maxLeft + 1;
} else {
return maxRight + 1;
}
}
return 0;
} 5 Find the height of the binary tree
Use recursion to achieve
// The height of the binary tree
int BiTreeHeight(BiTree root) {
if (root) {
int leftHeight = BiTreeHeight(root->lchild);
int rightHeight = BiTreeHeight(root->rchild);
return (leftHeight > rightHeight) ? (leftHeight + 1) : (rightHeight + 1);
}
return 0;
}6 Find the number of leaf nodes of binary tree
The degree of a node is the number of branches of a node , If the nodes in the binary tree are classified according to degree , Divided into three categories , The degrees are 0、1、2 The node of , We express its quantity as n0、n1、n2, And we use the total points of a tree N To express . Then the number of leaf nodes of a number is n0, And there are N = n0 + n1 + n2.
If we calculate the total points of a tree according to the number of child nodes of a tree , So the total number of points of a binary tree N = 2 * n2 + n1 + 1, the last one 1 Represents the root node of the tree . We will talk about N The two equations of merge , There is a conclusion ：n0 = n2 + 1.
Use recursion to achieve
// Leaf node
int LeafNodeNum(BiTree root) {
if (root == NULL) {
return 0;
}
if (root->lchild == NULL && root->rchild == NULL) {
return 1;
} else {
return LeafNodeNum(root->lchild) + LeafNodeNum(root->rchild);
}
} 7 Please k The number of layer nodes
Use recursion to achieve ：
// Please k The number of layer nodes
int LevelNodeNum(BiTree root, int k) {
if (root == NULL || k < 1) {
return 0;
}
if (k == 1) {
return 1;
}
return LevelNodeNum(root->lchild, k - 1) + LevelNodeNum(root->rchild, k - 1);
} 8 Find the total number of nodes in the binary tree
Use recursion to achieve ：
// Find the total number of nodes in the binary tree
int CountNode(BiTree root) {
if (root) {
if ((root->lchild == NULL) && (root->rchild == NULL)) {
return 1;
} else {
return CountNode(root->lchild) + CountNode(root->rchild) + 1;
}
}
return 0;
} 9 The search element is x The node of
Use recursion to achieve ：
// The search element is x The node of
BiTree SearchNode(BiTree root, int x) {
if (root) {
if (root->data == x) {
return root;
} else {
BiTree p;
p = SearchNode(root->lchild, x);
if (!p) {
p = SearchNode(root->rchild, x);
}
return p;
}
}
return NULL;
}10 Binary tree operation complete code
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100
// Tree structure
typedef struct TreeNode {
int data;// Data fields
struct TreeNode* lchild;// Point to the left child node
struct TreeNode* rchild;// Point to the right child node
} BiNode, *BiTree;
// Queue structure
typedef struct queue {
struct TreeNode* numQueue[MaxSize];
int front;
int rear;
} Queue;
Queue queue;// Declare global variables
// Initialize queue
void initQueue() {
queue.front = 0;
queue.rear = 0;
}
// The team
void Push(BiTree root) {
queue.numQueue[++queue.rear] = root;
}
// Out of the team
BiTree Pop() {
return queue.numQueue[++queue.front];
}
// Determines if the queue is empty
int empty() {
return queue.rear == queue.front;
}
// Construct a binary tree
BiTree CreateTree() {
int data;
scanf("%d", &data);// Root node data
BiTree root;
if (data <= 0) {
return NULL;
} else {
root = (BiTree)malloc(sizeof(BiNode));
root->data = data;
//printf(" Please enter %d The left subtree ：", root->data);
root->lchild = CreateTree();
//printf(" Please enter %d The right subtree ：", root->data);
root->rchild = CreateTree();
}
return root;
}
// Traversing a binary tree in order : Recursive implementation
void PreOrderTraverse(BiTree root) {
if (root) {
printf("%d ", root->data);
PreOrderTraverse(root->lchild);
PreOrderTraverse(root->rchild);
}
}
// Traversing a binary tree in order : Non recursive implementation
void PreOrderTraverseNonRec(BiTree root) {
BiTree stack[MaxSize];
BiTree p;
int top = -1;
if (root != NULL) {
// Root node stack
top++;
stack[top] = root;
// Stack not empty time loop
while (top > -1) {
// Get out of the stack and access the node
p = stack[top];
top--;
printf("%d ", p->data);
// Right child in the stack
if (p->rchild != NULL) {
top++;
stack[top] = p->rchild;
}
// Left child in the stack
if (p->lchild != NULL) {
top++;
stack[top] = p->lchild;
}
}
}
}
// Middle order ergodic binary tree : Recursive implementation
void InOrderTraverse(BiTree root) {
if (root) {
InOrderTraverse(root->lchild);
printf("%d ", root->data);
InOrderTraverse(root->rchild);
}
}
// Middle order ergodic binary tree : Non recursive implementation
void InOrderTraverseNonRec(BiTree root) {
BiTree stack[MaxSize];
BiTree p;
int top = -1;
if (root != NULL) {
p = root;
while (top > -1 || p != NULL) {
// scanning p All left nodes of are merged into the stack
while (p != NULL) {
top++;
stack[top] = p;
p = p->lchild;
}
if (top > -1) {
// Get out of the stack and access the node
p = stack[top];
top--;
printf("%d ", p->data);
// Scan right child
p = p->rchild;
}
}
}
}
// Post order traversal binary tree : Recursive implementation
void PostOrderTraverse(BiTree root) {
if (root) {
PostOrderTraverse(root->lchild);
PostOrderTraverse(root->rchild);
printf("%d ", root->data);
}
}
// Post order traversal binary tree : Non recursive implementation
void PostOrderTraverseNonRec(BiTree root) {
BiTree stack[MaxSize];
BiTree p;
int top = -1;
int sign;
if (root != NULL) {
do {
//root Nodes on the stack
while (root != NULL) {
top++;
stack[top] = root;
root = root->lchild;
}
//p Point to the previous visited node at the top of the stack
p = NULL;
// Set up root For visited
sign = 1;
while (top != -1 && sign) {
// Take out the top node of the stack
root = stack[top];
// If the right child does not exist or the right child has been accessed, access root
if (root->rchild == p) {
printf("%d ", root->data);
top--;
//p Point to the accessed node
p = root;
} else {
//root Point to the right child node
root = root->rchild;
// Set no access flag
sign = 0;
}
}
} while (top != -1);
}
}
// Level traversal : Non recursive implementation
void LevelOrderTraverseNonRec(BiTree root) {
BiTree p;
Push(root);
while (!empty()) {//empty() Determines if the queue is empty
p = Pop();// Out of the team
printf("%d ", p->data);// Output the first node of the team
if (p->lchild) {// hold Pop The left child of the dropped node joins the queue
Push(p->lchild);
}
if (p->rchild) {// hold Pop The right child of the dropped node joins the queue
Push(p->rchild);
}
}
}
// The maximum depth of a binary tree
int maxDepth(BiTree root) {
if (root) {
int maxLeft = maxDepth(root->lchild);
int maxRight = maxDepth(root->rchild);
if (maxLeft > maxRight) {
return maxLeft + 1;
} else {
return maxRight + 1;
}
}
return 0;
}
// The height of the binary tree
int BiTreeHeight(BiTree root) {
if (root) {
int leftHeight = BiTreeHeight(root->lchild);
int rightHeight = BiTreeHeight(root->rchild);
return (leftHeight > rightHeight) ? (leftHeight + 1) : (rightHeight + 1);
}
return 0;
}
// Leaf node
int LeafNodeNum(BiTree root) {
if (root == NULL) {
return 0;
}
if (root->lchild == NULL && root->rchild == NULL) {
return 1;
} else {
return LeafNodeNum(root->lchild) + LeafNodeNum(root->rchild);
}
}
// Please k The number of layer nodes
int LevelNodeNum(BiTree root, int k) {
if (root == NULL || k < 1) {
return 0;
}
if (k == 1) {
return 1;
}
return LevelNodeNum(root->lchild, k - 1) + LevelNodeNum(root->rchild, k - 1);
}
// Find the total number of nodes in the binary tree
int CountNode(BiTree root) {
if (root) {
if ((root->lchild == NULL) && (root->rchild == NULL)) {
return 1;
} else {
return CountNode(root->lchild) + CountNode(root->rchild) + 1;
}
}
return 0;
}
// The search element is x The node of
BiTree SearchNode(BiTree root, int x) {
if (root) {
if (root->data == x) {
return root;
} else {
BiTree p;
p = SearchNode(root->lchild, x);
if (!p) {
p = SearchNode(root->rchild, x);
}
return p;
}
}
return NULL;
}
// test
int main() {
// Test data ：5 3 2 0 0 0 8 6 0 0 9 0 0
//BiTree root;
//CreateTree(&root);
BiTree root = NULL;
root = CreateTree();// Create trees
printf(" Preorder non recursive traversal ：");
PreOrderTraverseNonRec(root);
printf("\n Middle order non recursive traversal ：");
InOrderTraverseNonRec(root);
printf("\n Postorder non recursive traversal ：");
PostOrderTraverseNonRec(root);
printf("\n First order recursive traversal ：");
PreOrderTraverse(root);// Preorder traversal output
printf("\n Middle order recursive traversal ：");
InOrderTraverse(root);// Middle order traversal output
printf("\n Backward recursive traversal ：");
PostOrderTraverse(root);// Middle order traversal output
printf("\n Hierarchical non recursive traversal ：");
LevelOrderTraverseNonRec(root);// Hierarchical traversal output
printf("\n The depth of the binary tree is ：%d",maxDepth(root));
printf("\n The height of the binary tree is ：%d",BiTreeHeight(root));
printf("\n The leaf node is ：%d",LeafNodeNum(root));
printf("\n The total node is ：%d", CountNode(root));
printf("\n The first 3 The number of layer nodes is ：%d",LevelNodeNum(root, 3));
BiTree q;
q = SearchNode(root, 9);
if (q) {
printf("\n We found it ：%d", q->data);
} else {
printf("\n Not found 9 ");
}
return 0;
}边栏推荐
- cvpr2022去雨去雾
- Restcloud ETL cross database data aggregation operation
- Coroutinecontext in kotlin
- Leetcode (540) -- a single element in an ordered array
- 面试八股文整理版
- 各国Web3现状与未来
- Thread safe singleton mode
- 简单理解svg
- Explore the conversion between PX pixels and Pt pounds, mm and MM
- How to find summer technical internship in junior year? Are you looking for a large company or a small company for technical internship?
猜你喜欢
Flink CDC mongoDB 使用及Flink sql解析monggo中复杂嵌套JSON数据实现
Detailed introduction to the usage of Nacos configuration center
Introduce in detail how to communicate with Huawei cloud IOT through mqtt protocol
Recommendation letter of "listing situation" -- courage is the most valuable
Create + register sub apps_ Define routes, global routes and sub routes
通达OA v12流程中心
Stm32f407 ------- IIC communication protocol
![[shutter] top navigation bar implementation (scaffold | defaulttabcontroller | tabbar | tab | tabbarview)](/img/f1/b17631639cb4f0f58007b86476bcc2.gif)
[shutter] top navigation bar implementation (scaffold | defaulttabcontroller | tabbar | tab | tabbarview)
![[shutter] pull the navigation bar sideways (drawer component | pageview component)](/img/6f/dfc9dae5f890125d0cebdb2a0f4638.gif)
[shutter] pull the navigation bar sideways (drawer component | pageview component)
Awk from introduction to earth (0) overview of awk
随机推荐
The use of Flink CDC mongodb and the implementation of Flink SQL parsing complex nested JSON data in monggo
GBase 8c系统表-pg_auth_members
How do it students find short-term internships? Which is better, short-term internship or long-term internship?
Explore the conversion between PX pixels and Pt pounds, mm and MM
Javescript 0.1 + 0.2 = = 0.3 problem
通达OA v12流程中心
Codeforces Round ＃418 (Div. 2) D. An overnight dance in discotheque
How to deal with cache hot key in redis
Flink CDC mongoDB 使用及Flink sql解析monggo中复杂嵌套JSON数据实现
Cfdiv2 Fixed Point Guessing - (2 points for Interval answer)
Summary of ES6 filter() array filtering methods
人脸识别6- face_recognition_py-基于OpenCV使用Haar级联与dlib库进行人脸检测及实时跟踪
cvpr2022去雨去雾
Comment communiquer avec Huawei Cloud IOT via le Protocole mqtt
Oauth2.0 authentication, login and access "/oauth/token", how to get the value of request header authorization (basictoken)???
Memory pool (understand the process of new developing space from the perspective of kernel)
Gbase 8C system table PG_ auth_ members
Detailed introduction to the deployment and usage of the Nacos registry
COM and cn
require.context