二叉树和堆排序

国内教程定义: 二叉树. 如果每层中的节点数达到最大值，则二叉树就是完整的二叉树. 也就是说二叉排序树 堆，如果二叉树的层数为K，则第i层的节点数为: 2（i-1），而节点的总数为（2k）-1，则这是一棵完整的二叉树.

国内二叉树

国外（国际）定义: 如果二叉树的节点是叶节点或具有两个子节点，则此类树是完整的二叉树.

外国二叉树（但不符合国内定义）

确定完整的二叉树

完整的二叉树: 叶节点只能出现在最低层和最低层中，最低层的节点集中在该层的最左侧位置. （我的理解是完整的二叉树: 它是完整的二叉树. 最底层的最右边的一些节点）

完整的二叉树定义

完整的二叉树

如果二叉树的深度为h，则除第h层以外的所有其他层（1〜h-1）的节点数均达到最大值，并且第h层的所有节点数均为不断地集中在最左边，这是一个完整的二叉树.

完整的二叉树源自[full binary tree]. 对于深度为K且节点数为n的二叉树，当且仅当其每个节点在深度为K的完整二叉树中对应于从1到n的的数字时，才称为完整二叉树.

在二叉树中，最高层的节点的度数最多可以小于2，并且最低层上的节点集中在该层的最左位置，这样二叉树就成为完整的二叉树.

二进制排序树，也称为二进制搜索树，也称为二进制搜索树.

定义:

二进制排序树是具有以下属性的空树或二进制树:

（1）如果左子树不为空，则左子树上所有节点的值都小于或等于其根节点的值;

（2）如果右子树不为空，则右子树上所有节点的值都大于或等于其根节点的值;

（3）左右子树也是二进制排序树；

查找:

二叉树

如果根节点的关键字值等于搜索到的关键字，则成功.

否则，如果它小于根节点的键值，则递归检查左子树.

如果它大于根节点的键值，则递归检查右子树.

如树为空，则搜索失败.

1. 链接列表

链接列表中的每个节点都包含两个指针leftchild和rightchild，分别指向左侧和右侧子树

2. 数组

利用平衡二叉树的平衡特性，使用数组存储完整的二叉树. a [n]的左右子节点分别是a [2n + 1]和a [2n + 2]

数组的索引从0开始，二叉树从1开始.

将要插入的节点添加到数组的末尾，这是平衡二叉树的最后一个叶节点. 从最后一个子树的根节点a（n / 2）开始，调整所有子树以保持大顶部堆的特征（a [n]> = a [2n + 1]，a [n]> = a [ 2n + 2]）

（从下至上调整，堆排序从上至下调整）

实质上二叉排序树 堆，它是满足以下属性的完整二叉树:

如果a [k]> = a [2k + 1]和a [k]> =，则数组a [N]总共有N个元素，令2k + 1

将a [0-n-1]构建为大的顶部堆，这时a [0]是数组中的最大值（总共n个元素），第一个和最后一个元素a [0]和a [n-1]交换，因此a [n-1]是堆a [0 – n-1]的最大值，而a [0-（n-2）]调整a [0 –（n- 2）]对于无序树对于大的顶部堆，再次交换第一个和最后一个元素...重复第3步，直到最后一个元素得到一个升序数组a [0-n-1]一个具有n个节点的完整二叉树和n / 2个父节点.

从最后一个父节点a [n / 2-1]开始，将以父节点为顶点的每棵树调整到一个大的顶部堆（从底部到顶部调整）.

调整过程，除了根节点（即a [0]）之外的调整树之外，其他父节点大于子节点（因为在构建堆时，它是一个大的顶部堆），因此您可以将其取下来，只需调整一次即可（无需从下至上进行调整，因为第二层在第二次调整中具有最大值）.

在交换当前大顶部堆（最大元素根节点与最后一个元素）之后，最大元素位于数组的末尾，然后将前n-1个元素调整为大根堆. 重复步骤2，直到最后一个元素为止. 此时，该数组是一个升序数组.

以下是对数组进行排序的实现过程:

数组堆排序的实现过程

请注意:

第一步: 图中的树1是在交换7和5之后的，因此调整了子树，但是子树是节点5，因此不需要调整.

第二步: 图中的树2是在交换了7和3之后的，因此也要调整子树. 此时，子树的父节点为3，左子节点和右子节点分别为6和5，因此需要在调整为树3之后完成桩的构造. 因此，每当子节点和父节点交换时，它们都必须调整其下方的子树.

摘要:

构建堆时，最后一个父节点向上调整为根节点，但调整向下调整，并且每当需要交换子节点和父节点时，交换之后，它们也必须从将此父节点更改为下一步，调整此子树，如从树1到树3的过程所示.

在排序过程中进行调整时，请从根节点向下调整到需要调整的最后一个根节点. 这里的调整与建造桩时的调整相同，并且也向下调整.

这是相关堆排序的代码. 实际上，只要达到了原理，编写代码就非常简单.

/*
 //向下调整
 a:需要调整的数组
 head:开始调整的位置
 length:数组长度
 */
+ (void)ajustHeapWith:(int *)a head:(int)head length:(uint)length
{
    int leftChild = 2 * head + 1;
    int switchChild = leftChild; //交换的子节点
    if (leftChild >= length) {   //当只剩一个元素的时候，满足这个条件，也就是递归的出口了
        return;
    }
    int rightChild = leftChild + 1;
    if (rightChild < length) {
        //如果右子节点存在，且大于左子节点
        if (a[rightChild] > a[leftChild]) {
            switchChild = rightChild;  //就让交换的子节点等于右子节点
        }
    }
    //判断是否要交换
    if (a[switchChild] > a[head]) {
        //交换
        [self swap:&a[switchChild] with:&a[head]];
        //调整一下被交换过的子树
        [self ajustHeapWith:a head:switchChild length:length];
    }
}
//建堆
+ (void)buidHeapWith:(int *)a length:(uint)length
{
    for (int i = length/2 -1; i >= 0; i--) {
        [self ajustHeapWith:a head:i length:length];  //从下往上调整，但是调整是向下调整的
    }
}
+ (void)sortCArray:(int *)a length:(uint)length
{
    //1.建堆
    [self buidHeapWith:a length:length];
    //2.排序
    for (int i = length - 1; i > 0; i--) {
        // 1.交换a[0]与a[i]
        [self swap:&a[0] with:&a[i]];
        // 2.调整堆（移除了最后一个元素，即最大值，所以长度减1.然后从a[0]往下开始调整）
        [self ajustHeapWith:a head:0 length:i];
    }
}
+ (void)testHeapSort
{
    int maxCount = 1000;
    int *a = [self unsortedCArrayWithLenght:maxCount];
    [self logArray:a length:maxCount];
    [self sortCArray:a length:maxCount];
    [self checkAsendingSortArray:a length:maxCount];
    [self logArray:a length:maxCount];
    
    free(a);
}
+ (BOOL)checkAsendingSortArray:(int [])a length:(int)length
{
    for (int i = 0; i < length - 1; i++) {
        if (a[i] > a[i+1]) {
            NSLog(@"位置:%d,%d; 位置:%d,%d",i,a[i],i+1,a[i+1]);
            NSLog(@"非升序数组！！");
            return false;
        }
    }
    NSLog(@"该数组是升序数组！！");
    return true;
}
+ (void)logArray:(int[])a length:(int)length
{
    for (int i = 0; i < length; i++) {
        NSLog(@"%d",a[i]);
    }
}
+ (int *)unsortedCArrayWithLenght:(NSUInteger)length
{
    int *a = (int *) malloc(sizeof(int) * length);
    for (int i = 0; i < length; i++) {
        a[i] = rand()%length;
    }
    return a;
}
+ (void)swap:(int *)a with:(int *)b
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

所谓的遍历（Traversal）是指遵循一定的搜索路线，依次对树中的每个节点进行一次访问，而仅进行一次访问. 接入节点执行的操作取决于特定的应用程序问题. 遍历是二叉树上最重要的操作之一，也是二叉树上其他操作的基础.

如上图所示，遍历结果为:

示例问题:

结合以上两个遍历，先遍历确定根节点，中遍历确定左，右子节点，从而绘制二叉树图，然后编写后遍历.

如上所示，后遍历为: AEFDHZMG

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-273699-1.html