数据结构作业：二叉树

Requirements

0. 输出叶子节点
1. 求节点的 level（层数，or 级）
2. 求 LCA

Code

#define REP(i, x, y) for (int i = (x); i <= (y); ++i)
#define l(x) ((x) << 1) + 1
#define r(x) ((x) << 1) + 2
#define father(x) ((x)&1 ? (x) >> 1 : ((x) >> 1) - 1)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;

template <class T>
class Node {
   public:
    T value;
    int index;
    Node()
        : value(0), index(-1) {}
    Node(T value)
        : value(value), index(-1) {}
    void printNode() {
        if (this == nullptr) {
            cout << "null\n";
        } else {
            cout << "{value = " << value << ", index = " << index << "}\n";
        }
    }
    bool operator<(const Node<T>& that) {
        return this->index < that.index;
    }
};

template <class T>
class Tree {
   private:
    Node<T>* tree[N];
    int last;

   public:
    Tree()
        : last(-1) {}
    Tree(Node<T>* root) {
        root->index = 0;
        tree[last = 0] = root;
    }
    void printTree() {
        REP(i, 0, last) {
            tree[i]->printNode();
        }
    }
    Node<T>* getNodeByIndex(int index) {
        if (index > last) {
            return nullptr;
        } else {
            return tree[index];
        }
    }
    void setNodeByIndex(Node<T>* node, int index) {
        if (index == 0) {
            node->index = 0;
            tree[index] = node;
            last = (index > last ? index : last);
            return;
        }
        if (index > last && tree[father(index)] == nullptr) {
            return;
        } else {
            node->index = index;
            last = (index > last ? index : last);
            tree[index] = node;
        }
    }
    int getLevel() {
        return getLevel(last);
    }
    int getLevel(int index) {
        if (index < 0) {
            return -1;
        }
        return (int)floor(log2(index + 1)) + 1;
    }
    void printLeaves() {
        REP(i, 0, last) {
            Node<T>* n = getNodeByIndex(i);
            if (n != nullptr) {
                if (getNodeByIndex(l(i)) == nullptr && getNodeByIndex(r(i)) == nullptr) {
                    n->printNode();
                }
            }
        }
    }
    void getInOrder(Node<T>*);
    Node<T>* LCA(int, int);
};

template <class T>
// in which we store the inOrder
Node<T>* inOrder[N];

int p = 0;
template <class T>
void Tree<T>::getInOrder(Node<T>* root) {
    if (root->index > this->last) {
        return;
    }

    Node<T>* left = getNodeByIndex(l(root->index));
    Node<T>* right = getNodeByIndex(r(root->index));
    if (left != nullptr)
        getInOrder(left);
    inOrder<T>[p++] = root;
    if (right != nullptr)
        getInOrder(right);
}

int powerTable[30] = {1};
template <class T>
Node<T>* rmq[N][30];

template <class T>
Node<T>* Tree<T>::LCA(int x, int y) {
    // Firstly we need to get the inOrder.
    getInOrder(getNodeByIndex(0));
    // Then we apply RMQ on it. Using ST.
    REP(i, 1, getLevel()) {
        powerTable[i] = powerTable[i - 1] << 1;
    }
    REP(i, 0, last) {
        rmq<T>[i][0] = inOrder<T>[i];
    }
    // Now we need to find out the position of the nodes in inOrder[]
    int left, right;
    REP(i, 0, last) {
        Node<T>* t = inOrder<T>[i];
        if (t == nullptr) {
            break;
        }
        if (t->index == x) {
            left = i;
        }
        if (t->index == y) {
            right = i;
        }
    }
    if (left > right)
        swap(left, right);
    REP(i, 1, getLevel()) {
        REP(j, 0, last) {
            Node<T>* a = rmq<T>[j][i - 1];
            Node<T>* b = rmq<T>[j + powerTable[i - 1]][i - 1];
            if (a == nullptr && b == nullptr)
                break;
            if (a == nullptr) {
                rmq<T>[j][i] = b;
                continue;
            }
            if (b == nullptr) {
                rmq<T>[j][i] = a;
                continue;
            }
            rmq<T>[j][i] = a->index < b->index ? a : b;
        }
    }
    // Now that we can using ST to get RMQ of [left, right]
    // Thus LCA is available
    int margin = log2(right - left + 1);
    Node<T>* a = rmq<T>[left][margin];
    Node<T>* b = rmq<T>[right - powerTable[margin] + 1][margin];
    return a->index < b->index ? a : b;
}

int main(int argc, char const* argv[]) {
    ios::sync_with_stdio(true);
    cin.tie(nullptr);

    // Here is a demo showing the several methods of a tree.
    Node<int>* node = new Node<int>(114);
    Tree<int>* t = new Tree<int>;
    t->setNodeByIndex(node, 0);
    node = new Node<int>(514);
    t->setNodeByIndex(node, 1);
    node = new Node<int>(1919);
    t->setNodeByIndex(node, 2);
    node = new Node<int>(810);
    t->setNodeByIndex(node, 4);
    t->printTree();
    cout << "---------\n";
    t->printLeaves();
    cout << "---------\n";
    t->LCA(2, 4)->printNode();
    return 0;
}

Review

又臭又长

节点类 Node 包含值和索引，这个索引和它在表示树的数组中的索引是一致的。

类树本质上就是个 Node 指针数组，有个 last 表示最后一个元素的索引。（中间可以有空指针表示空节点）

设置节点的规则是：

• root 可以直接设置
• 如果不是根节点：
  • 索引比 last 更大，并且该索引对应的 father 存在，可以加，然后更新 last
  • 索引比 last 小，改掉就是了

---

判定为叶子的规则就是遍历一遍树，如果一个有效的、非空的节点，其左节点右节点均为空节点，即可说明它是叶子。

---

LCA 是通过对中序遍历做 RMQ 实现的。RMQ 是通过 ST 做的。

忘了不少，复习了一下小时候写的博客（

简单来说，两个节点的 LCA 就是 中序遍历中这两个节点围起来的这一列节点中索引最小的，当然，包括两节点自己。所以就是中序遍历后求 RMQ 的问题。

没搞 tarjan 还真是抱歉呐但是我真的太忙了所以偷个懒

以上です。じゃ、寝ます…