JZTXT

二叉树链表

发布时间 2023-06-04 02:31:32作者: 刘倩_网安2211

二叉树链表

标签（空格分隔）： DS 二叉树 链式存储

1.二叉树的结构

1.1二叉链表结点结构

typedef struct BiTNode
{
    char data;
    struct BiTNode* lson,* rson;
}BiTNode,* BiTree;//BiTNode为结点结构，BiTree为结点指针

1.2二叉树的二叉线索存储结构

//Link==0,表示指向左右孩子的指针
//Thread==1,表示指向前驱或后继的线索
typedef enum {Link,Thread} PointerTag;

typedef struct BiThrNode
{
    char data;
    struct BiThrNode* lson,* rson;
    PointerTag LTag;
    PointerTag RTag;
    //LTag\RTag==Link==0,表示lson\rson指向左\右孩子；
    //LTag\RTag==Thread==1,表示lson\rson指向前驱\后继的线索；
}BiThrNode,* BiThrTree;

2.先序遍历

2.1二叉树的前序遍历

思路：遍历顺序：中左右
1.每棵树先输出其根的值，再递归其左子树同时输出根的值，再递归其右子树同时输出根的值
即边递归左子树边输出节点信息，再边递归右子树边输出节点信息
2.如果遍历到的结点为空，则return，返回上一层次继续递归，直到结束

void PreOrder(BiTree &T）
{
    if(T==NULL)
        return;
    
    printf("%c ",T->data);
    
    PreOrder(T->lson);
    PreOrder(T->rson);
}

2.2前序建立二叉树

思路：
1.按先序遍历输入结点信息，若指针指向空，则输入‘#’，并返回上一层次

void CreateBiTree(BiTree &T)
{
    char ch;//接受结点信息，若为'#',即空，
    scanf("%c",&ch);
    if(ch=='#')
        T=NULL;
    else
        {
            //申请结点空间
            T=(BiTree)malloc(sizeof(BiTNode));
            if(!T)
            exit(OVERFLOW);
            //赋值
            T->data=ch;
            CreateBiTree(&T->lson);
            CreateBiTree(&T->rson);
        }
}

3.中序遍历

3.1.二叉树的中序遍历

思路：遍历顺序：左中右
1.即先递归左子树，递归结束后输出节点信息回到上一层次，再边递归右子树边输出节点信息
2.如果遍历到的结点为空，则return，返回上一层次继续递归，直到结束

void InOrder(BiTree &T)
{
    if(T==NULL)
        return;
    
    InOrder(T->lson);
    printf("%c ",T->data);
    InOrder(T->rson);
}

3.2中序创建二叉树

void CreateBiTree(BiTree &T)
{
    char ch;//接受结点信息，若为'#',即空，
    scanf("%c",&ch);
    if(ch=='#')
        T=NULL;
    else
        {
            //申请结点空间
            T=(BiTree)malloc(sizeof(BiTNode));
            if(!T)
            exit(OVERFLOW);
            //赋值
            CreateBiTree(&T->lson);
            T->data=ch;
            CreateBiTree(&T->rson);
        }
}

3.3二叉树中序线索化

思路：线索化就是将空指针利用起来，指向其前驱和后继，左前驱，右后继；
1.中序遍历中打印结点的操作变成线索化
2.由于遍历到p时，指针pre指向刚刚遍历过的p的前驱，但不知道p的后驱，所以每个结点可以直接前驱线索化，但只能对此结点的前驱后继线索化。
    2.1p前驱线索化：如果某节点p无左孩子，即lson==NULL,则将lson指向前驱，并使LTag==Thread作为标记
    2.2p的pre后驱线索化：如果pre无右孩子，即rson==NULL,则rson指向后继p,并使RTag==Thread作为标记

BiThrTree pre;//全局变量，指针pre始终指向刚刚访问过的结点
void InThreading(BiThrTree p)
{
    if(p==NULL)
        return;

        //递归左子树
        InThreading(p->lson);
        
        //将打印结点的操作变成线索化
        if(p->lson==NULL)//p没有左孩子,前驱线索化
        {
            p->LTag=Thread;
            p->lson=pre;
        }
        
        if(pre->rson==NULL)//pre没有右孩子，后驱线索化
        {
            pre->RTag==Thread;
            pre->rson=p;
        }
        
        pre=p;//保持pre指向p的前驱
        
        //递归右子树
        InThreading(p->rson);
}

3.4中序遍历二叉线索树

P218

4.后序遍历

4.1.二叉树的后序遍历

思路：遍历顺序：左右中
1.即先递归左子树，递归结束后再递归右子树，直到右子树也递归结束，则输出节点信息回到上一层次，
2.如果遍历到的结点为空，则return，返回上一层次继续递归，直到结束

void PostBiTree(BiTree &T)
{
 if(T==NULL)
        return;
    
    InOrder(T->lson);
    InOrder(T->rson);
    printf("%c ",T->data);
}

4.2后序创建二叉树

void CreateBiTree(BiTree &T)
{
    char ch;//接受结点信息，若为'#',即空，
    scanf("%c",&ch);
    if(ch=='#')
        T=NULL;
    else
        {
            //申请结点空间
            T=(BiTree)malloc(sizeof(BiTNode));
            if(!T)
            exit(OVERFLOW);
            //赋值
            CreateBiTree(&T->lson);
            CreateBiTree(&T->rson);
            T->data=ch;
        }
}