LCA（最近公共祖先）问题

  1. 顺序存储方式
1
2
3
4
5
6
7
8
9
10
11
ElemType LeastCommonAncestor(SqTree T,int i,int j){
    if(T[i] != "#" && T[j] != "#"){
        while(i != j){
            if(i > j)   i = i/2;
            else    j = j/2;
        }
        return T[i];
    }
    return NULL;
}

  1. 二叉链表存储方式
1
2
3
4
5
6
7
8
9
10
11
12
13
BiNode *LeastCommonAncestor(BiNode * T,BiNode * p,BiNode * q){
    if(T == NULL || T == p || T == q)
        return T;
    BiNode * left = LeastCommonAncestor(T->left,p,q);
    BiNode * right = LeastCommonAncestor(T->right,p,q);

    if(left && right){
        return T;
    }else{
        return left == NULL?right:left;
    }
}

二叉树计数问题

下面几个小算法二叉树全部用二叉链表存储

  1. 叶子结点数
1
2
3
4
5
6
7
8
9
int LeafCount(BiTree T){
    if(T == NULL){
        return 0;
    }else if(T->rchild == NULL && T->rchild == NULL){
        return 1;
    }else{
        return LeafCount(T->lchild) + LeafCount(T->rchild);
    }
}
  1. 二叉树深度（递归算法，非递归见8）
1
2
3
4
5
6
7
8
9
10
11
int BiTreeDepth(BiTree T){
    if(T == NULL){
        return 0;
    }else{
        int left = BiTreeDepth(T->lchild);
        int right = BiTreeDepth(T->right);

        return left > left? left + 1 : right + 1;
    }
}

  1. 二叉树结点总数
1
2
3
4
5
6
7
int BiTreeNode(BiTree T){
    if(T == NULL){
        return 0;
    }else{
        BiTreeNode(T->lchild) + BiTreeNode(T->rchild) + 1;
    }
}
  1. 二叉树中度为1的结点个数
1
2
3
4
5
6
7
8
int BiTreeDegree1(BiTree T){
    if(T == NULL)
        return 0;
    if((T->lchild == NULL && T->rchild != NULL ) || (T->lchild != NULL && T->rchild == NULL ))
        return BiTreeDegree1(T->lchild) + BiTreeDegree1(T->rchild) + 1;

    return BiTreeDegree1(T->lchild) + BiTreeDegree1(T->rchild);
}
  1. 二叉树中度为2的结点个数
1
2
3
4
5
6
7
8
9
int DsonNode(BiTree T){
    if(T == NULL){
        return 0;
    }else if(T->lchild != NULL && T->rchild != NULL){
        return DsonNode(T->lchild) + DsonNode(T->rchild) + 1;
    }else{
        return DsonNode(T->lchild) + DsonNode(T->rchild);
    }
}
  1. 给定结点总数，统计所有可能的二叉树个数（即卡特兰数）
1
2
3
4
5
6
7
8
9
10
int Probable(int n){
    if(n == 0)
        return 1;   //空树也是二叉树
    int sum = 0;
    for(int i = 0;i < n;i++){
        sum += Probable(i) * Probable(n-i-1);
    }

    return sum;
}
  1. 给定前序和后序，判断可能的二叉树个数
1
2
3
4
5
6
7
8
9
10
11
12
int ComputeDiffTreeNum(String &str1,String &str2){
    int count = 1;
    if(str1.length() <= 1)
        return 1;
    for(int i = 1;i < str1.length();i++){
        int posInstr2 = str2.find(str1[i]);
        if(str1[i-1] == str2[posInstr2+1])
            count * = 2;
    }

    return count;
}
  1. 二叉树深度的非递归算法
    本算法还可用于求二叉树的宽度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int BiTreeDepth(BiTree T){
    if(!T)
        return 0;

    int front = -1,rear = -1;
    int last = 0,level = 0;
    BiTree Q[maxSize];
    BiTree p;

    Q[++rear] = T;
    while(front < rear){
        p = Q[++front];
        if(p->lchild)
            Q[++rear] = p->lchild;
        if(p->rchild)
            Q[++rear] = p->rchild;

        if(front == last){
            level++;
            last = rear;
        }
    }

    return level;
}

参考书籍

  1. 严蔚敏，吴伟民.数据结构：C语言版[M].北京：清华大学出版社.2007.

  2. 王道论坛.2019年数据结构考研复习指导[M].北京：电子工业出版社.2018.