【数据结构】二叉树(初阶)

1.树的概念及结构

1.1树的概念

树是一种非线性的数据结构，是由n个有限结点组成的一个具有层次关系的集合。像一颗倒着的树。 有一个特殊的节点，称为根结点，根结点灭有前驱结点。 除根结点外，其余结点被分成M(M>0)个互不相交的集合，其中每一个集合又是一颗结构与树类似的子树，每棵子树有且只有一个前驱，可以有0个或多个后继结点。 因此，树的递归定义的。(任何一棵树都分为根和子树，子树又可以被同样划分)

注意：树形结构中，子树之间不能有交集，否则就不是树形结构

1.2树的相关概念

节点的度：一个节点含有的子树的个数就称为该节点的度；如图A的度为6 叶节点或终端机节点：度为0的节点称为叶节点；如上图：B，C 非终端节点：度不为0的节点 双亲结点或父节点：含有子节点的节点称为该子节点的父节点；如A是B的父节点 孩子节点或子节点：一个节点含有的子树的根的节点 兄弟节点：具有相同父节点的节点称为兄弟节点；如B，C 树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度是6 节点的层次：从根开始定义起，根为第一层，根的子节点为第二层，以此类推 树的高度或深度：树中节点的最大层次；如上图：树的高度为4 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图；H，I互为堂兄弟节点 节点的祖先：从根到节点所经分支上的所有节点；如上图：A是所有节点的祖先 子孙：以某节点的根的子树中任一节点都称为该节点的子孙；如上图：所有节点都是A的子孙 森林：由m(m>0)棵互不相交的树的集合称为森林

1.3树的表示

孩子兄弟表示法(左孩子右兄弟表示法)：给两个指针，第一个孩子节点，和指向其下一个兄弟的节点。

typedef int DataType;
typedef struct Node
{
  struct Node* firstChild;      //第一个孩子节点
  struct Node* pNextBrother;    //指向下一个兄弟的节点
  DataType data;               //节点中的数据
};

1.4树在实际中的应用

表示文件系统的目录树结构：

2.二叉树的概念及结构

2.1概念

一颗二叉树的节点是一个有限集合，该集合： 1.或者为空 2.由一根节点加上两棵别称为左子树和右子树的二叉树组成

从上图中可以看出： 1.二叉树不存在度大于2的节点 2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树 注意：对于任意二叉树都是由以下几种情况复合而成

2.2特殊的二叉树

满二叉树：每一层的节点数都达到最大值，除了叶子节点的每一个节点都由两个节点，且叶子节点都在同一层。 完全二叉树：是效率很高的数据结构。对于节点数为N的完全二叉树就是满二叉树的从1到N个节点一一对应的数，如下图。

2.3二叉树的性质

1.若规定根节点的层数为1，则一颗非空二叉树的第i层上最多有2^(i-1)个节点. 2.若规定根节点的层数为1，则深度为h的二叉树的最大节点数是2^h - 1. 3.队任何一棵为叉树，如果度为0叶节点个数为N0，度为2的分支节点个数为N2，则有N0=N2+1. 4.若国定根节点的层数为1.具有N个节点的满二叉树的深度，h=log(n+1)(ps：其中log是以2为底的对数)

2.4二叉树的存储结构

二叉树一般有两种存储结构

2.4.1.顺序存储

顺序结构存储就是用数组来存储，一般使用数组只适合表示完全二叉树，若不是完全二叉树就会有空间浪费。二叉树顺序存储在物理上是一个数组，在逻辑上是一棵二叉树。

可以用下标计算父子间的关系：
leftchild = parent *2 + 1

rightchild = parent *2 + 2

parent = (child -1)/2

2.4.2.链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链。

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pParent; // 指向当前节点的双亲
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
}

3.二叉树的顺序结构及实现

3.1二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

3.2堆的概念及结构

给一个数据集合K = {k0，k1，k2，...，kn}，把他所有数据元素按照顺序存储方式储存在一个以为数组中，并满足：Ki <= K(2i+1)，Ki <= K(2i+2)（Ki >= K(2i+1),Ki >= K(2i+1)）i=0,1,2...,则称为小堆(或大堆)。将根节点大的堆叫做大堆，根节点小的叫做小堆。 堆的性质： 1.堆中某个节点的值总是不大于或不小于其父节点的值。 2.堆总是一棵完全二叉树。

意义：1.堆排序 --O(N*logN) 2.topK(选出最大的前K个)

3.3堆的实现

堆的接口：

typedef int HPDataType;
typedef struct Heap
{
    HPDataType* a;
    int size;
    int capacity;
}HP;
​
//初始化堆
void HeapInit(HP* php);
//销毁堆空间
void HeapDestroy(HP* php);
//向堆尾插入数据，并且调整堆中数据，保持堆的性质
void HeapPush(HP* php, HPDataType x);
//删除堆顶的数据，并调整堆中的数据，保持堆的性质
void HeapPop(HP* php);
//判断堆是否为空
bool HeapEmpty(HP* php);
//计算堆的大小
int HeapSize(HP* php);
//返回堆顶的数据
HPDataType HeapTop(HP* php);

3.3.1堆的初始化

思路：将数组置为空，size和capacity置为0即可

void HeapInit(HP* php)
{
    assert(php);
    php->a = NULL;
    php->size = php->capacity = 0;
}

3.3.2堆的销毁

思路：当我们退出程序时，需要释放堆中增加开辟过的内存，以免造成内存泄漏。

void HeapDestroy(HP* php)
{
    assert(php);
    //释放数组内存
    free(php->a);
    php->a = NULL;
    php->size = php->capacity = 0;
}

3.3.3堆的插入

思路：因为堆在物理上是一个顺序表，在逻辑上是一个完全二叉树，我们插入时采用的思想是将数据插在顺序表的尾部，为了保证堆的性质我们还需要应用到向上调整算法，每插入一个数都要用一边确保每个数的插入都能使堆保持他的性质(大堆，小堆)，这里我们实现的是小堆的插入。 首先我们插入下面这个测试数组：

int array[] = {27,15,19,18,28,34,65,49,25,37};

向上调整算法：将孩子节点与父节点进行比较，这里是小堆，所以当孩子节点比父节点小的时候就交换，直到出现该子节点大于父节点或者孩子节点走到根的位置才停止。

代码实现：

//交换数据
void Swap(HPDataType* val1, HPDataType* val2)
{
    HPDataType tmp = 0;
    tmp = *val1;
    *val1 = *val2;
    *val2 = tmp;
}
​
//向上调整堆
void AdjustUp(HPDataType* a, int child)
{
    //算出父节点
    int parent = (child - 1) / 2;
    while (child>0)
    {
        //判断大小
        if (a[parent] > a[child])
        {
            //交换节点
            Swap(&a[parent], &a[child]);
            //更新迭代条件
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}
​
void HeapPush(HP* php, HPDataType x)
{
    //判断堆是否为空或者容量是否已满
    assert(php);
    if (php->size == php->capacity)
    {
        //扩容
        int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
        HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
        if (tmp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        php->a = tmp;
        php->capacity = newcapacity;
    }
    //放入数据
    php->a[php->size] = x;
    php->size++;
    //调整堆
    AdjustUp(php->a, php->size-1);
}

3.3.4堆的删除

思路：对于删除堆最后一个数据并没有什么实际意义并且很简单，这里讲的删除是删除堆顶的数据。当我们删除后还需要保持堆的性质，当我们删除尾上的数据时堆的性质并没有发生变化，所以我们将堆顶的数据和最后一个数据交换位置，然后删除末尾的位置，将堆顶的数据采用向下调整算法进行调整，就可以很好的保证堆的性质。需要注意的是，我们从栈顶向下调整时，必须保证左子树和右子树都是堆才能保证调整完后整体是一个堆。 图像如下：

代码实现：

//交换数据
void Swap(HPDataType* val1, HPDataType* val2)
{
    HPDataType tmp = 0;
    tmp = *val1;
    *val1 = *val2;
    *val2 = tmp;
}
​
//向下调整堆
void AdjustDwon(HPDataType* a, int size, int parent)
{
    //算出初始孩子节点的位置
    int child = parent * 2 + 1;
    while (child < size)
    {
        //选出左右孩子中小/大的
        if (child + 1 < size && a[child] < a[child + 1])
            ++child;
        //比较父节点和子节点
        if (a[parent] < a[child])
        {
            //交换
            Swap(&a[parent], &a[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
​
//删除堆顶的数据，并调整堆中的数据，保持堆的性质
void HeapPop(HP* php)
{
    assert(php);
    //判断堆是否为空
    assert(!HeapEmpty(php));
​
    //不为空时删除堆顶的数据
    //1.首先将根节点和树最后一个节点交换
    Swap(&php->a[0], &php->a[php->size - 1]);
​
    //2.删除最后一个数(也就是交换后堆顶的数据)
    php->size--;
​
    //3.向下调整堆
    AdjustDwon(php->a, php->size, 0);
}

3.3.5判断堆是否为空

思路：当记录数据个数的size为0时堆就为空 代码实现：

bool HeapEmpty(HP* php)
{
    assert(php);
    //通过判断size是否为0判断堆是否为空
    return php->size == 0;
}

3.3.5计算堆的大小

思路：返回记录数据个数的size 代码实现：

int HeapSize(HP* php)
{
    assert(php);
    return php->size;
}

3.3.6找堆顶元素

思路：因为是逻辑结构中的堆顶对应的也就是物理结构中数组的第一个元素，所以返回array[0]即可。 代码实现：

HPDataType HeapTop(HP* php)
{
    assert(php);
    //判断堆是否为空
    assert(!HeapEmpty(php));
    return php->a[0];
}

3.4堆的应用

3.4.1堆排序

堆排序就是利用堆的思想来进行排序，分为两个步骤： 1.建堆：建堆有两种方式，向上调整和向下调整，向上调整时间复杂度是O(NlogN),向下调整是O(N)，所以我们用效率高的向下调整算法。 升序 -- 建大堆降序 -- 建小堆* 2.排序：假如我们想要排成一个升序，首先我们建好了大堆，堆顶的元素为最大的，但是后面的是乱序，我们只有一个最大值，我们可以将起和最后一个数交换，将最大值放在最后，就排好了一个，然后向下调整堆，再将需要处理的的长度减1，目的是隔离处理好的值，再重复上述步骤，直到全部排成升序。

代码实现：

//向下调整堆
void AdjustDwon(HPDataType* a, int size, int parent)
{
    //算出初始孩子节点的位置
    int child = parent * 2 + 1;
    while (child < size)
    {
        //选出左右孩子中小/大的
        if (child + 1 < size && a[child] < a[child + 1])
            ++child;
        //比较父节点和子节点
        if (a[parent] < a[child])
        {
            //交换
            Swap(&a[parent], &a[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
​
// 对数组进行堆排序
//升序 -- 建大堆
void HeapSort(HPDataType* a, int n)
{
    建堆方式1：O(N*logN)
    //for (int i = 0; i < n; i++)
    //{
    //  AdjustUp(a, i);
    //}
    
    //建堆方式2：O(N)效率高
    //n-1表示最后一个元素的位置 ((n-1)-1)/2是父节点的位置
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        //向下调整堆
        AdjustDwon(a, n, i);
    }
    //排序 -- 升序
    int end = n - 1;//最后一个元素
    while (end>0)
    {
        //将堆顶元素交换到堆尾
        Swap(&a[0], &a[end]);
        //向下调整堆
        AdjustDwon(a, end, 0);
        end--;
    }
}

3.4.2TopK

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大 。 说到TopK首先想到的堆排序，但是当数据量特别大的时候效率会非常低。内存可能也会存不下。 最佳解决方法就是用堆来解决： 1.用数据集合中前K个元素来建堆： 求前K个最大的数 -- 建小堆 求前K个最小的数 -- 建大堆 2.遍历一遍剩余的数，来与堆顶的数比较，求前K个最大的就当数比堆顶的数据大时就替换，然后调整堆，求前K个最小的就当比堆顶小的时候替换，当遍历完过后堆里的数据就是前K个最大或最小的元素。 如下给10000个数据，产生随机值都小于10000，随机指定10个数据大于10000，前K个最大的数就是这十个数，找到这10个数 代码：

//求前K个最大的
//建小堆
void PrintTopK(int* a, int n, int k)
{
    // 1. 建堆--用a中前k个元素建堆
    for (int i = (k - 1 - 1) / 2; i > 0; i--)
    {
        AdjustDwon(a, k, i);
    }
    // 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
    for (int i = k; i < n; i++)
    {
        if (a[0] < a[i])
        {
            Swap(&a[0], &a[i]);
            AdjustDwon(a, k, 0);
        }
    }
}
​
void TestTopk()
{
    int n = 10000;
    int* a = (int*)malloc(sizeof(int) * n);
    srand(time(0));
    for (int i = 0; i < n; ++i)
    {
        a[i] = rand() % 1000000;
    }
    a[5] = 1000000 + 1;
    a[1231] = 1000000 + 2;
    a[531] = 1000000 + 3;
    a[5121] = 1000000 + 4;
    a[115] = 1000000 + 5;
    a[2335] = 1000000 + 6;
    a[9999] = 1000000 + 7;
    a[76] = 1000000 + 8;
    a[423] = 1000000 + 9;
    a[3144] = 1000000 + 10;
    PrintTopK(a, n, 10);
}

4.二叉树链式结构的实现

4.1二叉树的创建

为了更快的上手学习，我们这里手敲一个二叉树。但并不是二叉树的创建方式，只是为了我们更好的理解下面的内容。

typedef int BTDataType;
typedef struct BinaryTreeNode
{
    BTDataType _data;
    struct BinaryTreeNode* _left;
    struct BinaryTreeNode* _right;
}BTNode;
BTNode* CreatBinaryTree()
{
    BTNode* node1 = BuyNode(1);
    BTNode* node2 = BuyNode(2);
    BTNode* node3 = BuyNode(3);
    BTNode* node4 = BuyNode(4);
    BTNode* node5 = BuyNode(5);
    BTNode* node6 = BuyNode(6);
    node1->_left = node2;
    node1->_right = node4;
    node2->_left = node3;
    node4->_left = node5;
    node4->_right = node6;
    return node1;
}

4.2二叉树的遍历

所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。当学好了遍历方式才能更好的操作二叉树。

4.2.1前中后序遍历

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。 当我们用递归来实现前序遍历时代码如下：void PreOrder(BTNode* root){ if (root == NULL) return NULL; printf("%d ", root->data);//根 PreOrder(root->left);//左子树 PreOrder(root->right);//右子树}
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中。 void InOrder(BTNode* root){ if (root == NULL) return NULL; InOrder(root->left);//左子树 printf("%d ", root->data);//根 InOrder(root->right);//右子树}
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。 void PostOrder(BTNode* root){ if (root == NULL) return NULL; PostOrder(root->left);//左子树 PostOrder(root->right);//右子树 printf("%d ", root->data);//根}

4.2.3层序遍历

这里需要用到队列的思想，父节点出队列将子节点带入队列，首先将根结点进到队列，当根出来后带入第二层，第二层第一个结点带入子节点，利用了队列的先进先出。需要注意一点，我们进队列不能只将值传进去，因为带入子节点时我们需要有子节点的地址，但是我们将整个结构体传进去空间占用比较大，所以我们传入结构体的指针图画如下：

void LevelOrder(BTNode* root)
{
    Queue qe;
    QueueInit(&qe);
    //先传根结点
    if (QueueEmpty(&qe))
    {
        QueuePush(&qe,root);
    }
    //队列不为空时进行遍历
    while (!QueueEmpty(&qe))
    {
        BTNode* front = QueueFront(&qe);
        printf("%d ", front->data);
        //父节点出队列
        QueuePop(&qe);
        //子节点进队列
        if(front->left)
            QueuePush(&qe, front->left);
        if(front->right)
            QueuePush(&qe, front->right);
    }
    printf("\n");
    QueueDestroy(&qe);
}

4.4二叉树的判断和销毁

4.4.1判断完全二叉树

可以利用层序遍历，如果是完全二叉树，当出现一个空的时候后面全是空，空和非空会很明显的分隔开，如果不是完全二叉树，则在非空中会穿插空。

bool BinaryTreeComplete(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    //先传根结点
    if (QueueEmpty(&q))
    {
        QueuePush(&q, root);
    }
    //队列不为空时进行遍历
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        //父节点出队列
        QueuePop(&q);
        //子节点进队列
        if (front)
        {
            QueuePush(&q, front->left);
            QueuePush(&q, front->right);
        }
        else
        {
            //遇见空后跳出循环
            break;
        }
    }
    //1.后面全是空，则是完全二叉树
    //2.后面出现非空，则不是完全二叉树
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        if (front != NULL)
        {
            QueueDestroy(&q);
            return false;
        }
    }
    QueueDestroy(&q);
    return true;
}

4.4.2销毁

当我们需要销毁二叉树的时候需要注意的是，如果我们想从根结点开始销毁的话销毁了就找不到左孩子和有孩子。所以我们采用的方式是利用后序遍历销毁先将左右孩子销毁掉再销毁根结点。

//二叉树的销毁
void TreeDestroy(BTNode* root)
{
    if (root == NULL)
        return ;
    //先销毁左孩子结点
    TreeDestroy(root->left);
    //再销毁右孩子结点
    TreeDestroy(root->right);
    //销毁根结点
    free(root);
}