数据结构

二叉树相关算法

Posted by Joel on June 29,2018

递归算法不在赘述。

先序遍历的非递归实现

思路：

  1. 先将根节点入栈
  2. 将栈顶元素出栈，访问之，如果该元素有右孩子则将右孩子入栈，如果有左孩子则将左孩子入栈
  3. 重复步骤2直到栈空

这种方法与图的深度优先搜索类似。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 先序遍历的非递归实现
void preOrder(BiTree tree) {
    InitStack(S);
    BiTNode p = tree;
    push(S, p);
    while(!isEmpty(S)) {
        // 循环的条件：
        // 应在栈中还有元素时循环
        pop(S, p); //将根节点出栈
        visit(p); // 访问之
        if (p -> rchild) {
            push(S, p -> rchild);
        }
        if (p -> lchild) {
            push(S, p -> lchild)
        }
    };
}

中序遍历的非递归实现

思路：

  1. 维护一个指针指向当前节点，初始状态指向根节点
  2. 如果当前节点不为空则将其入栈，并将指针指向该节点的左孩子
  3. 否则将栈中第一个结点出栈并访问，将指针指向该节点的右孩子
  4. 重复2-3的步骤直到栈为空并且当前节点为空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void inOrder(BiTree tree) {
    initStack(S);
    BiTNode p = tree;

    while(p || !isEmpty(S)) {
        if (p) {
            push(S, p);
            p = p -> lchild;
        } else {
            pop(S, p);
            visit(p);
            p = p -> rchild;
        }
    }
}

后序遍历的非递归实现

思路：

  1. 维护两个栈，S1用来存放临时数据，S2用来存放结果
  2. 从S1弹出栈顶元素压入S2，将S1的左右孩子入栈
  3. 重复步骤2直到S1为空
  4. 将S2中元素依次出栈即为结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void postOrder(BiTree tree) {
    BiTNode p = tree;
    initStack(S1);
    initStack(S2);
    push(S1, p);
    while (!isEmpty(S1)) {
        pop(S1, p);
        push(S2, p);
        if (p -> lchild) {
            push(S1, p -> lchild);
        }
        if (p -> rchild) {
            push(S1, p -> rchild);
        }
    }
    while (!isEmpty(S2)) {
        pop(S2, p);
        visit(p);
    }
}

二叉树的层次遍历

思路：借助队列来实现

  1. 将根节点入队
  2. 将根节点出队，访问之；将根节点的左孩子入队，右孩子入队
  3. 重复步骤2直到队列为空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void levelOrder(BiTree tree) {
    initQueue(Q);
    BiTNode p = tree;
    enQueue(Q, p);
    while (!isEmpty(Q)) {
        Dequeue(Q, p);
        visit(p);
        if ( p -> lchild) {
            enQueue(Q, p -> lchild);
        }
        if ( p -> rchild) {
            enQueue(Q, p -> rchild);
        }
    }
}

通过层次遍历求树高

思路：

观察层次遍历中的while循环

1
2
3
4
5
6
7
8
9
10
while (!isEmpty(Q)) {
    Dequeue(Q, p);
    visit(p);
    if ( p -> lchild) {
        enQueue(Q, p -> lchild);
    }
    if ( p -> rchild) {
        enQueue(Q, p -> rchild);
    }
}

实际上当第n层元素全部退队后，队列中的元素个数就是下一层元素的个数，如下图所示二叉树：

  1. 初始状态，队列中只有第一层元素–1，用一个变量CLS(curretLevelSize)记录队列中元素个数
  2. 当第一层元素全部退队，队列中有两个元素–2和3，更新CLS的值为2，即当前队列大小
  3. 当第二层元素全部退队，队列中有两个元素–4和5，更新CLS的值为2，即当前队列大小

这样只要在每层第一个元素退队时将层数+1即可完成算法。

C语言实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int getHeight(BiTree tree) {
    initQueue(Q);
    BiTNode p;
    enQueue(Q, p); // 根节点先入栈
    int CLS = 0, cnt = 0, height = 0;
    while (!isEmpty(Q)) {
        // 外层循环每次执行就代表有一层节点已经全部退队
        height++; // 层数+1
        CLS = size(Q); // 将CLS更新为当前层节点数
        cnt = 0; // cnt是当前层已经退队的节点数
        while (cnt < CLS) {
            deQueue(Q, p);
            cnt++; // 出队一个元素，cnt+1
            if (p -> lchild) {
                enQueue(Q, p -> lchild);
            }
            if (p -> rchild) {
                enQueue(Q, p -> rchild);
            }
        }
    }
    return height;
}

从先序遍历的结果和中序遍历的结果构造二叉链表

思想：

  1. 根据先序序列确定树的根结点
  2. 根据根节点在中序序列中划分出左右子树包含哪些结点，然后根据左右子树结点在先序序列中的次序可以确定子树的根节点，即回到步骤一
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
26
27
28
29
30
31
32
BiTree preInCreate(ElemType A[], ElemType B[], int FOP, int LOP, int FOI, int LOI) {
// 先序和中序序列存储在两个数组A、B中，FOP、LOP分别为先序的第一和最后一个下标
// 即当前子树的先序遍历结果，FOI、LOI分别为中序的第一和最后一个下标
// 初始状态FOP = FOP = 1，LOP = LOI = n
    root = (BiTNode*)malloc(sizeof(BiTNode)); // 构造根节点
    root -> data = A[FOP]; // 根节点

    int i = FOI; // 是根节点在中序序列中的位置

    for (; B[i] != root -> data; i++) // 在中序序列中找到根节点的位置

    llen = i - FOI; // 左子树长度
    rlen = LOI - i; // 右子树长度

    if (llen) {
        root -> lchild = preInCreate(A, B, FOP + 1, FOP + llen, FOI, FOI + llen - 1);
        // 非常trick的一步，主要问题是参数为什么这么取
        // FOP + 1：我们知道FOP是当前树的先序序列的第一个节点，那么FOP + 1不就是当前树的左孩子吗，不就是左子树的根节点吗
        // FOP + llen：就是左子树最后一个节点
        // FOI 与 FOI + llen - 1 是左子树中序序列
    } else {
        root -> lchild = NULL;
    }

    if (rlen) {
        root -> rchild = preInCreate(A, B, h1 - rlen + 1, h1, h2 - rlen + 1, h2);
    } else {
        root -> rchild = NULL;
    }

    return root;
}

判别给定二叉树是否为完全二叉树

思路：采用层次遍历，将所有节点全部加入队列（包括空节点），这样相当于层次遍历了一棵满二叉树，出队时如果遇到空节点则该节点之后的所有节点都应该为空节点，否则不是完全二叉树。

求二叉树中度为2的节点个数

思路：采用递归算法，f(t)的模型如下:

case return
b == NULL 0
b->lchild && b->rchild f(t->lchild) + f(t->rchild) + 1
else f(t->lchild) + f(t->rchild)

交换每个节点的左右节点

思路：采用递归，f(t)模型如下：

递归基： f(t)交换t的左子节点和右子节点
终止条件：t == NULL
递归调用：f(t->lchild); f(t->rchild)

寻找先序遍历中第k个节点的值

思路：递归，维护一个全局变量代表查找次数，f(t)模型如下：

递归基：在t的左右子树查找，每查找一次i + 1

终止条件：i == k

EOF

FEATURED TAGS
数据结构
FRIENDS
>