如何用C语言递归方法实现线索化二叉树？

本文共计691个文字，预计阅读时间需要3分钟。

本文以一个实例展示了如何使用C语言递归实现二叉树的线索化。以下是大致的代码内容和相关描述：

代码描述：将二叉树中的空左子节点指向其前驱节点，空右子节点指向其后继节点，实现线索化。

具体代码：

c// 假设二叉树节点定义如下：typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; int leftTag; // 0表示左子节点，1表示前驱节点 int rightTag; // 0表示右子节点，1表示后继节点} TreeNode;

// 线索化二叉树的函数void InThread(TreeNode *root, TreeNode *pre) { if (root !=NULL) { InThread(root->left, pre); if (root->left==NULL) { root->left=pre; root->leftTag=1; } if (pre !=NULL && pre->right==NULL) { pre->right=root; pre->rightTag=1; } pre=root; InThread(root->right, pre); }}

使用方法：

1.创建二叉树节点并建立二叉树。

2.调用`InThread(root, NULL)`函数，其中`root`是二叉树的根节点。

结果：

完成二叉树的线索化，使得每个节点都有线索指向其前驱或后继节点。

本文实例为大家分享了C语言递归实现线索二叉树的具体代码，供大家参考，具体内容如下

描述：将二叉树中结点的空左孩子指针域指向前驱结点，将空的右孩子指针域指向后继结点。

code:

#pragma warning(disable:4996) #include<stdio.h> #include<stdlib.h> typedef struct TreeNode { char data; struct TreeNode *lchild, *rchild; int ltag, rtag; }Tree,*BTree; BTree Build_Tree(void) { BTree T; char ch; scanf("%c", &ch); if (ch == '#') { T = NULL; } else { T = (BTree)malloc(sizeof(Tree)); T->data = ch; T->ltag = 0; T->rtag = 0; T->lchild = Build_Tree(); T->rchild = Build_Tree(); } return T; } //先序线索化 void Pre_Thread(BTree cur, BTree *pre) { if (cur && cur->ltag==0) { printf("%c ", cur->data); if (cur->lchild == NULL) { cur->lchild = *pre; (*pre)->ltag = 1; cur->ltag = 1; } if (cur->rchild == NULL) { cur->rtag = 1; } if (*pre && (*pre)->rtag == 1) { (*pre)->rchild = cur; } *pre = cur; Pre_Thread(cur->lchild, pre); Pre_Thread(cur->rchild, pre); } } //中序线索化 void In_Thread(BTree cur, BTree *pre) { if (cur) { In_Thread(cur->lchild, pre); printf("%c ", cur->data); if (cur->lchild==NULL) { cur->lchild = *pre; cur->ltag = 1; } if (cur->rtag == NULL) { cur->rtag = 1; } if (*pre && (*pre)->rtag == 1) { (*pre)->rchild = cur; } *pre = cur; In_Thread(cur->rchild, pre); } } //后序线索化 void Post_Thread(BTree cur, BTree *pre) { if (cur) { Post_Thread(cur->lchild, pre); Post_Thread(cur->rchild, pre); printf("%c ", cur->data); if (cur->lchild == NULL) { cur->lchild = *pre; cur->ltag = 1; } if (cur->rchild == NULL) { cur->rtag = 1; } if (*pre && (*pre)->rtag == 1) { (*pre)->rchild = cur; } *pre = cur; } } int main(void) { BTree T,p=NULL; T = Build_Tree(); Pre_Thread(T, &p); //In_Thread(T, &p); //Post_Thread(T, &p); return 0; }

跑时分别运行前序、中序、后序线索化。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持自由互联。