c++ - "Climbing"一棵二叉树

Question

有没有办法不用访问其他分支直接爬树到数字？例如，如果我有数字 11，我必须先访问它，然后访问 2，然后访问 5，然后访问 11，而无需进行任何类型的搜索。

                                 0
                            /         \
                           /           \
                          /             \
                        1                2
                      /    \           /    \
                     /      \         /      \ 
                    3        4        5       6
                   / \      / \      / \     / \
                  /   \    /   \    /   \   /   \
                 7     8  9    10   11  12  13  14 

我已经浪费了很多时间，我现在唯一得到的就是要获得第 N 条路线(1 或 2)，您必须 (n-1)/2 直到 n 等于 1 或 2 .例子:(12 - 1)/2 => (5 - 1)/2 => 2. (7-1)/2=>(3-1)/2 => 1. (11-1)/5=>( 2-1)/2 => 1。但是到最后，切掉根 (0) 并将 2 当作一个新根来对待是正确的:

          2
         / \
        /   \
       /     \
     5        6
    / \      / \
   /   \    /   \ 
  11   12  13   14

         to

          0
         / \
        /   \
       /     \
     1        2
    / \      / \
   /   \    /   \ 
  3     4  5     6

解决方法:

int climb(int ID, Tree<int> t)
{

    int time = 0;
    if (tree.exists()) {
        time += t.value();
        tree t1, t2;
        t.branches(t1, t2);
        int branch = ID;
        while (branch > 2) branch = (branch - 1)/2;
        int offset = 1;
        while (offset*2 < ID - 1) offset *= 2;
        if (aux == 1) time += climb(ID - offset2/, a1);
        if (aux == 2) time += climb(ID - offset, a2);
    }
    return time;
}

您可以访问完整二叉树的任何(1、5、13 等)元素。

Answer 1

如果您想跳过中间的所有节点，请使用散列容器(例如 std::map 或 std::set)和散列搜索。二叉树意味着递归遍历。请注意，set 不是关联的，因此您需要稍微解决一下。

如果您过于努力地向树/树节点添加自定义代码/成员变量，您最终可能会得到一个占用大量内存的树实现(David 的回答就是一个很好的例子)。

-- 编辑--

如果您的 ID 始终是没有太多空洞的序列(例如 0, 1, 2,..., 50 或 68, 69,...,230,231) 我推荐普通的旧阵列!如果您想了解更多，请告诉我。

一般来说，我的建议是首先选择正确的容器/结构，然后仅在需要时对结构本身进行“小”修改。