树结构_二叉树

树结构 - 二叉树的结构及其操作

结构 TNode - PtrToTNode - BinTree

1. 结点数据Data
2. 当前结点的左子树
3. 当前结点的右子树

创建

1. 动态申请树TNode空间
2. 初始化树的左、右孩子为NULL

先序遍历 (根 - 左 - 右)

1. 如果树不为空
2. 访问当前树的数据
3. 一路递归向左子树走
4. 再转身树的右子树递归

中序遍历 (左 - 根 - 右)

1. 如果树不为空
2. 一路递归向左子树走
3. 访问当前树的数据
4. 再转身树的右子树递归

后序遍历 (左 - 右 - 根)

1. 如果树不为空
2. 一路递归向左子树走
3. 再转身树的右子树递归
4. 访问当前树的数据

非递归遍历 - 堆栈实现中序遍历

1. 创建堆栈S
2. 树T不为空，或栈S不为空，就一直循环
3. 遍历左子树，并将沿途结点压入栈
4. 将最深层的左树结点从堆栈中弹出T，并访问
5. 转向访问该结点T的右子树

非递归遍历 - 层序遍历

1. 判空BT
2. 创建空队列
3. 将根结点加到队列中
4. 遍历队列Q至空
5. 从队列中取出一个元素结点，访问打印
6. 如果结点左子树不为空，将结点的左子树添加到队列中
7. 如果结点右子树不为空，将结点的右子树添加到队列中

求所有叶子结点（基于先序遍历）

1. 如果二叉树不为空
2. 判断是否有子孩子,无则是叶子结点
3. 递归向左子树
4. 递归向右子树

求二叉树的高度

1. 判空NULL
2. 递归求左子树的高度HL
3. 递归求右子树的高度HR
4. 返回较大者MaxH，+1指包含当前层

根据层序遍历生成二叉树

1. 创建队列Q
2. 读入根结点数据
3. 动态申请空结点BT，赋值给结点并初始化左右子树为NULL
4. 将根结点BT加入队列
5. 如果队列不为空，遍历队列
6. Q出列得到T
7. 读取左子树数据
8. 如果输入的数据不为空，则插入T的左子树，并加入队列Q
9. 读取右子树数据
10. 如果输入的数据不为空，则插入T的右子树，并加入队列Q

#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>
#define NoInfo 0

typedef int ElementType;
typedef struct TNode *PtrToTNode;
typedef PtrToTNode BinTree;

// 树的链表表示 5(遍历)+2(叶子和高度)+1(创建)
struct TNode {
    // 1.结点数据Data
    ElementType Data;
    // 2.当前结点的左子树
    PtrToTNode Left;
    // 3.当前结点的右子树
    PtrToTNode Right;
};

// 是否为空树
bool isEmpty(BinTree BT) {
   return BT == NULL ? true : false;
}

void Traversal(BinTree BT) {
   // 二叉遍历，有先序遍历、中序遍历、后序遍历、堆栈遍历、层次遍历
}

// 创建
BinTree CreatBinTree() {
   BinTree BT;
   // 1.动态申请树TNode空间
   BT = (BinTree) malloc(sizeof(struct TNode));
   // 2.初始化树的左、右孩子为NULL
   BT->Left = NULL;
   BT->Right = NULL;
   return BT;
}

// 中序遍历 左-根-右
void InOrderTraversal(BinTree BT) {
    // 1.如果树不为空
   if (BT) {
       // 2.一路递归向左子树走
       InOrderTraversal(BT->Left);
       // 3.访问当前树的数据
       printf("%d", BT->Data);
       // 4.再转身树的右子树递归
       InOrderTraversal(BT->Right);
   }
}

//先序遍历 根-左-右
void PreOrderTraversal(BinTree BT) {
    // 1.如果树不为空
   if (BT) {
       // 2.访问当前树的数据
       printf("%d", BT->Data);
       // 3.一路递归向左子树走
       PreOrderTraversal(BT->Left);
       // 4.再转身树的右子树递归
       PreOrderTraversal(BT->Right);
   }
}

//后序遍历，左-右-根
void PostOrderTraversal(BinTree BT) {
    // 1.如果树不为空
   if (BT) {
       // 2.一路递归向左子树走
       PostOrderTraversal(BT->Left);
       // 3.再转身树的右子树递归
       PostOrderTraversal(BT->Right);
       // 4.访问当前树的数据
       printf("%d", BT->Data);
   }
}

//非递归遍历 - 堆栈实现中序遍历
void InOrderTraversalStack(BinTree BT) {
   BinTree  T;
   // 1.创建堆栈
   Stack S = CreateStack();
   T = BT;
   // 2.树T不为空，或栈S不为空，就一直循环
   while (T || !IsEmpty(S)){
       // 3.遍历左子树，并将沿途结点压入栈
       while (T){
           Push(S, T);
           T = T->Left;
       }
       // 4.将最深层的左树结点从堆栈中弹出T，并访问
       T = Pop(S);
       printf("%d", T->Data);
       // 5.转向访问该结点T的右子树
       T = T->Right;
   }
}

//非递归遍历 - 层序遍历
void LevelOrderTraversal(BinTree BT) {
   Queue Q;
   BinTree  T;
   // 1.判空BT
   if (!BT){
       return;
   }
   // 2.创建空队列
   Q = CreateQueue();
   // 3.将根结点加到队列中
   AddQ(Q, BT);
   // 4.遍历队列Q至空
   while (!IsEmpty(Q)){
       // 5.从队列中取出一个元素结点，访问打印
       T = Delete(Q);
       printf("%d", T->Data);
       // 6.如果结点左子树不为空，将结点的左子树添加到队列中
       if (T->Left) {
           AddQ(Q, T->Left);
       }
       // 7.如果结点右子树不为空，将结点的右子树添加到队列中
       if (T->Right){
           AddQ(Q, T->Right);
       }
   }
}

//求所有叶子结点（基于先序遍历）
void PreOrderPrintLeaves(BinTree BT) {
    // 1.如果二叉树不为空
    if (BT) {
        // 2.判断是否有子孩子,无则是叶子结点
        if (!BT->Left && !BT->Right) {
            printf("%d", BT->Data);
        }
        // 3.递归向左子树
        PreOrderPrintLeaves(BT->Left);
        // 4.递归向右子树
        PreOrderPrintLeaves(BT->Right);
    }
}

//求二叉树的高度
int GetHeight(BinTree BT) {
   int HL, HR, MaxH;
   // 1.判空NULL
   if (BT) {
       // 2.递归求左子树的高度HL
       HL = GetHeight(BT->Left);
       // 3.递归求右子树的高度HR
       HR = GetHeight(BT->Right);
       // 4.返回较大者MaxH，+1指包含当前层
       MaxH = HL > HR ? HL : HR;
       return MaxH + 1;
   }
   // 空树返回0
   return 0;
}

//根据层序遍历生成二叉树
BinTree CreateBinTree() {
    BinTree BT, T;
    ElementType Data;
    // 1.创建队列Q
   Queue Q = CreateQueue();
   // 2.读入根结点数据
   scanf("%d", &Data);
   if (Data != NoInfo) {
       // 3.动态申请空结点BT，赋值给结点并初始化左右子树为NULL
       BT = (BinTree) malloc(sizeof(struct TNode));
       BT->Data = Data;
       BT->Left = BT->Right = NULL;
       // 4.将根结点BT加入队列
       AddQ(Q, BT);
   } else {
       return NULL;
   }
   // 5.如果队列不为空，遍历队列
   while (!IsEmpty(Q)){
       // 6.Q出列得到T
       T = DeleteQ(Q);
       // 7.读取左子树数据
       scanf("%d", &Data);
       if (Data != NoInfo){
           // 8.如果输入的数据不为空，则插入T的左子树，并加入队列Q
           T->Left = (BinTree)malloc(sizeof(struct TNode));
           T->Left->Data = Data;
           T->Left->Left = T->Left->Right = NULL;
           AddQ(Q, T->Left);
       } else{
           T->Left = NULL;
       }
       // 9.读取右子树数据
       scanf("%d", &Data);
       if (Data != NoInfo){
           // 10.如果输入的数据不为空，则插入T的右子树，并加入队列Q
           T->Right = (BinTree)malloc(sizeof(struct TNode));
           T->Right->Data = Data;
           T->Right->Left = T->Right->Right = NULL;
           AddQ(Q, T->Right);
       } else{
           T->Right = NULL;
       }
   }
    return BT;
}