首页 / 算法 / 线索二叉树（C语言）
线索二叉树（C语言）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了线索二叉树（C语言），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5299字，纯文字阅读大概需要8分钟。
内容图文
实现下面这棵树：
先序遍历: A B C D E F
中序遍历: C B D A E F
代码
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <unistd.h>
typedef enum {links, thread} TAG;
typedef struct treeNode {
char name;
struct treeNode *lchild, *rchild;
TAG ltag;
TAG rtag;
}TREENODE, *TREE;
void createTree(TREE *);
void traverse(TREE);
void traverse_middle(TREE);
void traverse_middle_detail(TREE);
// 线索化二叉树,相比普通的中序遍历，这里把输出节点数据的步骤改为了判断指针域的逻辑
void inThread(TREE, TREE *, TREE);
void traverse_inThread_by_rchild(TREE);
// 调用此函数时需要传入head
void traverse_inThread_by_rchild(TREE head)
{
printf("中序正向遍历二叉链表:\n");
printf("self %p - lc %10p, lt %u, %c, rt %u, rc %10p\n", head, head->lchild, head->ltag, head->name, head->rtag, head->rchild);
TREE p = head->lchild;
while (p->lchild != head) {
p = p->lchild;
//usleep(100000);
}
while (p) {
printf("self %p - lc %10p, lt %u, %c, rt %u, rc %10p\n", p, p->lchild, p->ltag, p->name, p->rtag, p->rchild);
p = p->rchild;
}
}
void inThread(TREE p, TREE *pre, TREE head)
{
if (! p)
return;
inThread(p->lchild, pre, head);
printf("pre p %p - lc %10p, lt %u, %c, rt %u, rc %10p\n", (*pre), (*pre)->lchild, (*pre)->ltag, (*pre)->name, (*pre)->rtag, (*pre)->rchild);
// 判断自身是否有左孩子，如果没有指向前驱节点
if (! p->lchild) {
p->ltag = thread;
p->lchild = *pre;
}
/*
* 因为遍历(中序)时，路径只走到当前节点，并不知道后继是否有，
* 所以每个节点都只处理自己的前驱和前驱的后继
* head节点rchild在第1个节点处理时指向了第1个节点
*/
if (! (*pre)->rchild) {
(*pre)->rtag = thread;
(*pre)->rchild = p;
}
printf(" inThread p %p - lc %10p, lt %u, %c, rt %u, rc %10p\n", p, p->lchild, p->ltag, p->name, p->rtag, p->rchild);
// 本节点处理完后，更新pre指向自身，作为中序遍历下一个节点的前驱
*pre = p;
// 头指针rchild指向当前节点，最终线索化完成后，头节点的右孩子必定指向中序最后1个节点
head->rchild = p;
inThread(p->rchild, pre, head);
}
void traverse_middle(TREE p)
{
if (p) {
traverse_middle(p->lchild);
printf("%c ", p->name);
traverse_middle(p->rchild);
}
}
void traverse_middle_detail(TREE p)
{
if (p) {
traverse_middle_detail(p->lchild);
printf("self %p - lc %10p, lt %u, %c, rt %u, rc %10p\n", p, p->lchild, p->ltag, p->name, p->rtag, p->rchild);
traverse_middle_detail(p->rchild);
}
}
void traverse(TREE p)
{
if (p) {
printf("%c ", p->name);
traverse(p->lchild);
traverse(p->rchild);
}
}
// 前序初始化树的各节点
void createTree(TREE *p)
{
char c;
scanf("%c", &c);
if (c == '_') {
*p = NULL;
}
else {
*p = (TREE)malloc(sizeof(TREENODE));
(*p)->name = c;
// 无论是否会有左右孩子，都先把tag标识为links
(*p)->ltag = (*p)->rtag = links;
createTree(&(*p)->lchild);
createTree(&(*p)->rchild);
}
}
int main(void)
{
// 头指针，指向线索二叉树的头节点(该节点的lchild指向root)
TREE head = NULL;
TREE tree;
head = (TREE)malloc(sizeof(TREENODE));
head->lchild = head->rchild = NULL;
head->ltag = head->rtag = thread;
// 为了方便确认头节点
head->name = 'H';
TREE pre = head;
createTree(&tree);
// 头节点lchild手动指向tree根节点(rchild已经在线索化完成后指向了中序最后1个节点)
head->lchild = tree;
printf("先序遍历: ");
traverse(tree);
putchar('\n');
printf("中序遍历: ");
traverse_middle(tree);
putchar('\n');
printf("中序遍历(detail):\n");
traverse_middle_detail(tree);
putchar('\n');
// 线索化二叉树(把空闲的lchild, rchild指向各自的前驱和后继)
inThread(tree, &pre, head);
// 使用rchild遍历中序线索化的二叉链表
traverse_inThread_by_rchild(head);
/*
* 目前中序最后1个节点的rchild依然是NULL，但是已经可以实现根据头节点正反向遍历二叉链表
* 如果按照其它教程里的需要把中序尾节点rchild的指向头节点，则中序遍历记住最后1个指针操作一下就可以。。。(如果需要判断空树等情况可以参考网上其它教程)
*/
return 0;
}
output
[root@8be225462e66 c]# gcc thrTree.c && ./a.out
ABC__D__E_F__
先序遍历: A B C D E F
中序遍历: C B D A E F
中序遍历(detail):
self 0x1a83740 - lc (nil), lt 0, C, rt 0, rc (nil)
self 0x1a83710 - lc 0x1a83740, lt 0, B, rt 0, rc 0x1a83770
self 0x1a83770 - lc (nil), lt 0, D, rt 0, rc (nil)
self 0x1a836e0 - lc 0x1a83710, lt 0, A, rt 0, rc 0x1a837a0
self 0x1a837a0 - lc (nil), lt 0, E, rt 0, rc 0x1a837d0
self 0x1a837d0 - lc (nil), lt 0, F, rt 0, rc (nil)
pre p 0x1a832a0 - lc 0x1a836e0, lt 1, H, rt 1, rc (nil)
inThread p 0x1a83740 - lc 0x1a832a0, lt 1, C, rt 0, rc (nil)
pre p 0x1a83740 - lc 0x1a832a0, lt 1, C, rt 0, rc (nil)
inThread p 0x1a83710 - lc 0x1a83740, lt 0, B, rt 0, rc 0x1a83770
pre p 0x1a83710 - lc 0x1a83740, lt 0, B, rt 0, rc 0x1a83770
inThread p 0x1a83770 - lc 0x1a83710, lt 1, D, rt 0, rc (nil)
pre p 0x1a83770 - lc 0x1a83710, lt 1, D, rt 0, rc (nil)
inThread p 0x1a836e0 - lc 0x1a83710, lt 0, A, rt 0, rc 0x1a837a0
pre p 0x1a836e0 - lc 0x1a83710, lt 0, A, rt 0, rc 0x1a837a0
inThread p 0x1a837a0 - lc 0x1a836e0, lt 1, E, rt 0, rc 0x1a837d0
pre p 0x1a837a0 - lc 0x1a836e0, lt 1, E, rt 0, rc 0x1a837d0
inThread p 0x1a837d0 - lc 0x1a837a0, lt 1, F, rt 0, rc (nil)
中序正向遍历二叉链表:
self 0x1a832a0 - lc 0x1a836e0, lt 1, H, rt 1, rc 0x1a837d0
self 0x1a83740 - lc 0x1a832a0, lt 1, C, rt 1, rc 0x1a83710
self 0x1a83710 - lc 0x1a83740, lt 0, B, rt 0, rc 0x1a83770
self 0x1a83770 - lc 0x1a83710, lt 1, D, rt 1, rc 0x1a836e0
self 0x1a836e0 - lc 0x1a83710, lt 0, A, rt 0, rc 0x1a837a0
self 0x1a837a0 - lc 0x1a836e0, lt 1, E, rt 0, rc 0x1a837d0
self 0x1a837d0 - lc 0x1a837a0, lt 1, F, rt 0, rc (nil)
[root@8be225462e66 c]#内容总结
以上是互联网集市为您收集整理的线索二叉树（C语言）全部内容，希望文章能够帮你解决线索二叉树（C语言）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】