Home DS复习 Part 3
Post
Cancel

DS复习 Part 3

树的常见结论

在含有 n 个结点的二叉链表中, 含有 n+1 个空指针域.

证明:

  • 方法 1: n 个结点有 2n 个指针, 而 n 个结点有 n-1 条边, 即有 n-1 个非根结点, 每个非根结点对应其父结点的一个指针域, 所以有 n-1 个非空指针域 (只有根结点没有指向它的指针, 因为没有父结点), 因此空指针域数量为 2n-(n-1)=n+1.
  • 方法 2: 每个叶结点有两个空指针, 每个度为 1 的结点有 1 个空指针, 因此空指针总数为 $2n_0+n_1$. 而 $n_0=n_2+1$, 因此空指针共有 $2n_0+n_1=n_0+n_0+n_1=n_0+n_1+(n_2+1)=n+1$.

后序遍历的非递归算法… 居然可以应用于这么多场景:

  • 代码参考我的另一篇博客.
  • 根据代码可以很容易地看出, 栈中始终存放着 p 结点的所有祖先, 因此栈中所有结点就构成了从根结点到 p 结点的一条路径.
  • 可以应用于: 求根结点到某结点到路径, 求两个结点的最近公共祖先 (LCA).

线索二叉树

线索二叉树的定义

若将二叉树中的空指针域改为指向其在某种遍历次序下的前驱和后继结点的指针, 则称为线索二叉树.

1
2
3
4
5
struct ThreadNode {
    ElemType data;
    ThreadNode *lchild, *rchild;
    int ltag, rtag;
};
  • ltag=0 表示 lchild 指向左孩子, ltag=1 表示 lchild 指向前驱结点.
  • rtag=0 表示 rchild 指向右孩子, rtag=1 表示 rchild 指向后继结点.

线索二叉树的遍历

中序线索二叉树的遍历

1
2
3
4
5
6
7
8
9
10
11
12
void InOrder(ThreadNode *T) {
    ThreadNode *p = T;
    while (p != NULL) {
        while (p->ltag == 0) p = p->lchild;
        cout << p->data << " ";
        while (p->rtag == 1 && p->rchild != NULL) {
            p = p->rchild;
            cout << p->data << " ";
        }
        p = p->rchild;
    }
}

先序线索二叉树的遍历

1
2
3
4
5
6
7
8
9
10
11
void PreOrder(ThreadNode *T) {
    ThreadNode *p = T;
    while (p != NULL) {
        while (p->ltag == 0) {
            cout << p->data << " ";
            p = p->lchild;
        }
        cout << p->data << " ";
        p = p->rchild;
    }
}

后序线索二叉树的遍历

1
2
3
4
5
6
7
8
9
10
11
12
void PostOrder(ThreadNode *T) {
    ThreadNode *p = T;
    while (p != NULL) {
        while (p->ltag == 0) p = p->lchild;
        while (p->rtag == 1 && p->rchild != NULL) {
            cout << p->data << " ";
            p = p->rchild;
        }
        cout << p->data << " ";
        p = p->rchild;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void InThread(ThreadNode *p, ThreadNode *&pre) {
    if (p != NULL) {
        InThread(p->lchild, pre);
        if (p->lchild == NULL) {
            p->lchild = pre;
            p->ltag = 1;
        }
        if (pre != NULL && pre->rchild == NULL) {
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;
        InThread(p->rchild, pre);
    }
}

树的存储结构

三种表示法: 双亲表示法, 孩子表示法, 孩子兄弟表示法.

This post is licensed under CC BY 4.0 by the author.