设已建立的二叉树的三叉链表存储结构中，结点的数据域孩子域一填好内容，现要求编写算法给双亲域填上指向

Question

设已建立的二叉树的三叉链表存储结构中，结点的数据域孩子域一填好内容，现要求编写算法给双亲域填上指向其双亲的指针

Answer 1

// 创建二叉树,输入先序扩展序列:
// ABC##DE#G##F###
// 先序遍历序列: A B C D E G F
// 中序遍历序列: C B E G D F A
// 后序遍历序列: C G E F D B A
// 先序遍历(显示双亲):
// A(NUL) B(NUL) C(NUL) D(NUL) E(NUL) G(NUL) F(NUL)
//
// 增加双亲后,先序遍历(显示双亲):
// A(NUL) B(A) C(B) D(B) E(D) G(E) F(D)
//
//        A
//       /
//      B
//     /  \
//    C    D
//        /  \
//       E    F
//        \
//         G
//
#include<stdio.h>
#include<stdlib.h>
typedef struct Node  //二叉树的"三叉链表"存储结构
{
    char data;
    struct Node *lchild; //左孩子指针
    struct Node *rchild; //右孩子指针
    struct Node *parent; //双亲指针
}Bitree;

//用 先序扩展序列+递归 创建二叉树
void CreateBiTree(Bitree **bt)
{
    char ch;
    scanf("%c",&ch); //输入数据
    if(ch=='#')      //'#'是空节点
    {
       *bt=NULL;
    }
    else
    {
        *bt=(Bitree *)malloc(sizeof(Bitree));
        (*bt)->data=ch;
        (*bt)->parent=NULL; //用于测试
        CreateBiTree(&((*bt)->lchild));
        CreateBiTree(&((*bt)->rchild));
    }
}

//增加双亲指针(用先序遍历,递归法)
void createParent(Bitree *ptr,Bitree *parent)
{
    if(ptr!=NULL)
    {
        ptr->parent = parent;
        createParent(ptr->lchild,ptr);
        createParent(ptr->rchild,ptr);
    }
}

void preOrderWithParent(Bitree *ptr) //先序遍历(显示双亲)
{
    if(ptr!=NULL)
    {
        if(ptr->parent == NULL)
        {
           printf("%c(NUL) ",ptr->data);
        }
        else
        {
           printf("%c(%c) ",ptr->data,ptr->parent->data);
        }

        preOrderWithParent(ptr->lchild);
        preOrderWithParent(ptr->rchild);
    }
}

void preOrder(Bitree *ptr) //先序遍历
{
    if(ptr!=NULL)
    {
        printf("%c ",ptr->data);
        preOrder(ptr->lchild);
        preOrder(ptr->rchild);
    }
}

void inOrder(Bitree *ptr) //中序遍历
{
    if(ptr!=NULL)
    {
        inOrder(ptr->lchild);
        printf("%c ",ptr->data);
        inOrder(ptr->rchild);
    }
}

void postOrder(Bitree *ptr) //后序遍历
{
    if(ptr!=NULL)
    {
        postOrder(ptr->lchild);
        postOrder(ptr->rchild);
        printf("%c ",ptr->data);
    }
}

int main()
{
    Bitree *root;

    //创建二叉树,输入先序扩展序列
    CreateBiTree(&root);

    printf("先序遍历序列: ");
    preOrder(root);
    printf("\n中序遍历序列: ");
    inOrder(root);
    printf("\n后序遍历序列: ");
    postOrder(root);
    printf("\n先序遍历(显示双亲): ");
    preOrderWithParent(root);

    createParent(root,NULL);
    printf("\n\n增加双亲后,先序遍历(显示双亲): ");
    preOrderWithParent(root);

    printf("\n");
    return 0;
}