二叉树的各种递归算法

1.求二叉树中的节点个数

//二叉树节点数
int NodeNum(BTNode *root) {
    if (root == NULL) //递归出口
        return 0;
    return NodeNum(root->lchild) + NodeNum(root->rchild) + 1; //分别求左右子树节点数
}

2.求二叉树的深度

//二叉树深度
int BTdeep(BTNode *root) {
    if (root == NULL) //递归出口
        return 0;
    int ldeep = BTdeep(root->lchild); //递归求左子树
    int rdeep = BTdeep(root->rchild); //递归求右子树
    return ldeep > rdeep ? (ldeep + 1) : (rdeep + 1)
}

3.求二叉树第K层的节点个数

//求二叉树第K层的节点个数
int TreeLevelSize(BTNode *root, int k) {
    if (root == NULL && k < 1) //递归出口
        return 0;
    if (k == 1)
        return 1;
    return TreeLevelSize(root->lchild, k - 1) + TreeLevelSize(root->rchild, k - 1);
}

4.求二叉树叶子节点个数

//求二叉树中叶子节点个数
int LeafNum(BTNode *root) {
    if (root == NULL) //递归出口
        return 0;
    if (root->lchild == NULL && root->rchild == NULL)
        return 1;
    return LeafNum(root->lchild) + LeafNum(root->rchild); //左右子树不同时为空
}

5.计算二叉树中双分支结点的个数

//计算分支节点
int Double(BTNode *root) {
    if (root == NULL) //递归出口
        return 0;
    if (root->lchild != NULL && root->rchild != NULL) //左右子树均不空
        return Double(root->lchild) + Double(root->rchild) + 1;
    else
        return Double(root->lchild) + Double(root->rchild); //左右子树有一个为空
}

6.删除二叉树中以元结点值x为的根节点的子树

//删除二叉树中以元结点值x为的根节点的子树
void Del_x_subTree(BTNode *root, int x) {
    if (root == NULL) //基于先序遍历的递归算法，先找到值为x的结点p,然后调用DestoryBTree(p)删除并释放该子树
        return;
    if (root->data == x) {
        DestoryBTree(root);
        root == NULL;
    } else {
        Del_x_subTree(root->lchild, x);
        Del_x_subTree(root->rchild, x);
    }
}

void DestoryBTree(BTNode *root) {
    if (root != NULL) { //释放二叉树b中所有结点分配的空间
        DestoryBTree(root->lchild);
        DestoryBTree(root->rchild);
        free(root);
    }
}

7.判断两棵二叉树是否相似

//判断两棵二叉树是否相似
int StructureCmp(BTNode *root2, BTNode *root2) {
    if (root == NULL && root2 == NULL) // 都为空，返回真
        return 1;
    else if (root == NULL || root2 == NULL) // 有一个为空，一个不为空，返回假
        return 0;
    int resultLeft = StructureCmp(root1->lchild, root2->lchild); // 比较对应左子树 
    int resultRight = StructureCmp(root1->rchild, root2->rchild); // 比较对应右子树
    return (resultLeft && resultRight);
}

8.查找一个值

//查找一个值
BTNode *TreeFind(BTNode *root, int to_find) {
    if (root == NULL) {
        //空树
        return NULL;
    }
    if (root->data == to_find) {
        return root;
    }
    BTNode *lresult = TreeFind(root->lchild, to_find);
    BTNode *rresult = TreeFind(root->rchild, to_find);
    //若左右子树均没有，返回值依然为空
    return lresult != NULL ? lresult : rresult;
}

9.返回一个结点的父结点

//返回一个结点的父结点
BTNode *Parent(BTNode *root, BTNode *node) {
    if (root == NULL) {
        return NULL;
    }
    if (root->lchild == node || root->rchild == node) {
        //说明此结点即为要找的结点的父结点
        return root;
    }
    BTNode *lresult = Parent(root->lchild, node);
    BTNode *rresult = Parent(root->rchild, node);
    return lresult != NULL ? lresult : rresult;
}

10.判断二叉树是不是平衡二叉树

//判断二叉树是不是平衡二叉树
int IsAVL(BTNode *root, int high) {
    if (root == NULL) // 空树，返回真
    {
        high = 0;
        return 1;
    }
    int highLeft;
    bool resultLeft = IsAVL(root->lchild, highLeft);
    int highRight;
    bool resultRight = IsAVL(root->rchild, highRight);
    if (resultLeft && resultRight && abs(highLeft - highRight) <= 1) // 左子树和右子树都是AVL，并且高度相差不大于1，返回真
    {
        high = max(highLeft, highRight) + 1;
        return 1;
    } else {
        high = max(highLeft, highRight) + 1;
        return 0;
    }
}

11.假设二叉树采用二叉链存储结构，设计一个算法，求二叉树b中值为x的结点的层号。

int L = 1;
//L是全局变量，初值为1,用来记录当前所访问的结点层号
void leno(BTNode *p, char x) {
    if (p == NULL)
        return;
    if (p->data == x) { //当第一次来到这个结点时，对其data域进行检查，看是否等于x,如果相等，则打印出其层号L
        printf("层号：%d", L);
    }
    ++L;    //打印完层号之后，指针p将要进入下一层结点，因此L要自增1,代表下一层的层号
    leno(p->lchild, x);
    leno(p->rchild, x);
    --L;    //p指针将要由下一层返回上一层，因此L要自减1,代表
}