数据结构自学Day7-- 二叉树

二叉树：

1、树概念及结构

树是一种非线性的数据结构，用于表示具有层次关系的数据。它是由**结点（Node）和边（Edge）**组成的一种结构。

• 根节点（Root）：树的顶端节点，只有一个。

• 子节点（Child）：某个节点的下一级节点。

• 父节点（Parent）：某个节点的上一级节点。

• 叶子节点（Leaf）：没有子节点的节点。

• 边（Edge）：连接父子节点的线。

• 深度（Depth）：从根节点到某个节点的路径长度。

• 高度（Height）：某个节点到最远叶子节点的路径长度。

• 节点的度：某个单个节点的子节点数。

  树的度：一棵树中所有节点的度的最大值。

• 2. 特点

• 每个节点只能有一个父节点。

• 每个节点可以有多个子节点。

• 树没有环（Cycle）的概念。

           树的结构定义：

                "左孩子，右兄弟的结构体指针定义"，结构体内定义两个指针，一个指针指向它左边第一个孩子，另一个指向它的兄弟，依次类推，整个树的结构体都被定义好了

//树的定义
struct TreeNode{
    int _val;
    TreeNode* _LefeChilds; //指向左边的第一个子节点
    TreeNode* _RightSiblings; //指向右边的兄弟节点

}

• 任何一颗树都可以看作是根和它的子树构成。
• 树的应用：目录，文件目录
• 

2、二叉树概念及结构 

二叉树是每个节点最多有两个子节点的数据结构，分别称为：

• 左子节点（Left Child）

• 右子节点（Right Child）

二叉树是一种特殊的树，满足每个节点的度不超过2。完全二叉树的节点度为1的节点只有0个或者1个

二叉树的常用性质：如下

3、二叉树顺序结构及实现

完全二叉树的顺序存储：假设父亲的下标是i，左孩子的下标是2*i+1；右孩子的下标是2*i+2  ；

假设孩子的下标是i，父亲的下标是：（i-1）/2  

非完全二叉树-->虚构出完全二叉树再进行存储-- >浪费空间

4、二叉树链式结构及实现

🧱 思路：每个节点由一个结构体表示，保存当前节点值 + 左右子树的指针。

总结：二叉树的存储方式

5、堆的概念和实现

堆的概念

堆是一种特殊的完全二叉树结构，它满足以下两个条件：

            结构性质：堆必须是完全二叉树（节点从上到下、从左到右依次填满）。

1. 堆序性质：任意一个节点的值，必须满足与其子节点的某种顺序关系（如下两种）：

 两种堆序性质（定义堆的“大小关系”）：

• 大根堆（Max Heap）：

  • 每个节点的值 ≥ 其子节点的值

  • 根节点是最大值

• 小根堆（Min Heap）：

         每个节点的值 ≤ 其子节点的值

  • 根节点是最小值

堆的代码实现

        这里的难点：增删元素时需要保持大根堆和小根堆的结构，如果删除了根节点，仍然其他元素代替根节点成为新的大根堆或小根堆。

假设我们这里给了一个数组元素排列成完全二叉树时如下：根节点不满足小根堆，但两个子树满足小根堆，此时我们需要进行向下调整

但是实际上我们给你们的数据并不一定满足只有根节点不满足小根堆，两个子树满足小根堆。比如：

1、堆的初始化定义 -->利用向下调整构建小根堆

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include <string.h>

typedef int HeapDataType;

typedef struct Heap
{
    HeapDataType* arr;
    int size;
    int capacity;
}Heap;

void Swap(HeapDataType* p1,HeapDataType* p2){
    HeapDataType* tmp = p1;
    p1 = p2; 
    p2 = tmp;
}

void AdjustDown(HeapDataType* arr,int n,int root){ //向下调整-->实现小根堆
    assert(arr);
    int parent = root;
    int Child  = 2*root+1;
    while (Child<n)//最后一个叶节点是我们循环终止条件。
    {   
        if(Child+1<n && arr[Child]>arr[Child+1]){
            Child++;
        }

        if(arr[Child]>arr[parent]){
            Swap(&arr[root],&arr[Child]);
            parent = Child;
            Child = 2*parent+1;
        }
        else{
            break;
        }
    }
}

Heap* Heap_Init(HeapDataType* arr,size_t n){
    assert(arr);
    Heap* pheap =(Heap*)malloc(n*sizeof(HeapDataType));
    memcpy(pheap->arr,arr,sizeof(HeapDataType)*n);
    // pheap->arr = arr;
    pheap->capacity = n;
    pheap->size = n;

    // 构建堆；大根堆，小根堆；
    int root = ((n-1-1)/2);
    while (root>=0)
    {
        AdjustDown(pheap->arr,pheap->size,root);
        root--;
    }
    
}

好了，本期的内容分享就到这里结束了，谢谢大家的点赞支持！！！👍