二叉树操作
2022/1/1 23:37:57
本文主要是介绍二叉树操作,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
有以下几点需要注意:
1.为根节点分配内存时,需要在函数中为一个指针分配内存,再将该指针作为返回值,用在主函数中定义的根节点指针接收该返回值。(不能将指针作为参数还妄想要给他分配内存)
2.该程序在linux 64位操作系统上成功运行。
正文部分
0.二叉树节点的结构体
typedef struct Node Node; struct Node { int value; Node *left; Node *right; int lsign; int rsign; };
1.二叉树的创建。
用-1表示每一个叶子节点的左右孩子的值,但-1并不会出现在二叉树中,你在给二叉树填值时可以先将其画出来,便于理解。
Node* create() { int n; Node* root=NULL; printf("Input the value(quit when you input -1):"); scanf("%d",&n); if(n==-1) return root; else{ root=(Node*)malloc(sizeof(Node)); root->value=n; root->lsign=0; root->rsign=0; root->left=create(); root->right=create(); return root; } }
注意:需要在主函数中创建一个根指针用于接收该函数分配出的内存(即二叉树本身)。
2.前序遍历。
void list(Node* root) { if(!root) return; printf("%d ",root->value); list(root->left); list(root->right); }
3.中序遍历。
void list(Node* root) { if(!root) return; list(root->left); printf("%d ",root->value); list(root->right); }
4.后序遍历。
void list(Node* root) { if(!root) return; list(root->left); list(root->right); printf("%d ",root->value); }
5.二叉树的线索化及线索化之后的输出。
void Threading(Node* root) {//以中序线索化为例 if(root) { Threading(root->left); if(!root->left) { root->lsign=1; root->left=pre; } if(!pre->right) { pre->right=root; pre->rsign=1; } pre=root; Threading(root->right); } }
void ThreadingList(Node* root) { Node*p=root; while(p!=NULL) { while(p->lsign==0) p=p->left; printf("%d ",p->value); while(p->rsign==1) { p=p->right; printf("%d ",p->value); } p=p->right; } }
注意:
1.函数中的pre指针我是将其作为了全局变量;
2.主函数中需要在引用该函数之前将pre指针指向root,即根指针。
6.层序遍历。
void layerlist(Node*root) { Node* queue[100]; int i=0,top=0; if(root){ queue[top]=root; } while(i<=top) { if(queue[i]->left){ queue[++top]=queue[i]->left; } if(queue[i]->right){ queue[++top]=queue[i]->right; } i++; } for(int i=0;i<=top;i++) printf("%d ",queue[i]->value); }
7.二叉树内存的释放。(普通的二叉树内存释放用后序遍历的思路很容易写出来,这里就不写了)
这里写出线索化之后的二叉树内存释放
void freeNode(Node*root) { if(root!=NULL) { if(root->lsign==0)//不通过前驱和后继 freeNode(root->left); if(root->rsign==0)//不通过前驱和后继 freeNode(root->right); free(root); root=NULL; } }
注意在释放内存时不能通过前驱和后继。
这篇关于二叉树操作的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南