当前位置：首页 > article >正文

（二叉树）

article 2025/1/22 6:55:46

我们今天就开始引进一个新的数据结构了：我们所熟知的：二叉树；

但是我们在引进二叉树之前我们先了解一下树；

树

树的概念和结构：

树是⼀种⾮线性的数据结构，它是由 n （ n>=0 ）个有限结点组成⼀个具有层次关系的集合。把它叫做树是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。

有⼀个特殊的结点，称为根结点，根结点没有前驱结点。

除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1 、 T2 、 …… 、 Tm ，其中每⼀个集合 Ti(1 <= i <= m) ⼜是⼀棵结构与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱，可以有 0 个或多个后继。因此，树是递归定义的。

我们的树，我们的单个结点可以当作是一个树，加入我们的某一个结点是没有后代的，就是一个单个的结点，这也可以算作是一个树；

这就是我们的一个树，我们可以看到，我们的树的结点的分布是没有什么规律的，每个结点后面可以有很多个后继的节点，但是只有一个前驱结点，但是除了根结点是没有前驱结点的，我们的最后面的叶子结点也是没有后继结点的；

在我们的树形结构里面，我们的子树之间是不能有交集的，否则这就不是一个树形的结构了；这就是一个图了

看这几个就不是树的结构，树的结构他的子树是不能有交集的，这是图；也是一种数据结构，但是在这里我们不进行讲解；

当我们有一个树的结构的时候；这个二叉树就有了下面的名字；

因为我们的树的后面可以有很多个结点；没有对他进行限制，这就不是一个好的数据结构，我们在这里再次引入一个新的数据结构：二叉树

二叉树

概念和结构：

在树形结构中，我们最常⽤的就是⼆叉树，⼀棵⼆叉树是结点的⼀个有限集合，该集合由⼀个根结点加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空

我们观察上面的图片，我们就可以知道的结论：

1.二叉树的度是不大于2的，最多是二，度其实就是这个结点拥有的孩子的个数，而树的度就是我们的节点里面的度最大的结点的度就是我们的树的度；

2.二叉树是有左右子树之分的，这样的次序是不能颠倒的，二叉树是一个有序树；

3.任意的二叉树都是由以下的结点组成的

这些东西相互复合，最终就可以构成一个二叉树；

这个就是我们的现实生活里面可以见到的二叉树；是非常标准的

我们再来引入一些特殊的二叉树：

1.满二叉树；

⼀个⼆叉树，如果每⼀个层的结点数都达到最⼤值，则这个⼆叉树就是满⼆叉树。也就是说，如果⼀个⼆叉树的层数为 K ，且结点总数是2^k-1个，则它就是满⼆叉树。

这就是满二叉树的结点的运算方法；我们知道了满二叉树的高度k，就可以得出他的总的结点的个数；2^k-1；

把每一层的结点的个数拉满，这就是满的二叉树；

2.完全二叉树

完全二叉树就是由满二叉树演变来的，满二叉树其实就是特殊的完全二叉树；

完全二叉树除了最后一层，其他层的结点的个数都是满的，但是我们的最后一层，节点个数不一定是满的，它可以是满的，比如满二叉树，也可以不是满的，还是完全二叉树；

我们来看这个，这就是一个完全的二叉树，也是一个满二叉树。

我们再来看这个，这就不是一个完全的二叉树；

完全的二叉树，他的节点一定是集中的位于左边，如果不是慢的二叉树，他的最后一层的结点一定是按顺序从左往右的进行排列的。

这就不是一个完全的二叉树，完全二叉树的话，除了最后一层结点，其他的层的结点一定都是满的。

我们的完全二叉树的最后一层的结点一定是从左往右的进行排列的。

我们来说一下二叉树的性质：

我们再说一下二叉树的存储结构

顺序结构和链式结构；

顺序结构的存储就是使用数组来进行存储；但是这种存储方式一般只适用于完全二叉树，因为使用完全二叉树不会有内存空间的浪费；

现实中我们通常把堆（⼀种⼆叉树）使⽤顺序结构的数组来存储，需要注意的是这⾥的堆和操作系统虚拟进程地址空间中的堆是两回事，⼀个是数据结构，⼀个是操作系统中管理内存的⼀块区域分段。

那我们就来实现一下堆二叉树

堆又分为两种；1.大根堆。2.小根堆

大根堆：根节点最大的堆，我们称作大根堆。

小根堆：根节点最小的堆，这就是小根堆。（要注意：我们的树的每一个子树的根节点都是最大或者最小的）。

顺序结构的存储使用的是完全的二叉树；这样可以减少空间的浪费；使用顺序结构来进行存储的时候，我们使用的完全二叉树就是堆二叉树

堆的性质：

1.堆二叉树里面的结点的值，总是不大于或者不小于其父节点的值；

2.堆二叉树是一颗完全二叉树；

我们再来看一下完全二叉树的性质：

1.当我们知道某一个结点的下标的时候，我们可以推断出其父节点的下标。(i-1)/2; 可以求出父节点下标；

2.当我们知道父节点的下标的时候，我们可以求出孩子结点的下标；但是我们求出来的孩子节点的下标是不能越界的，我们设置的结点的个数为n个，我们的数组最后一个结点所对应的下标为n-1，所以，我们求出来的孩子结点所对应的下标为2i+1<n，只有在这个范围里面才是有效的；

我们的右孩子的求法就是左孩子的下标加一；得到的就是右孩子的下标；而且我们的右孩子下标也是<n的，这是有效的；

我们的堆二叉树在逻辑结构上就是二叉树，但是在存储的结构上的底层是数组；

当我们往堆里面插入数据的时候，我们一开始是一个空的堆，也就是一个空的数组；

那我们使用代码来实现一下堆：

///堆二叉树的初始化
void HPInit(HP* php)
{
   assert(php);
   php->arr = NULL;
   php->capacity = php->size = 0;
}

//堆的销毁
void HPDestory(HP* php)
{
   assert(php);
   if (php->arr)
       free(php->arr);
   php->arr = NULL;
   php->capacity = php->size = 0;

}

void swap(int* x, int* y)
{
   int tmp = *x;
   *x = *y;
   *y = tmp;
}

//向上调整（入堆）
void Adjustup(HPDataType* arr, int child)
{
//我们要进行向上调整，我们可以根据孩子把父亲求出来
   int parent = (child - 1) / 2;
   //向上调整既可以是大堆，也可以是小堆；

   while (child > 0)
   {
       //如果要求是小堆的时候，我们看谁小，我们就把谁往上放，
       //所以小堆：<
       //如果孩子比父亲小我们就交换
       //大堆：>
       //如果孩子比父亲大我们就交换
       if (arr[child] < arr[parent])
       {
           swap(&arr[child], &arr[parent]);
       }
       else
       {
           break;
       }
       child = parent;
       parent = (child - 1) / 2;
   }
}

void Print(HP* php)
{
   for (int i = 0; i < php->size; i++)
   {
       printf("%d ", php->arr[i]);
   }
   printf("\n");
}

//入堆往堆里面插入数据
void HPPush(HP* php, HPDataType x)
{
   assert(php);//先进行一下断言，这个必须是一个有效的堆的数据结构；
   //判断空间是否足够；不够的话，我们就进行增容；
   if (php->capacity == php->size)
   {
       int Newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
       //当我们的arr是空指针的时候，我们也不需要担心，这个时候realloc的作用和malloc就是一样的；
       HPDataType* tmp = (HPDataType*)realloc(php->arr, Newcapacity * sizeof(HPDataType));
       if (tmp == NULL)
       {
           perror("realloc");
           exit(1);
       }
       php->arr = tmp;
       php->capacity = Newcapacity;
   }
   //然后我们直接把数据插入
   /*php->arr[php->size++] = x;*/
   //这个时候size还不能加加，因为我们还要使用size这个下标
   php->arr[php->size] = x;

   //然后向上进行调整；
   Adjustup(php->arr, php->size);
   php->size++;
}

//判空
//判断二叉树里面有没有数据
bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0;
}

//向下调整法（出堆）
void AdjustDown(HPDataType* arr, int parent, int n)
{
int child = 2 * parent + 1;//左孩子；

   while (child < n)
   {
       //大堆：<
       //大堆的话我们找到大孩子
       //小堆：>
       //小堆我们就找小孩子
       if (child + 1 < n && arr[child] < arr[child+1])
       {
           child++;
       }

       //大堆 >
       //我们找到大的放上去
       //小堆 <
       //我们找到小的放上去
       if (arr[child] > arr[parent])
       {
           swap(&arr[child], &arr[parent]);
           parent = child;
           child = 2 * parent + 1;
       }
       else
       {
           break;
       }
   }
}

//出堆 -- 出堆指的是出堆顶数据；
void HPPop(HP* php)
{
//我们把栈顶的数据给他出出去

   //出堆的话，堆里面一定是不能为空的
   assert(!HPEmpty(php));
   //我们的出堆的方式是先让第一个数据和最后一个数据进行交换；
   //然后让有效的数据减一，然后进行排序
   swap(&php->arr[0], &php->arr[php->size - 1]);
   //这时候我们的堆顶的数据放到了最后一个位置
   php->size--;
   //然后我们这里使用向下调整法；从堆顶往下进行调整
   AdjustDown(php->arr, 0, php->size);
   //我们要把数组传过去，还有我们的parent的下标0；然后还有有效的数据个数；
}

//取堆顶数据
HPDataType HPTop(HP* php)
{
   assert(!HPEmpty(php));
   //我们要取堆顶元素，那么我们的堆就不能为空堆二叉树；
   return php->arr[0];
}

查看全文

http://www.kler.cn/a/513146.html