当前位置：网站首页>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;
}边栏推荐
猜你喜欢
Trial setup and use of idea GoLand development tool
![[shutter] pull the navigation bar sideways (drawer component | pageview component)](/img/6f/dfc9dae5f890125d0cebdb2a0f4638.gif)
[shutter] pull the navigation bar sideways (drawer component | pageview component)
![[Flutter] dart: class；abstract class；factory；类、抽象类、工厂构造函数](/img/06/ab333a4752de27eae2dd937cf579e2.png)
[Flutter] dart: class；abstract class；factory；类、抽象类、工厂构造函数
Pytorch convolution network regularization dropblock
通达OA v12流程中心
返回一个树形结构数据
4. 类和对象
Oauth2.0 authentication, login and access "/oauth/token", how to get the value of request header authorization (basictoken)???
UDP receive queue and multiple initialization test
![[shutter] bottom navigation bar implementation (bottomnavigationbar bottom navigation bar | bottomnavigationbaritem navigation bar entry | pageview)](/img/41/2413af283e8f1db5d20ea845527175.gif)
[shutter] bottom navigation bar implementation (bottomnavigationbar bottom navigation bar | bottomnavigationbaritem navigation bar entry | pageview)
随机推荐
[shutter] top navigation bar implementation (scaffold | defaulttabcontroller | tabbar | tab | tabbarview)
[shutter] bottom navigation bar implementation (bottomnavigationbar bottom navigation bar | bottomnavigationbaritem navigation bar entry | pageview)
我的创作纪念日
GBase 8c系统表-pg_attribute
Machine learning process and method
Gbase 8C system table PG_ class
面试八股文整理版
GBase 8c系统表-pg_authid
where 1=1 是什么意思
Gbase 8C function / stored procedure parameters (I)
【 tutoriel】 Chrome ferme les cors et les messages de la politique inter - domaines et apporte des cookies à travers les domaines
String replace space
What are MySQL locks and classifications
Awk from getting started to getting into the ground (3) the built-in functions printf and print of awk realize formatted printing
Gbase 8C system table PG_ database
Gbase 8C system table PG_ auth_ members
Iptables layer 4 forwarding
udp接收队列以及多次初始化的测试
詳細些介紹如何通過MQTT協議和華為雲物聯網進行通信
苏世民：25条工作和生活原则