二叉树的遍历 线索二叉树

二叉树的存储结构--链式存储二叉树的遍历-前序遍历两个 return两种退出函数的方式手写return;仅当TNULL空节点触发直接结束当前这一次函数调用。隐式自动 return重点你疑惑的点当节点不为 NULL函数中所有代码全部执行完毕走到函数最后的大括号}C 语言 void 函数会自动返回上一层调用处不需要写 return 关键字。❗每一次函数调用都有自己独立的局部变量 T。下层函数的 T不会修改上层函数的 T。示例执行 preOrder (H) 的完整流程THH 不为 NULL跳过 if打印 H。执行preOrder(H-lchild)左孩子为空触发手写return;回到 H 函数左递归语句结束。执行preOrder(H-rchild)节点 KTK不为 NULL打印 KK 左为空手写 return回到 K 函数K 右为空手写 return回到 K 函数K 内部全部代码跑完遇到}隐式自动 return回到 H 函数。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 idex0; void createTree(BigTree *T)//BeTree是一级指针BeTree*是二级指针也就是传的参数是二级指针 { //通过递归的方式造树 ElemType ch; chstr[idx]; if(ch#) { *TNULL; } else { *T(BiTree)malloc(sizeof(TreeNode)); //赋值 创建节点 (*T)-datach; createTree((*T)-lchild); createTree((*T)-rchild); } } void inOrder(BiTree T) { if(TNULL) { 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 idex0; void createTree(BigTree *T)//BeTree是一级指针BeTree*是二级指针也就是传的参数是二级指针 { //通过递归的方式造树 ElemType ch; chstr[idx]; if(ch#) { *TNULL; } else { *T(BiTree)malloc(sizeof(TreeNode)); //赋值 创建节点 (*T)-datach; createTree((*T)-lchild); createTree((*T)-rchild); } } void inOrder(BiTree T) { if(TNULL) { 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 idex0; void createTree(BigTree *T)//BeTree是一级指针BeTree*是二级指针也就是传的参数是二级指针 { //通过递归的方式造树 ElemType ch; chstr[idx]; if(ch#) { *TNULL; } else { *T(BiTree)malloc(sizeof(TreeNode)); //赋值 创建节点 (*T)-datach; createTree((*T)-lchild); createTree((*T)-rchild); } } void inOrder(BiTree T) { if(TNULL) { 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 idx0; ThreadTree prev; //创建普通二叉树 void createTree(ThreadTree *T){ ElemType chstr[idx]; if(ch#){ *TNULL;//空节点 }else{ *T(TreadTree)malloc(sizeof(ThreadNode)); (*T)-datach; 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-ltag1) T-lchildprev; //如果前一个节点的右指针为空建立其后继线索指向当前节点 if(prevprev-tag1) prev-rchildT; prevT; //更新 prev为当前节点 threading(T-child); //线索化递归右子树 } } //创建头节点调用线索化过程建立线索二叉树 void inOderThreading (Threading *T,ThreadTree *head) { *head(ThreadTree)malloc(sizeof(ThreadNode)); (*head)-ltag0; (*head)-rtag1; (*head)-rchild*head; //初始时回指向自己 if(*TNULL){ (*head)-lchild*head; //空树的情况 }else{ (*head)-lchild*T; //头节点左指向根节点 prev*head; //初始化前驱指针 保存着上一个访问的节点 threading(*T); //中序线索化整个树 //补全最后一个节点的后继线索 prev-rchild*head; //prev-rtag1; (*head)-rchildprev; } } //中序线索遍历线索化后的二叉树非递归 void inOder(ThreadTree T){ ThreadTree currT-lchild; //从头节点的左子树开始 while(curr!T){ //沿左孩子一直走到底 while(curr-ltag0) currcurr-lchild; //直至找不到 输出 printf(%c,curr-data); //顺着线索一直向右访问所有后继 while(curr-rtag1curr-rchild!T){ currcurr-rchild; printf(%c,curr-data); } //进入当前节点的右子树 currcurr-rchild; } } int main(){ ThreadTree T,head; //head 为头节点 createTree(T); //创建原始二叉树 inOderhreaing(T,head); //执行线索化处理 printf(中序遍历结果:); inOder(head); retrn 0; //遍历线索二叉树 }