树 - 简书

写在最前：
树作为数据结构接触的第一个非线性结构，其实也是与线性结构密不可分——都要靠链表实现，学计算机之前就总是听过什么树啊二叉树啊，百闻不如一见，学习起来吧

一、树定义：

专业定义：
1.有且只有一个称为根的节点
2.有若干个互不相交的子树，这些子树本身也是一棵树
通俗定义：
1.树是由节点和边（指针）组成
2.每个节点只有一个父节点，但可以有多个子节点
3.但有一个节点例外，该节点没有父节点，此节点称为根节点

有几个名词：

①节点②父节点③子节点④子孙⑤堂兄弟
⑥深度：从根节点到最底层节点的层数称之为深度，根节点是第一层
⑦叶子节点（叶子不能劈叉）：没有子节点的节点
⑧非终端节点：实际就是非叶子节点
（根节点可以是叶子节点（打光棍）也可以是非叶子节点）
⑨度：子节点的个数称为度（一棵树就看最大的）

二叉树的性质

二、树的分类

一般树：任意一个节点的子节点的个数都不受限制
二叉树（有序树）：任意一个节点的子节点的个数最多两个，且子节点的位置不可更改（左右孩子不能互换）
1.一般二叉树
2.满二叉树：在不增加树的层数的前提下，无法再多添加一个节点的二叉树
3.完全二叉树：从右侧开始删除最后一层的节点
（满二叉树是特殊的完全二叉树，一个也不删）
森林：n个互不相交的树的集合

三、树的存储

顺序存储（数组）一般不用

按满二叉树的结点层次编号，依次存放二叉树中的数据元素
特点：
结点间关系蕴含在其存储位置中（查找某个节点的父节点和子节点很快）
浪费空间，适于存满二叉树和完全二叉树

顺序存储

链式存储（链表）

一个节点包含三个内容：值、左孩子指针、右孩子指针

typedef struct TreeNode *BinTree;
struct TreeNode{
int Data;//值
BinTree Left;//左孩子和右孩子
BinTree Right;
};

链式存储

//树的建立（可改进）
BinTree CreatBinTree(){
    BinTree BT;
    BT =  (BinTree)malloc(sizeof(struct TreeNode));
    BT->Data = 1;
    BT->Left = Insert(2);
    BT->Right = Insert(3);
    return BT;
}
//少不了的插入函数
BinTree Insert(int Data){
    BinTree BT;
    BT =  (BinTree)malloc(sizeof(struct TreeNode));
    BT->Data = Data;
    BT->Left = NULL;
    BT->Right = NULL;
    return BT;
}

四、树的遍历

三种递归遍历的本质区别就是什么时候访问根节点

先序递归（PreOrder）

先访问根节点
再先序访问左子树
再先序访问右子树

void PreOrderTraversal(BinTree BT){
    if(BT){
        printf("%d",BT->Data);  // 打印根 
        PreOrderTraversal(BT->Left);  // 进入左子树 
        PreOrderTraversal(BT->Right);  // 进入右子树 
    }
}

先序非递归

所有非递归算法实现的基本思路都是：使用堆栈
中序遍历的注释书写较多

//和中序非递归的区别就只有printf的位置
void PreOrderTraversal(BinTree BT){
    BinTree T = BT;
    Stack S = CreateStack();  // 创建并初始化堆栈 S
    while(T || !IsEmpty(S)){  // 当树不为空或堆栈不空 
        while(T){     
            Push(S,T); // 压栈，第一次遇到该结点 
            printf("%d",T->Data);  // 访问结点，here！！！不一样
            T = T->Left; // 遍历左子树 
        }
        if(!IsEmpty(S)){ // 当堆栈不空 
            T = Pop(S); // 出栈，第二次遇到该结点 
            T = T->Right; // 访问右结点 
        }
    } 
}

中序递归（InOrder）

中序遍历左子树
再访问根节点
再中序遍历右子树

void InOrderTraversal(BinTree BT){
    if(BT){
        InOrderTraversal(BT->Left);  // 进入左子树 
        printf("%d",BT->Data);  // 打印根 
        InOrderTraversal(BT->Right);  // 进入右子树 
    } 
}

中序非递归

①遇到一个结点，就把它压栈，并去遍历它的左子树
②当左子树遍历结束后，从栈顶弹出这个节点并访问它
③然后按其右指针再去中序遍历该节点的右子树

void InOrderTraversal(BinTree BT){
    BinTree T=BT;
    Stack S=CreateStack();//创建并初始化堆栈 
    while(T||!IsEmpty(S)){//当树不为空或堆栈不空 
        while(T){//一直向左并将沿途节点压入栈 
            Push(S,T);//压栈 
            T=T->Left;//遍历左子树 ，也是压入的过程
        }
//此时左子树的节点已经全部压入，准备打印
        if(!IsEmpty(S)){//当堆栈不空 
            T=Pop(S);//出栈一位 
            printf("%d",T->Data);//访问 
            T=T->Right;//访问右子树 
        }
    }
}

后序递归PostOrder

先后序遍历左子树
再后序遍历右子树
再访问根节点

void PostOrderTraversal(BinTree BT){
    if(BT){
        PostOrderTraversal(BT->Left);  // 进入左子树 
        PostOrderTraversal(BT->Right);  // 进入右子树 
        printf("%d",BT->Data);  // 打印根 
    } 
}

后序非递归

void PostOrderTraversal(BinTree BT){
    BinTree T = BT;
    Stack S = CreateStack();  // 创建并初始化堆栈 S
    vector<BinTree> v;
    Push(S,T);  //放入根节点 
    while(!IsEmpty(S)){  // 当树不为空或堆栈不空 
        T = Pop(S);//弹出 
        v.push_back(T);//把弹出来的放入数组 
        if(T->Left)     //遍历左右孩子 
            Push(S,T->Left);
        if(T->Right)
            Push(S,T->Right);
    }
    reverse(v.begin(),v.end());  // 逆转，因为是正着放入 
    for(int i=0;i<v.size();i++)
        printf("%d",v[i]->Data);
}

层序遍历（用队列）LevelOrder

一层一层的下来
首先将根节点入队，然后开始执行循环：
从队列中取出一个元素
访问该元素所指的节点
若左右孩子非空，将左右孩子的指针顺序入队（类似于BFS）

void LevelOrderTraversal(BinTree BT){
    queue<BinTree> q;
    BinTree T;
    if(!BT)//如果是空树直接返回
        return;
    q.push(BT);  // BT 入队 
    while(!q.empty()){
        T = q.front();  // 访问队首元素 
        q.pop();  // 出队
        printf("%d",T->Data);
        if(T->Left)//有左孩子，入队
            q.push(T->Left);
        if(T->Right)//有右孩子，入队
            q.push(T->Right);
    }
}

树