二叉树

#define DEF_MAX_TREE_SIZE 100   // 二叉树的最大结点数
typedef struct                  //
{                               //
    int value;                  //
} TElemType;                    // 二叉树的结点数据类型
                                //
typedef struct                  //
{                               //
    TElemType elem;             //
} SqBiTree[DEF_MAX_TREE_SIZE];  // 顺序存储的二叉树类型
                                //
SqBiTree bt;                    // 二叉树存储变量

typedef struct
{
    int value;
} TElemType;

typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

typedef struct BiTNode
{
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

static int data[] = {1, 2, 3, -1, -1, 4, 5, -1, 6, -1, -1, 7, -1, -1, -1};
static int i = I0;
// 递归创建二叉树
static int create_binary_tree(BiTree* biT)
{
    int iRet = -1;
    if (data[i] == -1)
    {
        // 如果结点数值为-1，则表示不存在。
        biT = NULL;
        i++;
        return iRet;
    }
    // 1. 先为根节点赋值
    *biT = (BiTNode*)malloc(sizeof(BiTNode));
    if (*biT == NULL)
    {
        exit(-1);
        return iRet;
    }
    memset(*biT, 0x00, sizeof(BiTNode));
    (*biT)->data = data[i];
    i++;
    // 2. 递归为左子树赋值
    create_binary_tree(&(*biT)->lchild);
    // 3. 递归为右子树赋值
    create_binary_tree(&(*biT)->rchild);
    return iRet;
}

// 先序遍历
static void pre_order_traverse(BiTree T, Visit_T visit)
{
    if (T != NULL)
    {
        // 1. 根结点不为空，访问根结点。
        visit(T->data);
        // 2. 递归遍历左子树。
        pre_order_traverse(T->lchild, visit);
        // 3. 递归遍历右子树。
        pre_order_traverse(T->rchild, visit);
    }
}

// 中序遍历
static void in_order_traverse(BiTree T, Visit_T visit)
{
    if (T != NULL)
    {
        // 当前结点不为空
        // 1. 中序遍历左子树。
        in_order_traverse(T->lchild, visit);
        // 2. 访问当前结点。
        visit(T->data);
        // 3. 中序遍历右子树。
        in_order_traverse(T->rchild, visit);
    }
}

// 后序遍历
static void post_order_traverse(BiTree T, Visit_T visit)
{
    if (T != NULL)
    {
        // 1. 后序遍历左子树。
        post_order_traverse(T->lchild, visit);
        // 2. 后序遍历左子树。
        post_order_traverse(T->rchild, visit);
        // 3. 访问当前结点。
        visit(T->data);
    }
}

int main()
{
    BiTree biT = NULL;
    create_binary_tree(&biT);
    pre_order_traverse(biT, visit); // 1 2 3 4 5 6 7
    in_order_traverse(biT, visit);  // 3 2 5 6 4 7 1
    post_order_traverse(biT, visit);// 3 6 5 7 4 2 1
}

// 用指针数组模拟栈结构
BiTNode* bitNodePre[100];
int indexPre = 0;
static void pre_order_traverse(BiTree T, Visit_T visit)
{
    BiTNode* p = T;
    while (p != NULL || indexPre > 0)
    {
        if (p != NULL)
        {
            // 1. 访问根节点
            visit(p->data);
            // 2. 将右子树压栈
            if (p->rchild != NULL)
            {
                bitNodePre[indexPre] = p->rchild;
                indexPre++;
            }
            // 2. 当前结点设置为根结点的左子树
            p = p->lchild;
        }
        else
        {
            // 当左子树为为空或左侧到头时，表示当前子树的左子树和根节点都已经访问过，
            // 所以出栈访问右子树。
            indexPre--;
            p = bitNodePre[indexPre];
        }
    }
}

BiTNode* bitNodeIn[100];
int indexIn = 0;
static void in_order_traverse(BiTree T, Visit_T visit)
{
    BiTNode* p = T;
    while (indexIn > 0 || p != NULL)
    {
        if (p != NULL)
        {
            // 1. 向左子树走到头，并入栈。
            bitNodeIn[indexIn] = p;
            indexIn++;
            p = p->lchild;
        }
        else
        {
            // 2. 没有左子树时，出栈。
            indexIn--;
            p = bitNodeIn[indexIn];

            // 3. 访问根节点
            visit(p->data);

            // 4.当前结点指向右子树，下一次循环中开始将右子树入栈
            p = p->rchild;
        }
    }
}

BiTNode* bitNodePost[100];
int indexPost = 0;
static void post_order_traverse(BiTree T, Visit_T visit)
{
    BiTNode* p = T;
    BiTNode* r = NULL;  // 用来记录结点是否访问过。
    while (indexPost > 0 || p != NULL)
    {
        if (p != NULL)
        {
            // 1. 向左子树走到头，并入栈。
            bitNodePost[indexPost] = p;
            indexPost++;
            p = p->lchild;
        }
        else
        {
            // 2. 获取栈顶元素，即为最左侧子树的根，判断是否有右子树。
            p = bitNodePost[indexPost - 1];  // 获取栈顶元素
            if (p->rchild != NULL && p->rchild != r)
            {
                // 3.当前结点更新为右子树的根节点，右子树不为空，则将其压栈。
                p = p->rchild;
                bitNodePost[indexPost] = p;
                indexPost++;
                // 4. 从右子树的左侧结点开始，重新将左侧结点入栈。
                p = p->lchild;
            }
            else
            {
                // 5.没有右子树，则出栈，访问根节点。
                indexPost--;
                p = bitNodePost[indexPost];  // 获取栈顶元素
                visit(p->data);
                // 6. 记录访问过的结点，用以避免右子树访问过并出栈之后，
                // 再次判断是否有右子树时又被重新入栈。
                r = p;
                p = NULL;
            }
        }
    }
}

typedef enum
{
    Link,   // Link==0，表示指针
    Thread  // Thread==1，表示线索
} PointerTag;

typedef struct BiThrNode
{
    int data;
    struct BiThrNode *lchild, *rchild;
    PointerTag LTag, RTag;
} BiThrNode, *BiThrTree;

typedef enum
{
    Link,   // Link==0，表示指针
    Thread  // Thread==1，表示线索
} PointerTag;

typedef struct BiThrNode
{
    int data;
    struct BiThrNode *lchild, *rchild;
    PointerTag LTag, RTag;
} BiThrNode, *BiThrTree;

static int data[] = {1, 2, 3, -1, -1, 4, 5, -1, 6, -1, -1, 7, -1, -1, -1};
int i = 0;
// 递归创建二叉树
static int create_binary_tree(BiThrTree* biThrT)
{
    int iRet = -1;
    if (data[i] == -1)
    {
        // 如果结点数值为-1，则表示不存在。
        biThrT = NULL;
        i++;
        return iRet;
    }
    // 1. 先为根节点赋值
    *biThrT = (BiThrNode*)malloc(sizeof(BiThrNode));
    if (*biThrT == NULL)
    {
        exit(-1);
        return iRet;
    }
    memset(*biThrT, 0x00, sizeof(BiThrNode));
    (*biThrT)->data = data[i];
    i++;
    // 2. 递归为左子树赋值
    create_binary_tree(&(*biThrT)->lchild);
    // 3. 递归为右子树赋值
    create_binary_tree(&(*biThrT)->rchild);
    return iRet;
}

typedef void (*Visit_T)(int data);
static void visit(int data)
{
    printf("%d ", data);
}
// 中序遍历
static void in_order_traverse(BiThrTree T, Visit_T visit)
{
    if (T != NULL)
    {
        // 当前结点不为空
        // 1. 中序遍历左子树。
        in_order_traverse(T->lchild, visit);
        // 2. 访问当前结点。
        visit(T->data);
        // 3. 中序遍历右子树。
        in_order_traverse(T->rchild, visit);
    }
}

// // 中序线索化
static BiThrTree pre = NULL;
static void in_threading(BiThrTree T)
{
    if (T != NULL)
    {
        in_threading(T->lchild);
        // 左子树为空，则左指针为线索，指向前一个结点
        if (T->lchild == NULL)
        {
            T->LTag = Thread;
            T->lchild = pre;
        }

        // 右子树为空，则右子树为线索，指向当前结点
        if (pre->rchild == NULL)
        {
            pre->RTag = Thread;
            pre->rchild = T;
        }
        pre = T;
        in_threading(T->rchild);
    }
}

// 在中序线索二叉链表上进行遍历
static void in_order_traverse_thread(BiThrTree T, Visit_T visit)
{
    BiThrTree p = T->lchild;  // p指向二叉树的根节点

    while (p != T)  // 空树或者遍历结束时p==T
    {
        // 1. 获取最左下结点，为中序遍历的第一个结点
        while (p->LTag == Link)
            p = p->lchild;
        visit(p->data);

        // 2. 右子树为线索并且不是最后一个结点，表示指向有效的后继结点。
        while (p->RTag == Thread && p->rchild != T)
        {
            p = p->rchild;
            visit(p->data);
        }
        p = p->rchild;
    }
}

int main(int argc, char* argv[])
{
    BiThrTree biThrT = NULL;
    create_binary_tree(&biThrT);

    in_order_traverse(biThrT, visit);
    printf("\n");

    // 1. 建立头节点并初始化
    BiThrTree biThrTHead = (BiThrTree)malloc(sizeof(BiThrNode));
    biThrTHead->LTag = Link;
    biThrTHead->lchild = biThrTHead;
    biThrTHead->RTag = Thread;
    biThrTHead->rchild = biThrTHead;

    if (biThrT != NULL)
    {
        // 2. 二叉树不为空，头节点左指针指向二叉树的根节点
        biThrTHead->lchild = biThrT;
        // 3. pre指针始终指向刚刚访问过的结点
        pre = biThrTHead;
        // 4. 中序线索化
        in_threading(biThrT);
        // 5. 最后一个结点的右指针指向头节点
        pre->rchild = biThrTHead;
        pre->RTag = Thread;
        // 6. 头节点的右指针指向最后一个结点，构成双向线索链表
        biThrTHead->rchild = pre;
    }

    in_order_traverse_thread(biThrTHead, visit);
}