二叉树的建立、先中后遍历以及层次遍历,交换左右子树,凹入打印二叉树,删除结点
根据给定文件的信息,本文将详细介绍二叉树的建立、先序、中序、后序以及层次遍历方法,左右子树的交换操作,以及如何实现凹入打印二叉树和删除节点等知识点。 ### 一、二叉树的建立 在给定的代码片段中,`bintree` 结构体定义了一个典型的二叉树节点结构,包含数据域 `data` 和两个指向左右子树的指针 `lchild` 和 `rchild`。此外还有一个 `next` 指针,用于链接不同的树节点。 二叉树的建立主要通过递归方式完成。在 `create()` 函数中,首先读取一个字符输入,如果该字符为空则返回空节点;否则创建一个新的节点,并递归地为该节点建立左右子树。这样通过不断输入字符来构建一棵完整的二叉树。 ### 二、遍历二叉树 #### 1. 先序遍历 (Preorder Traversal) 先序遍历的顺序是:根节点 -> 左子树 -> 右子树。在给定代码中,`preorder()` 函数实现了这一逻辑。具体实现时,首先访问当前节点,然后递归遍历左子树和右子树。 #### 2. 中序遍历 (Inorder Traversal) 中序遍历的顺序是:左子树 -> 根节点 -> 右子树。`inorder()` 函数实现了这一过程。其步骤为先递归遍历左子树,再访问当前节点,最后递归遍历右子树。 #### 3. 后序遍历 (Postorder Traversal) 后序遍历的顺序是:左子树 -> 右子树 -> 根节点。`postorder()` 函数实现了这一遍历方式。它先递归遍历左子树,接着遍历右子树,最后才访问当前节点。 #### 4. 层次遍历 (Level Order Traversal) 层次遍历是指按照树的层级自上而下、由左至右依次访问所有节点。在给定代码中,`levelorder()` 函数使用了链表的方式实现了层次遍历。首先将根节点加入到链表中,然后遍历链表中的每个节点,将其左右子节点(如果存在的话)加入到链表中,直到链表为空为止。最后按顺序输出链表中的节点值即可得到层次遍历的结果。 ### 三、交换左右子树 `exchange()` 函数用于交换二叉树中所有节点的左右子树。这通过遍历整个二叉树并交换每个节点的 `lchild` 和 `rchild` 指针来实现。同时为了可视化地展示出交换前后的效果,还调用了 `indentation()` 函数来进行凹入打印。 ### 四、凹入打印二叉树 `indentation()` 函数实现了对二叉树的凹入打印。通过传入一个表示当前节点深度的参数 `n`,可以控制每一层的缩进量。具体来说,对于每个节点,先输出相应数量的空格作为缩进,然后输出节点的数据。这种打印方式能够让二叉树的结构更加清晰易见。 ### 五、删除节点 `deletenode()` 函数实现了删除指定数据的节点。该函数首先提示用户输入要删除的节点的数据,然后遍历整个二叉树寻找这个节点。一旦找到目标节点,就将其数据设为0,并将其左右子树置为 NULL,从而实现删除节点的操作。最后同样调用 `indentation()` 函数来展示删除后的结果。 以上就是从给定文件的标题、描述、标签以及部分内容中提取的相关知识点。这些操作涵盖了二叉树的基本概念及其常用操作,对于理解和应用二叉树具有重要的意义。
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
/*结构体定义*/
typedef struct tree
{
char data; //数据域
struct tree *lchild; //左孩子
struct tree *rchild; //右孩子
struct tree *next; //用于构造队列
}bintree;
//二叉树的建立
bintree *create()
{
char ch;
bintree * t;
ch=getche(); //依次读入字符
if(ch==' ') t=NULL; // 表示空结点
else
{
t=(bintree *)malloc(sizeof(bintree)); //非空则构造新结点
t->data=ch; //新结点数据域即为读入字符
t->next=NULL; //新结点next域暂时不用,赋空
t->lchild=create(); //建立左子树
t->rchild=create(); //建立右子树
}
return(t);
}
void indentation(bintree *root,int n)
/*凹入表示时,遍历顺序完全同于先序遍历,故每访问一个结点,将其按一定的格式输出格式为每行一个结点,,第k层次结点前输出K-1个空格,空格数记为n。采用递归算法*/
{
bintree *t=root;
int i;
if(NULL!=t)
{
for(i=0;i<n;++i)
printf(" "); //输出n个空格
printf("%c\n",t->data); //访问根结点
n++; //层次加深一层,n也相应自增一
indentation(t->lchild,n); //先序遍历左子树
indentation(t->rchild,n); //先序遍历右子树
}
}
//先序遍历
void preorder(bintree *root)
{
bintree *t=root;
if(NULL!=t)
{
printf("%c ",t->data); //访问根结点
preorder(t->lchild); //先序遍历左子树
preorder(t->rchild); //先序遍历右子树
}
}
剩余6页未读,继续阅读
bh21sdm89SHH2012-05-30是txt格式的,
- 粉丝: 0
我的内容管理
展开
我的资源
快来上传第一个资源
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏
我的下载
下载帮助
前往需求广场,查看用户热搜最新资源
- (源码)基于ESP32的无线控制应用.zip
- ppt模板:蓝色大气未来智慧城市发展规划年终报告模板.pptx
- plc机械手控制系统设计4组.doc
- 大数据方案介绍.docx
- 电信大数据的研究与应用.docx
- 别墅智能家居系统方案设计书要求.doc
- 通信中练习综合能力.doc
- 计算机技术在生物信息学研究中的应用分析.docx
- 计算机的认识和计算PPT.ppt
- 湖南科技计划项目管理申报指南.doc
- 应用型本科院校《数据通信与计算机网络》课程的改革与探索.docx
- Docker安装-Nginx.doc
- 电力营销系统现状与信息化系统的建设探讨.docx
- 电力调度自动化系统及计算机网络防雷措施.doc
- Vb保存幅图到Access数据库.doc
- (源码)基于Arduino的Si5351替代石英项目.zip


信息提交成功