建立二叉樹并輸出每個字符所在的層數(shù)。如下圖要求輸出A在第一層 B,C在第二層 D,E在第三層

圖片.png

代碼實現(xiàn)如下：

#include<stdafx.h>
#include<stdio.h>
#include<stdlib.h>

typedef char ElemType;

typedef struct BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
//創(chuàng)建一顆二叉樹，約定用戶遵照前序遍歷的方式輸入數(shù)據(jù)
void CreateBiTree(BiTree *T) {
    char c;
    scanf_s("%c", &c);
    if (' ' == c) 
    {
        *T = NULL;
    }
    else
    {
        *T = (BiTNode *)malloc(sizeof(BiTNode));
        (*T)->data = c;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
}
//訪問二叉樹節(jié)點的具體操作，你想干嘛
void visit(ElemType elem, int level) {
    printf("%c 位于第%d層\n", elem, level);
}
//前序遍歷二叉樹
void PreOrderTraverse(BiTree T, int level) {
    if (T)
    {
        visit(T->data, level);
        PreOrderTraverse(T->lchild, level + 1);
        PreOrderTraverse(T->rchild, level + 1);
    }
}

int main() {
    int level = 1;
    BiTree T = NULL;
    CreateBiTree(&T);
    PreOrderTraverse(T, level);
    getchar();
    getchar();
    return 0;
}

線索二叉樹

圖片.png

-ltag為0時指向該節(jié)點的左孩子，為1時指向該節(jié)點的前驅(qū)
-rtag為0時指向該節(jié)點的右孩子，為1時指向該節(jié)點的后繼

代碼實現(xiàn)

#include<stdafx.h>
#include<stdio.h>
#include<stdlib.h>

typedef char ElemType;
typedef int PointerTag;
//線索存儲標(biāo)志位 
//link（0）:表示指向左右孩子的指針
//Thread(1): 表示指向前驅(qū)后繼的線索
typedef enum {Link, Thread};
typedef struct BiThrNode {
    char data;
    struct BiThrNode *lchild, *rchild;
    PointerTag ltag;
    PointerTag rtag;
}BiThrNode, *BiThrTree;

//全局變量，始終指向剛剛訪問過的節(jié)點
BiThrTree pre;

//創(chuàng)建一顆二叉樹 約定用戶遵照前序遍歷的方式輸入數(shù)據(jù)
void CreateBiThrTree(BiThrTree *T) {
    char c;
    scanf_s("%c", &c);
    if (' ' == c)
    {
        *T = NULL;
    }
    else
    {
        *T = (BiThrNode *)malloc(sizeof(BiThrNode));
        (*T)->data = c;
        (*T)->ltag = Link;
        (*T)->rtag = Link;

        CreateBiThrTree(&(*T)->lchild);
        CreateBiThrTree(&(*T)->rchild);
    }
}

void InThreading(BiThrTree T) {
    if (T)
    {
        InThreading(T->lchild); //遞歸左孩子線索化
        //節(jié)點處理
        if (!T->lchild)    //如果該節(jié)點沒有左孩子，設(shè)置ltag為Thread, 并把lchild指向剛剛訪問的節(jié)點
        {
            T->ltag = Thread;
            T->lchild = pre;
        }
        if (!pre->rchild)
        {
            pre->rtag = Thread;
            pre->rchild = T;
        }
        pre = T;

        InThreading(T->rchild); //遞歸右孩子線索化
    }
}
void InOrderThreading(BiThrTree *p, BiThrTree T) {
    *p = (BiThrTree)malloc(sizeof(BiThrNode));
    (*p)->ltag = Link;
    (*p)->rtag = Thread;
    (*p)->rchild = *p;
    if (!T) {
        (*p)->lchild = *p;
    }
    else
    {
        (*p)->lchild = T;
        pre = *p;
        InThreading(T);
        pre->rchild = *p;
        pre->rtag = Thread;
        (*p)->rchild = pre;
    }
}

void visit(char c) {
    printf("%c", c);
}

//中序遍歷二叉樹 非遞歸
void InOrderTraverse(BiThrTree T) {
    BiThrTree p;
    p = T->lchild;
    while (p != T)
    {
        while (p->ltag == Link)
        {
            p = p->lchild;
        }
        visit(p->data);
        while (p->rtag == Thread && p->rchild != T)
        {
            p = p->rchild;
            visit(p->data);
        }
        p = p->rchild;
    }
}
int main() {
    BiThrTree P, T = NULL;
    CreateBiThrTree(&T);
    InOrderThreading(&P, T);
    printf("中序遍歷結(jié)果為：");
    InOrderTraverse(P);

    getchar();
    getchar();
    return 0;
}