| 线索二叉树的建立和遍历（附源码）（前/中/后序）「数据结构算法精讲」 | 您所在的位置：网站首页 › 二叉树的创建与遍历代码 › 线索二叉树的建立和遍历（附源码）（前/中/后序）「数据结构算法精讲」 |
线索二叉树的建立和遍历（附源码）（前/中/后序）「数据结构算法精讲」
|
前言：二叉树的非递归遍历算法（点此学习算法）避免了系统栈的调用，提高了执行效率。而线索二叉树可以将用户栈也省去，把二叉树的遍历过程线性化，进一步提高效率（但代价就是会使用较多的的存储空间）。 完整代码见文章末尾 普通的二叉链表，n个结点的二叉树会有n+1个空链域，为了把这些空链域有效的利用起来，线索二叉树出现了。 线索二叉树的结点构造如下： lchildltagdatartagrchild左孩子左标识域数据域右孩子右标识域 typedef struct TBTNode // 定义线索二叉树的节点 { char data; // 节点数据类型 int ltag, rtag; // 线索标记 struct TBTNode *lchild; // 左孩子 struct TBTNode *rchild; // 右孩子 }TBTNode; 中序线索化二叉树由于二叉树的（前序/中序/后序）线索化都极为相似，所以本篇着重讲解中序线索化。 二叉树线索化的过程中，会把树中的空指针利用起来作为寻找当前结点前驱或后继的线索，但这样会出现一个问题，即线索和树中原有的指向孩子结点的指针无法区分。所以在线索二叉树的结构中额外添加了 ltag 和 rtag 两个标识域，用来区分他们的孩子是否存在，具体含义如下： 如果 ltag=0，表示 lchild 为指针，指向结点的左孩子；如果 ltag=1，表示 lchild 为线索，指向结点的直接前驱。如果 rtag=0，表示 rchild 为指针，指向结点的右孩子；如果 rtag=1，表示 rchild 为线索，指向结点的直接后继。分析：使用二叉树中序递归算法框架，在遍历过程中连接上合适的线索即可 规则： 在某一时刻 p 指针指向当前正在访问的结点，pre指向 p 的前驱结点；p 的左线索如果存在，则让其指向 pre；pre 的右线索如果存在则让其指向 p，因为 p 是 pre 的后继结点；当 p 将要离开一个访问过的结点的时候，pre 指向 p，当 p 来到一个新的结点时，pre 显然指向的是此时 p 所指结点的前驱结点。例子： ……当整颗二叉树遍历完的时候，线索化也就完成了。代码如下： void InThread(TBTNode *p, TBTNode *&pre) { if(p != NULL) { InThread(p->lchild, pre); // 递归，左子树线索化 if(p->lchild == NULL) { // 建立当前节点的前驱线索 p->lchild = pre; p->ltag = 1; } if(pre != NULL && pre->rchild == NULL) // pre != NULL 排除第一个结点前驱为空的情况 { // 建立当前节点的后继线索 pre->rchild = p; pre->rtag = 1; } pre = p; p = p->rchild; InThread(p, pre); // 递归，右子树线索化 } } void createInThread(TBTNode *root) { TBTNode *pre = NULL; if(root != NULL) { InThread(root, pre); pre->rchild = NULL; // 非空二叉树，线索化 pre->rtag = 1; // 后处理中序最后一个结点 } } 中序遍历线索二叉树因为二叉树已经被中序线索化，所以我们遍历链表，并按照中序（左->根->右）的方式访问结点即可。 优先访问根左子树，找到第一个访问的结点，也就位于树最左下的结点（不一定是叶子结点）；找到结点，若当前结点存在右子树，优先访问右子树的左子树（中序遍历的要求）；若当前结点不存在右子树，直接访问当前结点的后继结点（线索化时添加的后继线索）；重复2、3。由此可见，第一个访问的结点，和后序访问的其他结点的访问方式有所不同，所以需要将逻辑分开，容易得到代码： TBTNode *First(TBTNode *p) // 中序序列下第一个结点访问算法 { while (p->ltag == 0) p = p->lchild; // 最左下结点（不一定是叶子结点） return p; } TBTNode *Next(TBTNode *p) // 中序序列下后继结点访问算法 { if(p->rtag == 0) return First(p->rchild); else return p->rchild; // rtage == 1，直接返回后序线索 } void Inorder(TBTNode *root) { for(TBTNode *p = First(root); p != NULL; p = Next(p)) cout if(p->lchild == NULL) { // 建立当前节点的前驱线索 p->lchild = pre; p->ltag = 1; } if(pre != NULL && pre->rchild == NULL) // pre != NULL 排除第一个结点前驱为空的情况 { // 建立当前节点的后继线索 pre->rchild = p; pre->rtag = 1; } pre = p; // 注意，这里在递归入口处有条件限制，左、右指针不是线索才能继续递归 if(p->ltag == 0) preThread(p->lchild, pre); // 递归，左子树线索化 if(p->rtag == 0) preThread(p->rchild, pre); // 递归，右子树线索化 } } void createPreThread(TBTNode *root) // 前序线索化二叉树 { TBTNode *pre = NULL; if(root != NULL) { preThread(root, pre); pre->rchild = NULL; // 非空二叉树，线索化 pre->rtag = 1; // 后处理中序最后一个结点 } } 前序遍历线索二叉树 void preorder(TBTNode *root) { if(root != NULL) { TBTNode *p = root; while (p != NULL) { while (p->ltag == 0) // 左指针不是线索，则边访问边左移 { cout lchild; // 左移，访问左子树 } cout rchild; // 此时p左孩子不存在，则右指针若非空，则不论是否为线索都指向其后继 } } } 后序线索化二叉树后序线索化代码和中序线索化代码极为相似，最大的区别就是把连接线索的代码提到了两递归入口后边，这也符合后序递归遍历的框架。 void postThread(TBTNode *p, TBTNode *&pre) // 后序线索化二叉树子函数 { if(p != NULL) { preThread(p->lchild, pre); // 递归，左子树线索化 preThread(p->rchild, pre); // 递归，右子树线索化 if(p->lchild == NULL) { // 建立当前节点的前驱线索 p->lchild = pre; p->ltag = 1; } if(pre != NULL && pre->rchild == NULL) // pre != NULL 排除第一个结点前驱为空的情况 { // 建立当前节点的后继线索 pre->rchild = p; pre->rtag = 1; } pre = p; } } 后序遍历线索二叉树考试几乎会不考到后序线索遍历，故省略。 日后有需要的话再来补充。 最后附上源码，希望能对你有所帮助～ #include #include using namespace std; typedef struct TBTNode // 定义线索二叉树的结点 { char data; // 结点数据类型 int ltag, rtag; // 线索标记 struct TBTNode *lchild; // 左孩子 struct TBTNode *rchild; // 右孩子 }TBTNode; TBTNode *createBinaryTree() // 前序递归创建二叉树 { TBTNode *p; char ch; cin >> ch; if(ch == '#') { p = NULL; } else { p = (TBTNode*)malloc(sizeof(TBTNode)); p->data = ch; p->lchild = createBinaryTree(); p->rchild = createBinaryTree(); } return p; } void InThread(TBTNode *p, TBTNode *&pre) // 中序线索化二叉树子函数 { if(p != NULL) { InThread(p->lchild, pre); // 递归，左子树线索化 if(p->lchild == NULL) { // 建立当前节点的前驱线索 p->lchild = pre; p->ltag = 1; } if(pre != NULL && pre->rchild == NULL) // pre != NULL 排除第一个结点前驱为空的情况 { // 建立当前节点的后继线索 pre->rchild = p; pre->rtag = 1; } pre = p; p = p->rchild; InThread(p, pre); // 递归，右子树线索化 } } void createInThread(TBTNode *root) // 中序线索化二叉树 { TBTNode *pre = NULL; if(root != NULL) { InThread(root, pre); pre->rchild = NULL; // 非空二叉树，线索化 pre->rtag = 1; // 后处理中序最后一个结点 } } TBTNode *First(TBTNode *p) // 中序遍历线索二叉树-第一个结点访问算法 { while (p->ltag == 0) p = p->lchild; // 最左下结点（不一定是叶子结点） return p; } TBTNode *Next(TBTNode *p) // 中序遍历线索二叉树-后继结点访问算法 { if(p->rtag == 0) return First(p->rchild); else return p->rchild; // rtage == 1，直接返回后序线索 } void Inorder(TBTNode *root) // 中序遍历线索二叉树 { for(TBTNode *p = First(root); p != NULL; p = Next(p)) cout if(p->lchild == NULL) { // 建立当前节点的前驱线索 p->lchild = pre; p->ltag = 1; } if(pre != NULL && pre->rchild == NULL) // pre != NULL 排除第一个结点前驱为空的情况 { // 建立当前节点的后继线索 pre->rchild = p; pre->rtag = 1; } pre = p; // 注意，这里在递归入口处有条件限制，左、右指针不是线索才能继续递归 if(p->ltag == 0) preThread(p->lchild, pre); // 递归，左子树线索化 if(p->rtag == 0) preThread(p->rchild, pre); // 递归，右子树线索化 } } void createPreThread(TBTNode *root) // 前序线索化二叉树 { TBTNode *pre = NULL; if(root != NULL) { preThread(root, pre); pre->rchild = NULL; // 非空二叉树，线索化 pre->rtag = 1; // 后处理中序最后一个结点 } } void preorder(TBTNode *root) // 前序遍历线索二叉树 { if(root != NULL) { TBTNode *p = root; while (p != NULL) { while (p->ltag == 0) // 左指针不是线索，则边访问边左移 { cout lchild; // 左移，访问左子树 } cout rchild; // 此时p左孩子不存在，则右指针若非空，则不论是否为线索都指向其后继 } } } void postThread(TBTNode *p, TBTNode *&pre) // 后序线索化二叉树子函数 { if(p != NULL) { preThread(p->lchild, pre); // 递归，左子树线索化 preThread(p->rchild, pre); // 递归，右子树线索化 if(p->lchild == NULL) { // 建立当前节点的前驱线索 p->lchild = pre; p->ltag = 1; } if(pre != NULL && pre->rchild == NULL) // pre != NULL 排除第一个结点前驱为空的情况 { // 建立当前节点的后继线索 pre->rchild = p; pre->rtag = 1; } pre = p; } } int main() { cout |
【本文地址】
公司简介
联系我们