知识架构

在这里插入图片描述

相关代码

#include <iostream>
using namespace std;

/**
 * 1. 二叉树的存储结构
 */

//1.1 顺序存储
#define MaxSize 100
struct TreeNode {
    int value[MaxSize];
    bool isEmpty;
};


//1.2 链式存储
typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
}BiTNode, *BiNode;


/**
 * 2. 二叉树的遍历
 */

//2.1 先序遍历：根左右

void PreOrder(BiNode T){
    if (T != NULL){
        cout << T->data << endl; // 访问根节点
        PreOrder(T->lchild); //遍历左子树
        PreOrder(T->rchild); //遍历右子树
    }
}

//2.2 中序遍历
void MidOrder(BiNode T){
    if (T != NULL){
        MidOrder(T->lchild); //遍历左子树
        cout << T->data << endl; // 访问根节点
        MidOrder(T->rchild); //遍历右子树

    }
}

//2.2 后序遍历
void PostOrder(BiNode T){
    if (T != NULL){
        PostOrder(T->lchild); //遍历左子树
        PostOrder(T->rchild); //遍历右子树
        cout << T->data << endl; // 访问根节点
    }
}


//2.3 求树的深度
int treeDepth(BiNode T){
    if (T == NULL){
        return 0;
    } else {
        int l = treeDepth(T->lchild);
        int r = treeDepth(T->rchild);
        return l>r ? l+1:r+1;
    }
}

//3. 线索二叉树

typedef struct ThreadNode{
    int data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;
}ThreadNode, *ThreadTree;

//辅助全局变量，用于查找结点p的前驱
ThreadNode *pre = NULL;//指向当前结点的前驱

//3.1 中序线索二叉树
void visit(ThreadTree q) {
    if (q->lchild == NULL){
        //左孩子为空，建立前驱索引
        q->lchild = pre;
        q->ltag = 1;
    }
    if (pre != NULL && pre->rchild == NULL){
        //前一个结点右孩子为空，指向当前结点（后继）
        pre->rchild = q;
        pre->rtag = 1;
    }
    pre =  q;
}

//！！！上面完成后，需要对最后一个结点进行处理，即pre结点，判断pre->rchild 是否为 NULL，是-》设置pre->rtag=1;

void InThread(ThreadTree T){
    if (T != NULL){
        InThread(T->lchild); //遍历左子树
        visit(T); // 访问根节点
        InThread(T->rchild); //遍历右子树
    }
}

//3.2 先序线索二叉树
void PreThread(ThreadTree T){
    visit(T);
    if (T->ltag != 1){
        //左孩子不是一个线索时
        PreThread(T->lchild);
    }

    PreThread(T->rchild);
}