二叉树的基本算法

【结点个数计算】

结点个数计算

先统计出左子树、右子树的结点个数，再加上根结点即可，利用后序遍历即可解决

typedef struct BiTNode {    //二叉链表
    int data;               //数据域
    struct BiTNode *lchild; //左指针
    struct BiTNode *rchild; //右指针
} BiTNode, *BiTree;
int getNodeNum(BiTree &root) { //计算结点个数
    if (root == NULL)
        return 0;
    int left = getNodeNum(root->lchild);
    int right = getNodeNum(root->rchild);
    return left + right + 1;
}

叶结点个数计算

只有当一个结点的左指针右指针指向 NULL 时，才说明该结点是叶结点

typedef struct BiTNode {    //二叉链表
    int data;               //数据域
    struct BiTNode *lchild; //左指针
    struct BiTNode *rchild; //右指针
} BiTNode, *BiTree;
int getLeafNodeNum(BiTree &root) { //统计叶结点个数
    if (root == NULL)
        return 0;
    else if (root->lchild == NULL && root->rchild == NULL)
        return 1;
    else {
        int left = getLeafNodeNum(root->lchild);
        int right = getLeafNodeNum(root->rchild);
        return left + right;
    }
}

满结点个数计算

在二叉树中，满结点即双分支结点，是度为 $2$ 的结点，因此在统计时，仅有当左右子树均不为空时，个数 $+1$

typedef struct BiTNode {    //二叉链表
    int data;               //数据域
    struct BiTNode *lchild; //左指针
    struct BiTNode *rchild; //右指针
} BiTNode, *BiTree;
int getFullNodeNum(BiTree &root) { //统计满结点个数
    if (root == NULL)
        return 0;
    else if (root->lchild == NULL && root->rchild == NULL)
        return 0;
    else if (root->lchild != NULL && root->rchild == NULL)
        return getFullNodeNum(root->lchild);
    else if (root->lchild == NULL && root->rchild != NULL)
        return getFullNodeNum(root->rchild);
    else {
        int left = getFullNodeNum(root->lchild);
        int right = getFullNodeNum(root->rchild);
        return left + right + 1;
    }
}

除上述方法外，由于在二叉树中，当叶结点个数为 $n_0$，度为 $2$ 结点个数为 $n_2$ 时，有 $n_2=n_0-1$，故还有如下解法：

typedef struct BiTNode {    //二叉链表
    int data;               //数据域
    struct BiTNode *lchild; //左指针
    struct BiTNode *rchild; //右指针
} BiTNode, *BiTree;
int getFullNodeNum(BiTree &root) { //统计满结点个数
    return getLeafNodeNum(root) > 0 ? getLeafNodeNum(root)-1 : 0;
}

【深度计算】

由于树的深度 = max(左子树深度，右子树深度)+1，因此要先统计出左子树、右子树的深度，才能得到树的深度，利用后序遍历即可解决

typedef struct BiTNode {    //二叉链表
    int data;               //数据域
    struct BiTNode *lchild; //左指针
    struct BiTNode *rchild; //右指针
} BiTNode, *BiTree;
int getDepth(BiTree &root) { //计算深度
    if (root == NULL)
        return 0;
    int left = getDepth(root->lchild);
    int right = getDepth(root->rchild);
    return (left > right ? left : right) + 1;
}

【宽度计算】

二叉树的宽度即是最宽的一层的节点数，利用层序遍历的思想，计算每层的结点数，然后找出最大的即可

typedef struct BiTNode {    //二叉链表
    int data;               //数据域
    struct BiTNode *lchild; //左指针
    struct BiTNode *rchild; //右指针
} BiTNode, *BiTree;
int getWidth(BiTree root) { //计算宽度
    if (root == NULL)
        return 0;
    queue<BiTree> Q;
    Q.push(root);
    int width = 1; //宽度
    int count = 1; //每层的结点数
    while (!Q.empty()) {
        int temp = 0; //临时保存下层节点数
        for (int i = 0; i < count; i++) {
            BiTree p = Q.front();
            Q.pop();
            if (p->lchild != NULL) {
                temp++;
                Q.push(p->lchild);
            }
            if (p->rchild != NULL) {
                temp++;
                Q.push(p->rchild);
            }
        }
        if (temp == 0) //下一层没有结点，结束
            break;
        width = width > temp ? width : temp;
        count = temp;
    }
    return width;
}

【二叉树判定】

完全二叉树判定

对于完全二叉树来说，其叶结点只能出现在最下两层，因此考虑利用层序遍历的思想，一旦在队列中读到空指针，那么必将完全二叉树遍历完全，若空指针后还有要访问的元素，那么不是完全二叉树

typedef struct BiTNode {    //二叉链表
    int data;               //数据域
    struct BiTNode *lchild; //左指针
    struct BiTNode *rchild; //右指针
} BiTNode, *BiTree;
bool isCompleteBiTree(BiTree root) { //完全二叉树判定
    if (root == NULL)
        return true;
    queue<BiTree> Q;
    Q.push(root);
    while (!Q.empty()) {
        BiTree p = Q.front();
        Q.pop();
        if (p == NULL) //读到空指针，终止
            break;
        Q.push(p->lchild);
        Q.push(p->rchild);
    }
    while (!Q.empty()) { //检查队列中未访问到的结点
        BiTree p = Q.front();
        Q.pop();
        if (p != NULL) // p非空
            return false;
    }
    return true;
}

满二叉树判定

对于满二叉树来说，其除最后一层是叶结点外，每一层都是满的，即每一个节点都有左右孩子

因此，利用层序遍历的思想，统计结点数与层数，然后利用 $结点数=2^{层数}-1$ 的关系，即可判断二叉树是否为满二叉树

typedef struct BiTNode {    //二叉链表
    int data;               //数据域
    struct BiTNode *lchild; //左指针
    struct BiTNode *rchild; //右指针
} BiTNode, *BiTree;
bool isFullBiTree(BiTree root) { //满二叉树判定
    if (root == NULL)
        return true;
    int nodes = 0; //节点数
    int layers = 0; //层数
    BiTNode *tail = root; //尾指针
    BiTNode *nxt = NULL; //后继指针
    queue<BiTree> Q;
    Q.push(root);
    while (!Q.empty()) {
        root = Q.front();
        Q.pop();
        nodes++;

        if (root->lchild != NULL) {
            Q.push(root->lchild);
            nxt = root->lchild;
        }
        if (root->rchild != NULL) {
            Q.push(root->rchild);
            nxt = root->rchild;
        }

        if (root == tail) {
            tail = nxt;
            nxt = NULL;
            layers++;
        }
    }
    if (nodes == pow(2, layers) - 1) //节点数=2^层数-1
        return true;
    return false;
}