非递归实现遍历

  • 前序遍历非递归实现

    • 使用栈来完成。
    • 访问左节点，压入右节点。
    • 左节点为空，弹出右节点。

  • 中序遍历非递归实现

    • 使用栈来完成
    • 遇到一个节点，将其推入栈，遍历其左子树
    • 遍历完左子树，弹出栈顶节点并访问
    • 同时遍历其右节点，重复上述动作。

  • 非递归后续遍历二叉树

    • 从根节点开始，判断栈空还是非空
    • 沿左路下降。。。
    • 最难的。。总之就是左右子树访问完毕，才访问根节点

    O(n)

    ​

二叉树的搜索

  • 宽度搜索
    • 队列来存储
    • 类似层序遍历。
    • 访问当前节点，将左右节点压入队列
    • 弹出当前节点

存储结构

使用二叉链表的信息。当前节点，存储左右节点的指针。（还有的保存了parent指针）

寻找一个指针的父节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Node* FindParent(Node* root, Node* current){
    Node* tmp;
    if(root == NULL) return NULL;
    // root 是否为 current的父节点
    if(root->left == current || root->right == current){
       return root;
    }
    if(tmp = FindParent(root->left, current) != NULL){
        return tmp;
    }
    if(tmp = FindParent(root->right, current) != NULL)
   		return tmp;
   	return NULL;
}

Node* Tree(Node* current){
    stack<Node*> s;
    Node* tmp = root;
    s.push(NULL);
}

完全二叉树，用数组层序存储。

编号为 i 的节点的左节点为 2 i + 1

二叉搜索树

快速搜索，时间复杂度为 O(log n )

其中的构建二叉搜索树比较简单。这里重点记一下，BST删除节点的操作。

我们使用递归的来删除节点，需要分三种情况：

  1. 节点的左节点为空，直接将右节点复制到删除节点的位置。（不用考虑右节点是否为空）
  2. 如果左节点非空，右节点为空，那就将左节点复制到删除节点的位置。
  3. 如果左右节点都不为空，那就找出左子树中的最右节点，将右子树的根节点拼接到该最右节点的右边。
    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
void removehelp(Node* &root, int val){
    if(root == NULL) cout << val << " is not in the tree \n" << endl;
    else if(val < root->val){
        removehelp(root->left, val);
    }
    else if(val > root->val){
        removehelp(root->right, val);
    }
    else{
        Node* tmp = root;
        if(root->left == NULL) root = root->right;
        else if (root->right == NULL) root = = root->left;
        else{
            tmp = deletemin(root->right); // 找到右子树中最小的那个数 min，并删除
            root->setValue(tmp->value); // 将 min中的数赋值给删除的节点的值
        }
        delete tmp;
        tmp = NULL;
    }
}

Node* deletemin(Node * &root){
    if(root->left != NULL){
        return deletemin(root->left);
    }
    else{ // 找到右子树中最小的，删除，然后将该节点复制到原先被删除节点的位置
        node *tmp = root;
        root = root->right;
        return tmp;
    }
}

如何放置BST退化成线性结构？

允许重复关键码吗？