树

约 890 个字 107 行代码 1 张图片预计阅读时间 4 分钟

1. 基础知识

树的性质：
- 第 \(i\) 层最多有\(2^{i-1}\)个节点；深度为 \(k\) 的二叉树最多有\(2^k-1\)个节点。
- 对于非空二叉树，\(n_0=n_2+1\)
证明需要会推广到 \(n\) 叉树：

证明

令 \(n_1\) 为度为 1 的节点，\(n\) 为节点总数，则\(n = n_0 + n_1 + n_2\)
令 \(B\) 为边的条数，则 \(n = B + 1\)，而且不难发现 \(B = n_1 + 2n_2\)
联立上述三个方程，可以得到 \(n_0 = n_2 + 1\)(\(n_1\) 被消掉了)

前序、中序、后序遍历无非是递归，略。

2. BST

非空左子树的键必须小于根上的键；
非空右子树的键必须大于根上的键；
删除节点：
- 删除叶子节点，直接设为NULL
- 删除度为1的节点，用该节点的子节点替换自己
- 删除度为2的节点
  - 用该节点左子树的最大节点或右子树的最小节点（挑一种）替换它自身
  - 从子树中删除用来替换的节点
线索二叉树：
- 如果 Tree->Left 为空，将它指向中序遍历中的前一个节点
- 如果 Tree->Right 为空，将它指向中序遍历中的后一个节点
- 有一个头节点(dummy node)，使得最左边和最右边孩子分别指向这个节点的左右孩子

注

虽然这里默认使用中序遍历的定义，但我们也可以将其修改成前序或者后序遍历的版本 ( 比如对于后序遍历版的线索二叉树，某个节点空出来的左子树指向它在后序遍历中的前一个节点，空出来的右子树指向它在后序遍历中的后一个节点 )

3. BST 定义 & 基本函数

#include<stdio.h>
#include<stdlib.h>

typedef struct TreeNode *SearchTree;

struct TreeNode{
    int root;
    SearchTree left;
    SearchTree right;
};

typedef struct TreeNode *Position;

Position Find(int x,SearchTree T){
    if(T==NULL){
        return NULL;
    }
    else{
        if(x<T->root){
            return(Find(x,T->left));
        }
        else if(x>T->root){
            return(Find(x,T->right));
        }
        else{
            return T; //founded
        }
    }
}

//即找最左边的点
//最左边的例子，这个节点没有左节点了
Position FindMin(SearchTree T){
    if(T==NULL){
        return NULL;//空树，返回空
    }
    else{
        if(T->left==NULL){
            return T;
        }
        else{
            return FindMin(T->left);
        }
    }
}

//FindMax逻辑类似，找最右边的点
Position FindMax(SearchTree T){
    if(T==NULL){
        return NULL;
    }
    else{
        if(T->right==NULL){
            return T;
        }
        else{
            return FindMax(T->right);
        }
    }
}
SearchTree Insert(int x, SearchTree T){
    if(T==NULL){
        //递归终点，创建一个节点
        T=(SearchTree)malloc(sizeof(struct TreeNode));
        T->root=x;
        T->left=NULL;
        T->right=NULL;
    }
    else{
        if(x<T->root){
            T->left=Insert(x,T->left);
        }
        else if(x>T->root){
            T->right=Insert(x,T->right);
        }
    }
    return T;
}
SearchTree Delete(int x,SearchTree T){
    if(x<T->root){
        //Go Left
        T->left=Delete(x,T->left);
    }
    else if(x>T->root){
        T->right=Delete(x,T->right);
    }
    else{
        if(T->left && T->right){
            Position tmp=FindMin(T->right);
            T->root=tmp->root;
            T->right=Delete(tmp->root,T->right);
        }
        else{//0 or 1 child
            Position tmp=T;
            if(T->left==NULL){
                T=T->right;
            }
            else if(T->right==NULL){
                T=T->left;
            }
            free(tmp);
        }
    }
    return T;
}

//这里不用Find的原因：因为Delete是递归的过程，需要返回删除的子树，所以Find的话就没有这样递归的过程，直接操作节点了，没有返回到上一层，不好。

4. 理论题

In a binary search tree which contains several integer keys including 4, 5, and 6, if 4 and 6 are on the same level, then 5 must be their parent.

Answer

False
5还可以是更远的祖先：
![[Pasted image 20250620194010.png|194]]

![[Pasted image 20250620194413.png]]

Answer

保证取整方式一致, 这样好像应该只有两种树。

A 'full tree' of degree 3 (every non-leaf node has 3 children) has 61 nodes. Then its height \(h\) is at most ( ). Note: \(h = 0\) for a single node tree."

Answer

性质：对于任何度为\(m\)的满树，总节点数\(n\)和内部节点数\(i\)（非叶子节点）之间存在固定关系：\(n-1=im\).
（解释：树中除了根节点，每个节点都有一个父节点。所以，总边数是 \(n-1\). 每条边都从一个内部节点（非叶子节点）发出。因为每个内部节点都有\(m\) 个孩子，所以总边数也等于\(im\)）
\(\therefore 61-1=3i,i=20\)，答案是20.
构造方式：不要总是想着满二叉树，每三个叶子节点中只有一个重新变成下一个的根节点，变成一颗比较瘦的树。

If a binary search tree of \(N\) nodes is complete, which one of the following statements is FALSE?

A. the average search time for all nodes is \(O(\log N)\)
B. the minimum key must be at a leaf node
C. the maximum key must be at a leaf node
D. the median node must either be the root or in the left subtree"

Answer

注意到这是完全二叉搜索树，最大值可能在上一层最右边的结点,该节点只有左儿子。

Given a binary search tree with its level order traversal sequence {7, 4, 12, 3, 6, 8, 1, 5, 10}. If 7 is deleted from the tree, which one of the following statements is FALSE?
- [ ] A. 5 and 8 may be at the same level
- [ ] B. The in-order traversal is {1, 3, 4, 5, 6, 8, 10, 12}
- [ ] C. 3 and 12 may be at the same level
- [ ] D. 6 and 10 may be at the same level

Answer

|500

选C。

树

1. 基础知识

2. BST

3. BST 定义 & 基本函数

4. 理论题

Comments