后序线索二叉树的后序遍历问题求解？

  • Z时代
  • 2024-01-10
  • 分类：IT

对二叉树进行后序线索化，建立后序线索二叉树，然后对其进行后序遍历，写的代码如下：

#include <stdio.h>
#include <malloc.h>
//构建线索链表 
typedef struct ThreadNode {
    int data;
    /*
    ltag = 0， 表示lchild域指结点的左孩子   ltag = 1 表示lchild域指结点的前驱
    rtag = 0   表示rchild域指结点的右孩子， rtag = 1 表示rchild域指结点的后继 
    */
    struct ThreadNode *lchild, *rchild;    //左右孩子指针 
    int ltag, rtag;      //左右线索标志 
}ThreadNode, *ThreadTree;
ThreadTree CreateThrTree(ThreadTree &ThrTree) {
    int e;
    scanf("%d", &e);
    if(e < 0) {
        //输入负数，表示该位置的结点是不存在的，令其为NULL 
        ThrTree = NULL;
        return ThrTree;
    } 
    ThrTree = (ThreadNode *)malloc(sizeof(ThreadNode));
    ThrTree->data = e;
    //从根结点开始， 
    printf("输入结点为%d左子结点的结点值: ",ThrTree->data);
    ThrTree->lchild = CreateThrTree(ThrTree->lchild);
    printf("输入结点为%d右子结点的结点值: ",ThrTree->data);
    ThrTree->rchild = CreateThrTree(ThrTree->rchild);
    return ThrTree;
}
//后序线索化
void PostThread(ThreadTree &ThrTree, ThreadTree &pre) {
    if(ThrTree != NULL) {
        PostThread(ThrTree->lchild, pre);    //递归左孩子线索化
        PostThread(ThrTree->rchild, pre);     //递归右孩子线索化
        if(ThrTree->lchild == NULL) {
            ThrTree->ltag = 1;
            ThrTree->lchild = pre;
        } 
        if(pre != NULL && pre->rchild == NULL) {
            pre->rtag = 1;
            pre->rchild = ThrTree;
        }
        pre = ThrTree;
    } 
}
//建立后序线索二叉树
void CreatePostThread(ThreadTree &ThrTree) {
    ThreadTree pre = NULL;
    if(ThrTree) {
        PostThread(ThrTree, pre);     //对非空二叉树进行线索化 
        //处理遍历的最后一个结点 
        pre->rchild = NULL;
        pre->rtag = 1;
    }
} 
ThreadTree getFirstNode(ThreadTree ThrTree) {
   /*
    while(ThrTree->ltag == 0) {
        ThrTree = ThrTree->lchild;
    }
    while(ThrTree->rtag == 0) {
        ThrTree = ThrTree->rchild;
    }
    */
    //这一段求第一个结点的函数写的也不对，请问该怎么纠正？？
    return ThrTree;
}
ThreadTree getNextNode(ThreadTree ThrTree) {
    if(ThrTree->rtag = 1) {
        return ThrTree->rchild;
    }else {
        //该怎么写 
        //??????
    }
}
void ThrPostOrder(ThreadTree ThrTree) {
    ThreadTree p = getFirstNode(ThrTree);
    /*    
    for(p; p != NULL; p = getNextNode(p)) {
        printf("%3d", p->data);
    }
    */
    for(int i = 0; i < 10; i++) {
        printf("%3d", p->data);
        p = getNextNode(p);
    }
}
int main() {
    ThreadTree ThrTree;
    printf("用先序序列创建二叉树(输入第一个为根结点，以负数表示某结点不存在): \n"); 
    CreateThrTree(ThrTree);
    printf("\n通过后序遍历将该二叉树建立为后序线索二叉树 \n");
    CreatePostThread(ThrTree);
    printf("\n后序线索二叉树建立完成\n"); 
    printf("该后序线索二叉树的后序遍历为: ");
    ThrPostOrder(ThrTree);
}

比如对一颗这样的二叉树：
图片描述

在后序遍历的过程中，首先得到后序的第一个结点3，然后getNextNode函数中，3的rtag为1，后续结点为4，再次执行getNextNode，后续结点为2,2的rtag为0，即2有右孩子，那么需要找到2的父结点的右子树中的后序遍历的第一个结点，然后将其作为2的后序结点，

问题是，怎么去找到2的父结点？然后我写的求子树中的后序遍历的第一个结点的函数也有问题，该怎么纠正？

我想如果把2 的值取出来，然后编写一个函数求某个结点值为2的父节点，可是如果这颗二叉树中有多个值为2的结点，那么怎么取到上图中的那个2结点的父节点呢？
求教，谢谢

回答：

建议遍历用递归写，在你还不是熟悉的时候，递归要简单很多。

void postrav(struct btnode *bt) {
    if(bt!=NULL) {
    postrav(bt->lchild);
    postrav(bt->rchild);
    printf("%d ",bt->d);
    }
}

回答：

摘自维基百科：

线索二叉树(引线二叉树) 的定义如下:

“一个二叉树通过如下的方法“穿起来”：所有应该为空的右孩子指针指向该节点在中序序列中的后继，所有应该为空的左孩子指针指向该节点的中序序列的前驱。”

以上是 后序线索二叉树的后序遍历问题求解？ 的全部内容， 来源链接： utcz.com/p/195190.html

回到顶部