PThreadNode pre; void PreOrder(ThreadTree& T) { if (T == NULL) return; else { visit(T); if (T->ltag == 0) PreOrder(T->lchild); PreOrder(T->rchild); } } void InOrder(ThreadTree& T) { if (T == NULL) return; else { InOrder(T->lchild); visit(T); InOrder(T->rchild); } } void PostOrder(ThreadTree& T) { if (T == NULL) return; else { PostOrder(T->lchild); PostOrder(T->rchild); visit(T); } } void visit(PThreadNode& T) { cout << T->data << " "; if (T->lchild == NULL) { T->lchild = pre; T->ltag = 1; } if (pre != NULL && pre->rchild == NULL) { pre->rchild = T; pre->rtag = 1; } pre = T; } PThreadNode createTreeNode(Elemtype data) { PThreadNode p = new ThreadNode; p->data = data; p->lchild = nullptr; p->rchild = nullptr; p->rtag = 0; p->ltag = 0; return p; }
时间: 2024-01-07 14:02:52 浏览: 60
pre-mid-creattree.zip_pre_pre mid
这段代码实现了将普通二叉树转化为线索二叉树的过程,其中 pre 是一个全局变量,用于记录上一个被访问的节点。具体实现过程如下:
1. PreOrder 函数先访问当前节点,然后分别递归遍历左子树和右子树。
2. InOrder 函数先递归遍历左子树,然后访问当前节点,最后递归遍历右子树。
3. PostOrder 函数先递归遍历左子树和右子树,最后访问当前节点。
4. visit 函数实现了对当前节点的访问,具体包括输出节点的值以及线索化左右子树。如果当前节点的左子树为空,则将其左孩子线索化为 pre;如果 pre 的右孩子为空,则将其右孩子线索化为当前节点。最后将 pre 更新为当前节点,以备下一次访问使用。
5. createTreeNode 函数用于创建新节点,初始化时左右孩子均为空,线索标志位均为 0。
需要注意的是,线索化后的二叉树可以通过线索遍历来实现不需要递归的遍历操作,可以大大提高遍历的效率。
阅读全文