【数据结构-树】二叉树的基本操作

1 链式存储的二叉树

1.1 定义

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

1.2 先序遍历

void PreOrder (BiTree T){
    if (T != NULL){
        访问 T 结点;
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

1.3 中序遍历

void InOrder (BiTree T){
    if (T != NULL){
        InOrder(T->lchild);
        访问 T 结点;
        InOrder(T->rchild);
    }
}

1.4 后序遍历

void PostOrder (BiTree T){
    if (T != NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        访问 T 结点;
    }
}

1.5 层次遍历

void LevelOrder (BiTree T){
    Queue Q; // 辅助队列
    BiTree *TNode;
    
    InitQueue(Q);
    EnQueue(Q, T); // 根节点入队
    
    while (!Empty(Q)){
        DeQueue(Q, TNode); // 队头结点出队
        访问 TNode 结点;
        if (TNode->lchild != NULL)
            EnQueue(Q, TNode->lchild); // 左孩子入队
        if (TNode->rchild != NULL)
            EnQueue(Q, TNode->rchild); // 右孩子入队
    }
}

2 顺序存储的二叉树

2.1 树的结点从数组下标 1 开始存储

2.1.1 定义

#define MAX 50

typedef struct{
    int data;
    bool empty; // 记录结点是否为空
} TreeNode;

TreeNode T[MAX+1];

• 初始化：

void InitTree (TreeNode &T){
    int i;
    for (i = 1; i <= MAX+1; i++)
        T[i].empty = true;
}

2.1.2 先序遍历

void PreOrder (TreeNode &T, int i){
    if (!T[i].empty){
        访问 T[i].data;
        
        if (2*i <= MAX)
            PreOrder(T, 2*i);
            
        if (2*i+1 <= MAX)
            PreOrder(T, 2*i+1);
    }
}

2.1.3 中序遍历

void InOrder (TreeNode &T, int i){
    if (!T[i].empty){
        if (2*i <= MAX)
            InOrder(T, 2*i);
            
        访问 T[i].data;
        
        if (2*i+1 <= MAX)
            InOrder(T, 2*i+1);
    }
}

2.1.4 后序遍历

void PostOrder (TreeNode &T, int i){
    if (!T[i].empty){
        if (2*i <= MAX)
            PostOrder(T, 2*i);
            
        if (2*i+1 <= MAX)
            PostOrder(T, 2*i+1);
            
        访问 T[i].data;
    }
}

2.1.5 层次遍历

void LevelOrder (TreeNode &T){
    int i;
    for (i = 1; i <= MAX; i++){
        if (!T[i].empty)
            访问 T[i].data;
    }
}

2.1.6 结点 i 的父结点

int FindFather (int i){
    return i / 2;
}

2.1.7 结点 i 的左孩子

int FindLeftChild (int i){
    return 2 * i;
}

2.1.8 结点 i 的右孩子

int FindRightChild (int i){
    return 2 * i + 1;
}

2.1.9 结点 i 的层数

int FindFloor (int i){
    return log(2, i) + 1; // log 以 2 为底的对数函数
}

2.2 树的结点从数组下标 0 开始存储

2.2.1 定义

#define MAX 50

typedef struct{
    int data;
    bool empty; // 记录结点是否为空
} TreeNode;

TreeNode T[MAX];

• 初始化：

void InitTree (TreeNode &T){
    int i;
    for (i = 0; i < MAX; i++)
        T[i].empty = true;
}

2.2.2 先序遍历

void PreOrder (TreeNode &T, int i){
    if (!T[i].empty){
        访问 T[i].data;
        
        if (2*i+1 < MAX)
            PreOrder(T, 2*i+1);
            
        if (2*i+2 < MAX)
            PreOrder(T, 2*i+2);
    }
}

2.2.3 中序遍历

void InOrder (TreeNode &T, int i){
    if (!T[i].empty){
        if (2*i+1 < MAX)
            InOrder(T, 2*i+1);
            
        访问 T[i].data;
        
        if (2*i+2 < MAX)
            InOrder(T, 2*i+2);
    }
}

2.2.4 后序遍历

void PostOrder (TreeNode &T, int i){
    if (!T[i].empty){
        if (2*i+1 < MAX)
            PostOrder(T, 2*i+1);
            
        if (2*i+2 < MAX)
            PostOrder(T, 2*i+2);
            
        访问 T[i].data;
    }
}

2.2.5 层次遍历

void LevelOrder (TreeNode &T){
    int i;
    for (i = 0; i < MAX; i++){
        if (!T[i].empty)
            访问 T[i].data;
    }
}

2.2.6 结点 i 的父结点

int FindFather (int i){
    return (i - 1) / 2;
}

2.2.7 结点 i 的左孩子

int FindLeftChild (int i){
    return 2 * i + 1;
}

2.2.8 结点 i 的右孩子

int FindRightChild (int i){
    return 2 * i + 2;
}

2.2.9 结点 i 的层数

int FindFloor (int i){
    return log(2, i-1) + 1; // log 以 2 为底的对数函数
}