news 2026/8/23 7:26:55

二叉树的遍历 线索二叉树

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
二叉树的遍历 线索二叉树

二叉树的存储结构--链式存储

二叉树的遍历-前序遍历

两个 return，两种退出函数的方式

  1. 手写return;仅当T==NULL（空节点）触发，直接结束当前这一次函数调用。

  2. 隐式自动 return（重点！你疑惑的点）

当节点不为 NULL，函数中所有代码全部执行完毕，走到函数最后的大括号}，C 语言 void 函数会自动返回上一层调用处，不需要写 return 关键字。

❗每一次函数调用，都有自己独立的局部变量 T。下层函数的 T，不会修改上层函数的 T。

示例：执行 preOrder (H) 的完整流程

  1. T=H，H 不为 NULL，跳过 if，打印 H。
  2. 执行preOrder(H->lchild)：左孩子为空，触发手写return;，回到 H 函数，左递归语句结束。
  3. 执行preOrder(H->rchild)（节点 K）
    • T=K，不为 NULL，打印 K
    • K 左为空：手写 return，回到 K 函数
    • K 右为空：手写 return，回到 K 函数
    • K 内部全部代码跑完，遇到}，隐式自动 return，回到 H 函数。
  4. H 函数：printf、左递归、右递归全部执行完成。走到}，隐式自动 return，回到 D 函数中调用 H 的那一行。
#include <stdio.h> typedef char ElemType; tyedef struct TreeNoed { ElemType data; struct TreeNode *lchild; struct TreeNode *rchild; }TreeNode; typedef TreeNode* BigTree;//指针的指针 char str[]="ABDH#K###E##CFI###G#J##"; //传入节点从左到右 int idex=0; void createTree(BigTree *T)//BeTree是一级指针，BeTree*是二级指针，也就是传的参数是二级指针 { //通过递归的方式造树 ElemType ch; ch=str[idx++]; if(ch=='#') { *T=NULL; } else { *T=(BiTree)malloc(sizeof(TreeNode)); //赋值 创建节点 (*T)->data=ch; createTree(&(*T)->lchild); createTree(&(*T)->rchild); } } void inOrder(BiTree T) { if(T==NULL) { return; } printf("%c ",T->data); preOrder(T->lchild); preOder(T->rchild); } int main() { BiTree T; createTree(&T); preOrder(T); printf("\n"); return 0; }

中序遍历

#include <stdio.h> typedef char ElemType; tyedef struct TreeNoed { ElemType data; struct TreeNode *lchild; struct TreeNode *rchild; }TreeNode; typedef TreeNode* BigTree;//指针的指针 char str[]="ABDH#K###E##CFI###G#J##"; //传入节点从左到右 int idex=0; void createTree(BigTree *T)//BeTree是一级指针，BeTree*是二级指针，也就是传的参数是二级指针 { //通过递归的方式造树 ElemType ch; ch=str[idx++]; if(ch=='#') { *T=NULL; } else { *T=(BiTree)malloc(sizeof(TreeNode)); //赋值 创建节点 (*T)->data=ch; createTree(&(*T)->lchild); createTree(&(*T)->rchild); } } void inOrder(BiTree T) { if(T==NULL) { return; } preOrder(T->lchild); printf("%c ",T->data); preOder(T->rchild); } int main() { BiTree T; createTree(&T); preOrder(T); printf("\n"); return 0; }

后序遍历

#include <stdio.h> typedef char ElemType; tyedef struct TreeNoed { ElemType data; struct TreeNode *lchild; struct TreeNode *rchild; }TreeNode; typedef TreeNode* BigTree;//指针的指针 char str[]="ABDH#K###E##CFI###G#J##"; //传入节点从左到右 int idex=0; void createTree(BigTree *T)//BeTree是一级指针，BeTree*是二级指针，也就是传的参数是二级指针 { //通过递归的方式造树 ElemType ch; ch=str[idx++]; if(ch=='#') { *T=NULL; } else { *T=(BiTree)malloc(sizeof(TreeNode)); //赋值 创建节点 (*T)->data=ch; createTree(&(*T)->lchild); createTree(&(*T)->rchild); } } void inOrder(BiTree T) { if(T==NULL) { return; } preOrder(T->lchild); preOder(T->rchild); printf("%c ",T->data); } int main() { BiTree T; createTree(&T); preOrder(T); printf("\n"); return 0; }

非递归前序遍历

二叉树性质

线索二叉树

存储结构

#include <stdio.h> #include <stdlib.h> typedef cahr ElemType; //定义线索二叉树的节点结构 typedef struct ThreadNode{ ElemType data; struct ThreadNode *lchild; struct ThreadNode *rchild; int ltag; //左标志：0表示左孩子，1表示前驱线索 int rtag; // 右标志：0表示有右孩子，1表示后驱线索 }ThreadNode; typedef ThreadNode* ThreadTree; char str[]="ABDH##I##EJ###CF##G##"; int idx=0; ThreadTree prev; //创建普通二叉树 void createTree(ThreadTree *T){ ElemType ch=str[idx++]; if(ch=='#'){ *T=NULL;//空节点 }else{ *T=(TreadTree)malloc(sizeof(ThreadNode)); (*T)->data=ch; createTree(&(*T)->lchild); //构建左子树，0为有左子树，1为有线索 (*T)->ltag=(*T)->lchild ? 0:1; createTree(&*(T)->rchild); (*T)->rtag=(*T)>rchild ? 0:1; } //中序线索化函数：建立前驱/后驱关系 void threading(ThreadTree T){ if(T!=NULL){ threading(T-lchild); //递归线索化左子树 // 如果当前节点左指针为空，建立前驱线索 if(T->ltag==1) T->lchild=prev; //如果前一个节点的右指针为空，建立其后继线索指向当前节点 if(prev&&prev->tag==1) prev->rchild=T; prev=T; //更新 prev为当前节点 threading(T->child); //线索化递归右子树 } } //创建头节点，调用线索化过程，建立线索二叉树 void inOderThreading (Threading *T,ThreadTree *head) { *head=(ThreadTree)malloc(sizeof(ThreadNode)); (*head)->ltag=0; (*head)->rtag=1; (*head)->rchild=*head; //初始时回指向自己 if(*T==NULL){ (*head)->lchild=*head; //空树的情况 }else{ (*head)->lchild=*T; //头节点左指向根节点 prev=*head; //初始化前驱指针 保存着上一个访问的节点 threading(*T); //中序线索化整个树 //补全最后一个节点的后继线索 prev->rchild=*head; //prev->rtag=1; (*head)->rchild=prev; } } //中序线索遍历线索化后的二叉树（非递归） void inOder(ThreadTree T){ ThreadTree curr=T->lchild; //从头节点的左子树开始 while(curr!=T){ //沿左孩子一直走到底 while(curr->ltag==0) curr=curr->lchild; //直至找不到 输出 printf("%c",curr->data); //顺着线索一直向右访问所有后继 while(curr->rtag==1&&curr->rchild!=T){ curr=curr->rchild; printf("%c",curr->data); } //进入当前节点的右子树 curr=curr->rchild; } } int main(){ ThreadTree T,head; //head 为头节点 createTree(&T); //创建原始二叉树 inOderhreaing(&T,&head); //执行线索化处理 printf("中序遍历结果:"); inOder(head); retrn 0; //遍历线索二叉树 }
版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/8/23 7:25:35

从零实现流式Markdown解析器：状态机与渐进式渲染实战

在实际前端面试中&#xff0c;流式 Markdown 解析器是一个能很好考察候选人综合能力的问题。它不像简单的算法题有标准答案&#xff0c;而是需要你理解流式处理、状态机、词法分析、语法解析、异步渲染等多个概念&#xff0c;并能将它们组合成一个可工作的方案。很多开发者对 M…

作者头像 李华
网站建设 2026/8/23 7:17:53

构建个人知识体系：从信息过载到认知清晰的四层架构与实践方法

1. 从“信息过载”到“认知清晰”&#xff1a;我们为什么需要知识体系&#xff1f;你有没有过这样的经历&#xff1f;每天刷着手机&#xff0c;收藏了无数篇“干货”文章&#xff0c;关注了几十个领域的博主&#xff0c;感觉自己每天都在学习新东西。但当你真正需要解决一个具体…

作者头像 李华
网站建设 2026/8/23 7:16:12

Claude Code v2.1.236 更新：环境变量与闲置通知如何提升AI编程效率

如果你是一名开发者&#xff0c;最近在尝试各种AI编程助手&#xff0c;可能会发现一个现象&#xff1a;很多工具要么配置繁琐&#xff0c;要么模型切换不灵活&#xff0c;要么在长时间对话后突然“失忆”&#xff0c;导致工作流中断。这些问题看似琐碎&#xff0c;却实实在在地…

作者头像 李华
网站建设 2026/8/23 7:14:26

AI绘画实战：基于Stable Diffusion生成泪痣遮眼刘海女性角色

这次我们来看一个关于AI绘画与角色形象生成的实际需求案例。用户的核心诉求是希望基于文字描述&#xff0c;为一位带有泪痣、刘海遮住单眼的女性角色生成无偿的肖像画。这背后反映的&#xff0c;是当前AI绘画技术如何将抽象的文字描述转化为具体、符合预期的视觉形象&#xff0…

作者头像 李华
网站建设 2026/8/23 7:11:53

企业招聘风险防控与科学评估体系构建

1. 招聘困境的本质剖析在人力资源领域摸爬滚打十几年&#xff0c;我发现一个令人深思的现象&#xff1a;超过60%的企业在入职半年内就发现新员工与岗位要求存在明显偏差。某科技公司HR总监曾向我透露&#xff0c;他们每年因招聘失误导致的重置成本高达年度人力预算的15%。这种&…

作者头像 李华
网站建设 2026/8/23 7:11:14

从时序数据到分类模型：人类活动识别的特征工程与机器学习实战

1. 从“人类活动分类”到数学建模实战&#xff1a;一次完整的解题思路拆解最近在整理过往的竞赛资料&#xff0c;翻到了2022年小美赛&#xff08;美国大学生数学建模竞赛&#xff0c;MCM/ICM&#xff09;的C题“Classify Human Activities”。这道题当时在圈内讨论度很高&#…

作者头像 李华