线索二叉树的实现(C语言)
2021/4/30 18:57:11
本文主要是介绍线索二叉树的实现(C语言),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
线索二叉树的实现(C语言)
- 线索二叉树
- 操作
- 线索二叉树的建立
- 线索二叉树的线索化
- 线索二叉树的遍历
- 总体
明天就要五一去重庆了,今天在坚持一下把这篇博文写完,也能减轻不少玩的负罪感啦。
线索二叉树
鉴于普通二叉树使用过程中会出现空间的浪费,后人对在在二叉树的的基础上做了改进,利用它的空指针域存放在某种遍历次序下指向它的前驱结点,和后继结点的指针。这些指针称为线索,相应的二叉树就成了线索二叉树。
我们就充分利用二叉链表的空闲结点进行操作,使之充分利用。
也就是在定义结构时外加两个标志域,若结点有左子树,则Lchild指向左孩子,否则指向前驱;若结点有右子树,则Lchild指向右孩子,否则指向后驱。
操作
线索二叉树的建立
///线索二叉树的建立 ThreadTree InitThreadTree(){ char ch; ThreadTree T; scanf("%c", &ch); if(ch == '#') T = NULL; else{ T = (ThreadTree)malloc(sizeof(ThreadNode)); T->data = ch; T->lchild = InitThreadTree(); T->rchild = InitThreadTree(); } return T; }
线索二叉树的线索化
///线索二叉树的线索化 /* * 首先如果根节点的lchild为null,那么根节点的lchild为pre为null * 第二个if的时候,pre不为null的时候才执行,第一次是不执行的 * 根节点的左孩子线索完毕之后,pre就指向了根节点了,然后递归 * 递归之后,指针pre每次都会指向刚刚访问过的节点 * 中序遍历,如果左孩子不为空,就会一直继续处理左孩子知道左孩子为空,然后处理右孩子 */ void InThread(ThreadTree p,ThreadTree pre){ if(p != NULL){ //p是当前节点,pre是刚访问的节点 InThread(p->lchild, pre); //递归,优化左子树 if(p->lchild == NULL){ //左子树为空,建立前驱线索 p->lchild = pre; p->ltag = 1; } if(pre != NULL && pre->rchild == NULL){ pre->rchild = p; //右子树为空,就建立前驱节点的后及线索 pre->rtag = 1; } pre = p; //p刚刚访问过了,则pre = p InThread(p->rchild, pre); //递归,优化右子树 } } void CreateInThread(ThreadTree T){ ThreadTree pre = NULL; if(T != NULL){ InThread(T, pre); pre->rchild = NULL; //处理遍历的最后一个节点 pre->rtag = 1; } }
线索二叉树的遍历
///线索二叉树的遍历 /* firstnode是中序遍历下面的第一个访问的节点 nextnode是这个结点在中序遍历下面访问的下一个节点 如果有右子树的链接,则下一个节点就是rchild 如果没有,表示存在右子树,由中序遍历的递归思想,下一个节点就相当于以这个结点的右节点为根节点在中序遍历下面的首节点 nextNode = firstNode(p->rchild); */ ThreadTree FirstNode(ThreadTree p){ while(p->ltag == 0) p = p->lchild; return p; } ThreadTree NextNode(ThreadTree p){ if(p->rtag == 0) return FirstNode(p->rchild); //有右节点,访问以右节点为根的树的第一个节点 else return p->rchild; //rtag为1时候,rchild总是指向下一个 } void Visit(ThreadTree T){ printf("%c ", T->data); } void InOrder(ThreadTree T){ for(ThreadTree p = FirstNode(T); p != NULL; p = NextNode(p)) Visit(p); }
总体
#include<stdio.h> #include<stdlib.h> typedef struct ThreadNode{ char data; struct ThreadNode * lchild, * rchild; int ltag, rtag;//0为不建立前驱或后驱,1为建立 }ThreadNode, * ThreadTree; ThreadTree InitThreadTree(); void InThread(ThreadTree p,ThreadTree pre); //通过中序遍历对二叉树线索化 void CreateInThread(ThreadTree T); //通过中序遍历建立中序二叉树 ThreadTree FirstNode(ThreadTree p); //求中序遍历下的第一个节点 ThreadTree NextNode(ThreadTree p); //求节点p在中序序列下的后一个节点 void Visit(ThreadTree T); void InOrder(ThreadTree T); //中序遍历 ///线索二叉树的建立 ThreadTree InitThreadTree(){ char ch; ThreadTree T; scanf("%c", &ch); if(ch == '#') T = NULL; else{ T = (ThreadTree)malloc(sizeof(ThreadNode)); T->data = ch; T->lchild = InitThreadTree(); T->rchild = InitThreadTree(); } return T; } ///线索二叉树的线索化 /* * 首先如果根节点的lchild为null,那么根节点的lchild为pre为null * 第二个if的时候,pre不为null的时候才执行,第一次是不执行的 * 根节点的左孩子线索完毕之后,pre就指向了根节点了,然后递归 * 递归之后,指针pre每次都会指向刚刚访问过的节点 * 中序遍历,如果左孩子不为空,就会一直继续处理左孩子知道左孩子为空,然后处理右孩子 */ void InThread(ThreadTree p,ThreadTree pre){ if(p != NULL){ //p是当前节点,pre是刚访问的节点 InThread(p->lchild, pre); //递归,优化左子树 if(p->lchild == NULL){ //左子树为空,建立前驱线索 p->lchild = pre; p->ltag = 1; } if(pre != NULL && pre->rchild == NULL){ pre->rchild = p; //右子树为空,就建立前驱节点的后及线索 pre->rtag = 1; } pre = p; //p刚刚访问过了,则pre = p InThread(p->rchild, pre); //递归,优化右子树 } } void CreateInThread(ThreadTree T){ ThreadTree pre = NULL; if(T != NULL){ InThread(T, pre); pre->rchild = NULL; //处理遍历的最后一个节点 pre->rtag = 1; } } ///线索二叉树的遍历 /* firstnode是中序遍历下面的第一个访问的节点 nextnode是这个结点在中序遍历下面访问的下一个节点 如果有右子树的链接,则下一个节点就是rchild 如果没有,表示存在右子树,由中序遍历的递归思想,下一个节点就相当于以这个结点的右节点为根节点在中序遍历下面的首节点 nextNode = firstNode(p->rchild); */ ThreadTree FirstNode(ThreadTree p){ while(p->ltag == 0) p = p->lchild; return p; } ThreadTree NextNode(ThreadTree p){ if(p->rtag == 0) return FirstNode(p->rchild); //有右节点,访问以右节点为根的树的第一个节点 else return p->rchild; //rtag为1时候,rchild总是指向下一个 } void Visit(ThreadTree T){ printf("%c ", T->data); } void InOrder(ThreadTree T){ for(ThreadTree p = FirstNode(T); p != NULL; p = NextNode(p)) Visit(p); } int main() { ThreadNode *T=(ThreadNode*)malloc(sizeof(ThreadNode)); T=InitThreadTree(); InThread(T,NULL); InOrder(T); return 0; }
这篇关于线索二叉树的实现(C语言)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升