目录

二叉树

判断二叉树是否平衡

求二叉树的带权路径长度（WPL）

求二叉树的高度

求二叉树的宽度

数组排序

快速排序（经典版）

---

二叉树

判断二叉树是否平衡

算法思想

二叉树后序遍历，根据左右子树的高度差判断是否平衡

代码实现

//二叉树结点定义
typedef struct BiTNode {
    int data;   //数据域
    struct BiTNode* lchild, * rchild;   //指针域
}BiTNode, * BiTree;


bool isBalance = true;  //全局变量
int PostOrder(BiTree T) {
    if (T == NULL) {
        return 0;
    }
    int left = PostOrder(T->lchild);
    int right = PostOrder(T->rchild);
    if (left - right > 1) {
        isBalance = false;
        isBalance = false;
    }
    return left > right ? left + 1 : right + 1;
}

求二叉树的带权路径长度（WPL）

路径：树中两个结点之间的结点序列

路径长度：路径上所经过的边的个数

树的路径长度：根到每个结点的路径长度之和

结点的带权路径长度：根到结点的路径长度×该结点权值

树的带权路径长度（WPL）：所有叶结点的带权路径长度之和

算法思想

二叉树的带权路径长度（WPL）的计算方法

①定义：二叉树中全部叶结点的带权路径长度之和

②带权二叉树的性质：二叉树中所有非叶结点的权值之和

代码实现

先序遍历

//二叉树结点定义
typedef struct BiTNode {
    int data;   //数据域
    struct BiTNode* lchild, * rchild;   //指针域
}BiTNode, * BiTree;

int WPL = 0;
void PreOrder(BiTree T, int n) {
    if (T == NULL) {
        return;
    }
    if (T->lchild == NULL && T->rchild == NULL) {   //只累加叶结点
        WPL += n * T->data;
    }
    PreOrder(T->lchild, n + 1);
    PreOrder(T->rchild, n + 1);
}

求二叉树的高度

算法思想

①后序遍历，通过返回值传递高度

②先序遍历，通过参数传递高度，需要用到全局变量

代码实现

//二叉树结点定义
typedef struct BiTNode {
    int data;   //数据域
    struct BiTNode* lchild, * rchild;   //指针域
}BiTNode, * BiTree;

void PostOrder(BiTree T) {
    if (T == NULL) {
        return;
    }
    int left = PostOrder(T->lchild);
    int right = PostOrder(T->rchild);
    return left > right ? left + 1 : right + 1;
}

//二叉树结点定义
typedef struct BiTNode {
    int data;   //数据域
    struct BiTNode* lchild, * rchild;   //指针域
}BiTNode, * BiTree;

int height = 0;
void PreOrder(BiTree T, int n) {
    if (T == NULL) {
        return;
    }
    if (n > height) {
        height = n;
    }
    PreOrder(T->lchild, n + 1);
    PreOrder(T->rchild, n + 1);
}

求二叉树的宽度

二叉树的宽度：结点最多的那一层的结点数量

算法思想

先序遍历

算法实现

//二叉树结点定义
typedef struct BiTNode {
    int data;   //数据域
    struct BiTNode* lchild, * rchild;   //指针域
}BiTNode, * BiTree;

int width[MAX]; //记录各层结点个数

void PreOrder(BiTree T, int n) {
    if (T == NULL) {
        return;
    }
    width[n]++;
    PreOrder(T->lchild, n + 1);
    PreOrder(T->rchild, n + 1);
}

int TreeWidth(BiTree T) {
    for (int i = 0;i < MAX;i++) {
        width[i] = 0;
    }
    PreOrder(T, 0);
    int maxWidth = 0;
    for (int i = 0;i < MAX;i++) {
        if (width[i] > maxWidth) {
            maxWidth = width[i];
        }
    }
    return maxWidth;
}

数组排序

快速排序（经典版）

算法思想

只要可以通过排序来解决问题，并且是数组存储，都可以考虑快排，记住这个代码可以在考场上直接默写

代码实现

int Partition(int A[], int l, int h) {
    int pivot = A[l];
    while (l < h) {
        while (l < h && A[h] >= pivot) {
            h--;
        }
        A[l] = A[h];
        while (l < h && A[l] <= pivot) {
            l++;
        }
        A[h] = A[l];
    }
    A[l] = pivot;
    return l;
}

void QuickSort(int A[], int l, int h) {
    if (l >= h) {
        return;
    }
    int i = Partition(A, l, h);
    QuickSort(A, l, i - 1);
    QuickSort(A, i + 1, h);
}