Skip to content

树

约 882 个字 61 行代码 预计阅读时间 5 分钟

Tree 树

  • FirstChild-NextSibling 表示法
    • 记录第一个子节点和下一个兄弟节点
    • 因为一棵树的儿子顺序可以改变，所以一棵树的表示方式不唯一
    • 每棵树都可以通过 FirstChild-NextSibling 表示成 Binary Tree
      • 原树 T 的后序遍历和二叉树表示 BT 的中序遍历相同，且两者前序遍历相同

由于 \(2n_2 + n_1 +1= n_2 +n_1+ n_0\) ，所以\(n_2= n_0-1\)，即度为 2 的节点个数为叶结点个数减一。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
typedef struct TreeNode *Tree;
struct TreeNode {
    int Element;
    Tree Left;
    Tree Right;
};

Tree newnode(int data)
{
    Tree temp = (Tree)malloc(sizeof(struct TreeNode));
    temp->element = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

迭代版中序遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void iter_inorder(tree_ptr tree) {
    Stack S = create_stack();
    for (;;) {
        for (; tree; tree = tree->left)
            push(S, tree);
        tree = top(S); pop(S);
        if (!tree) break;
        visit(tree->element);
        tree = tree->right;
    }
}

从中序遍历和后序遍历得到一个二叉树

 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
33
34
35
int main(void){
    Tree T;
    int inorder[MAXN], postorder[MAXN], N, i;
    scanf("%d", &N);
    for (i=0; i<N; i++) scanf("%d", &inorder[i]);
    for (i=0; i<N; i++) scanf("%d", &postorder[i]);
    T = BuildTree(inorder, postorder, N);
}

Tree BuildTree(int inorder[],int postorder[],int N){
    Tree root=(Tree)malloc(sizeof(struct TreeNode));
    int index;
    if (N<=0) {
        return NULL;
    }else if (N==1) {
        root->Element=postorder[N-1];
        root->Left=NULL;
        root->Right=NULL;
        return root;
    }
    root->Element=postorder[N-1];
    for (int i = 0;i < N;i++)
        if (inorder[i]==postorder[N-1]) {
            index=i;
            break;
        }
    root->Left=BuildTree(inorder,postorder,index);
    root->Right=BuildTree(inorder+index+1,postorder+index,N-index-1);
    return root;
}
/*
 *若是想要以zigzagging order输出的话，建立两个栈，
 *第一个栈弹出顶端后依次将左节点和右节点压入第二个栈中；
 *第二个栈弹出顶端后一次将右节点和左节点压入第一个栈中，每个栈空了之后轮换到下一个栈
 */

线索二叉树 Threaded

建树的时候，每个节点是有两个指针（指向一左一右）的，N个节点，也就是2N个指针，但是实际上不是Null的只有N-1个，因为除了根都有一个指向这个节点，还有N+1个指针没有用，线索二叉树就是为了让这N+1个节点有用，指向的就是你的排序方式给出后，那个线性排列的“前驱”和“后驱”，左指针指向前驱，右指针指向后驱。

因此写选择题的时候可以先将遍历（无论是前序还是后序还是中序）列出来，再将虚线连上去。

Example

线索二叉树.png

二叉搜索树 Binary Search Tree

  • 二叉搜索树是一种二叉树，非空情况下服从以下性质：
    • 所有节点都有不同的 key（一个整数）
    • 左 ＜ 根 ＜ 右
    • 左子树和右子树也都是二叉搜索树
  • 二叉搜索树的中序遍历是有序的
  • 查找
    • 从根节点开始，如果 key 小于当前节点的 key，就往左子树找，否则往右子树找
    • 直到找到 key 相等的节点，或者找到空节点
    • 时间复杂度 𝑂(ℎ)，ℎ 为树的高度，即 𝑂(log⁡𝑛)
  • 查询最小值：遍历到最左边的节点
  • 查询最大值：遍历到最右边的节点
  • 插入
    • 从根节点开始，如果 key 小于当前节点的 key，就在左子树递归插入，大于就在右子树递归插入
    • 直到找到空节点，然后插入
    • 或者找到相同的 key，忽略
    • 时间复杂度 𝑂(logn)
  • 删除
    • 删除叶节点：直接删除即可
    • 删除只有一个儿子的节点：直接删除，然后把儿子接上
    • 删除有两个儿子的节点
      • Step 1: 将该节点替换为左子树的最大值，或右子树的最小值
      • Step 2: 删除左子树的最大值，或右子树的最小值
    • 在删除不多的情况下，可以仅找到该删除节点并标记删除，访问时忽略这个节点即可

Among the following binary trees, which one can possibly be the decision tree (the external nodes are excluded) for binary search?

折半查找判定树.png

其实是要判断哪棵树可以是折半查找判定树，答案选 A。

  • 折半查找判定树要求可以通过左右子节点的值找到 mid，可以通过根节点的左右子树大小判断求mid时应该取上界还是下界。
    • 如果叶节点统一朝左偏，则 \(mid = \lceil \frac{l+r}{2}\rceil\)
    • 如果叶节点统一朝右偏，则 \(mid = \lfloor\frac{l+r}{2} \rfloor\)
  • 如上图 A ，左子树有 5 个，右子树有 4 个，因此mid应该等于(left+right)/2+1（取大）
  • 因此，折半判定二叉树的叶节点应往同一侧偏
Comments: