树形结构的调试打印

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2846 天前的主题，其中的信息可能已经有所发展或是发生改变。

这是一篇讲究套路的数据结构实战教学文，阅读需要约 20 分钟。

先来回答三个问题。

为什么要打印树形结构

树形结构是算法里很常见的一种数据结构，从二叉树到多叉树，还有很多变种。很多涉及到算法的工作，就需要程序员自己手动实现树形结构，但出于结构本身复杂性，不太容易做对，需要一种调试工具来检测正确性。一般的调试手段无非就是加打印， GDB 上断点，写测试用例等，但这些局部以及外部的调试信息对于数据结构的整体把握提供的帮助十分有限，经验不足的程序员甚至可能会迷失在一大片调试信息的汪洋大海中找不着北。理解算法本身是一回事，自己动手是另一回事了，这跟我们理解算法的思维方式有关——对于数据结构而言，我们的感知是形象化的，比方脑海中自动出现一幅图，动态的插入删除，每个节点是如何变动的，平衡的时候局部是怎么旋转的等等，对智力正常的人来说不是什么难事。但对机器来说，它要面对的是只是一堆基于状态的指令而已，将人的形象思维转化为状态机，本身是一件艰难的工作，因为我们很难感知并存储这么多状态，这就需要工具来辅助，最好是画出整个形状结构，以直观地提醒我们哪里出错了，所谓**“观其形，见其义”**。

我们知道 Linux 有个 tree 命令用来打印树状目录列表，可以将某个目录下的所有文件和子目录一览无遗，非常直观，本文可以说就是为了实现这个效果，并给出源码实现。

为什么用深度优先遍历

主要是方便输出。在终端输出一般都是从左至右，从上到下，对于树形结构来说，前者自然表达的是从根节点到叶子节点，后者自然表达的是相邻分支，深度优先遍历符合输出次序。

实际上广度优先遍历实现起来更简单，只要在每一层左端建立一个链表头，将同一层的节点横向串联起来，从上到下遍历链表头数组就可以了。但考虑以下几点：

我们的屏幕没有这么宽，足以容纳整棵树，而且我们更趋向于纵向滚动浏览；
层次关系很难表示，光实现对齐就很麻烦；
每个节点需要维护一个额外 next 指针，如果这不是数据结构本身所需要的成员，对于存储空间来说是个额外的负担。

这也说明深度优先遍历第二个优点，它的实现对于数据结构本身是非侵入式的。

为什么使用非递归遍历

其实这是一个见仁见智的问题。递归还是非递归，不过是两种不同的遍历形式，不存在绝对的优劣，而且一般情况下可以相互补充。我个人选择非递归出于以下几种因素：

避免树层次过多导致函数调用堆栈溢出；
避免 C 语言函数调用开销；
所有状态可见可控。

当然以上因素并不重要，开心就好。

一切皆套路，不变应万变

既然本文讲究套路，那么干脆现在就把套路给出来好了，伪代码形式：

/* log 对象 */
typedef struct node_backlog {
    node 指针;
    回溯点位置（索引）;
};

/* Dump */
void dump(tree) {
    从根节点开始迭代;
    初始化 log 堆栈;
    for (; ;) {
        if (节点指针为空) {
            从 log 对象中获取回溯点位置;
            if (不存在，或无效的回溯点) {
                压栈空节点指针;
            } else {
                压栈当前节点指针，同时记录下一个回溯点位置;
            }
            if (回溯点位置索引为 0) {
                输出层次缩进、画路径，打印节点内容;
            }
            进入下一层;
        } else {
            if (log 堆栈为空) return;
            弹出 log 对象，获取最近记录的节点指针;
        }
    }
}

简单吧？而且我敢说，这个套路对于所有树形结构都是通用的，只要能够深度遍历。

不信我给出三个实战例子。

目录树或字典树

代码在gist。这是个 MIB 树，是管理网络节点（设备）用的。简要地讲，它具有两重特性：

节点之间的层次嵌套关系，决定了它属于目录层次结构；
节点的 key 具有公共前缀，使得它也类似于（或可用于）字典结构。

我们不需要关心其 CRUD 实现，只需要知道有一棵现成的目录树或者字典树，我们如何在终端输出它的形状。

#define OID_MAX_LEN  64

struct node_backlog {
    /* node to be backlogged */
    struct mib_node *node;
    /* the backtrack point, next to the orignal sub-index of the node, valid when >= 1, invalid == 0 */
    int next_sub_idx;
};

static inline void
nbl_push(struct node_backlog *nbl, struct node_backlog **top, struct node_backlog **bottom) {
    if (*top - *bottom< OID_MAX_LEN) {
        (*(*top)++) = *nbl;
    }
}

static inline struct node_backlog *
nbl_pop(struct node_backlog **top, struct node_backlog **bottom) {
    return *top > *bottom? --*top : NULL;
}

void mib_tree_dump(void) {
    int level = 0;
    oid_t id = 0;
    struct mib_node *node = *dummy_root; 
    struct node_backlog nbl, *p_nbl = NULL;
    struct node_backlog *top, *bottom, nbl_stack[OID_MAX_LEN];

    top = bottom = nbl_stack;

    for (; ;) {
        if (node != NULL) {
            /* Fetch the pop-up backlogged node's sub-id. If not backlogged, set 0. */
            int sub_idx = p_nbl != NULL ? p_nbl->next_sub_idx : 0;
            /* Reset backlog for the node has gone deep down */
            p_nbl = NULL;

            /* Backlog the node */
            if (is_leaf(node) || sub_idx + 1 >= node->sub_id_cnt) {
                nbl.node = NULL;
                nbl.next_sub_idx = 0;
            } else {
                nbl.node = node;
                nbl.next_sub_idx = sub_idx + 1;
            }
            nbl_push(*nbl, *top, *bottom);
            level++;
      
            /* Draw lines as long as sub_idx is the first one */
            if (sub_idx == 0) {
                int i;
                for (i = 1; i < level; i++) {
                    if (i == level - 1) {
                        printf("%-8s", "+-------");
                    } else {
                        if (nbl_stack[i - 1].node != NULL) {
                            printf("%-8s", "|");
                        } else {
                            printf("%-8s", " ");
                        }
                    }
                }
                printf("%s(%d)\n", node->name, id);
            }

            /* Go deep down */
            id = node->sub_id[sub_idx];
            node = node->sub_ptr[sub_idx];
        } else {
            p_nbl = nbl_pop(*top, *bottom);
            if (p_nbl == NULL) {
                /* End of traversal */
                break;
            }
            node = p_nbl->node;
            level--;
        }
    }
}

代码不算复杂，就讲几个要点：

深度优先遍历要利用回溯点，就是走到一个分支的尽头后，上溯到原先路过的某个位置，从另一个分支继续遍历，如果回溯到根节点，就说明遍历结束了，所以，回溯点是必须要记录的。问题是记录哪个位置呢？以二叉树为例，遍历了左子树后，接下来遍历的就是右子树，所以回溯点是右孩子；对于多叉树，遍历第 N 个分支后，接下来要遍历 N+1 分支，所以回溯点是 N+1 ；如果遍历完最后一个分支，则需要继续上溯寻找回溯点了。所以呢，我们就用 sub_idx + 1 来记录回溯点，我们还可以利用这个属性做个分类，值大于等于 1 时，回溯点有效，值等于 0 ，回溯点无效。

关于 log 堆栈操作，这里使用了二级指针的技巧。这个堆栈十分小巧，所以利用函数局部变量做存储也未尝不可，还有不需要对外暴露数据的好处。那么对于堆栈指针，就需要传递二次指针来改变它。比如我们看入栈操作：

(*(*top)++) = *nbl;

这是将 log 对象拷贝给 top 指向位置，然后将 top 指针上移， top 和 bottom 的差值就是堆栈元素的数目。由于 top 是二级指针，所以被赋值的是**top ，指针移动就是(*top)++。再来看出栈操作：

return --*top;

先将 top 下移一个单位，然后返回所指向的 log 对象，也就是*top 。

接下来该深入讲解套路了，首先，根节点设置成了 dummy ，这是一个虚拟节点，是为了保证最上层只有一个节点而使用的编码技巧，好比 tree 命令输出目录树总是从当前目录“.”开始。由于第一次进入循环， log 堆栈为空，不存在所谓回溯点，我们将回溯位置索引设为 0 ，这有两重含义，一来表示该回溯点无效或不存在，二来既然没有回溯，那么接下来就从当前节点的第一个分支开始遍历。

然后我们将遍历过的节点压栈，这里也是有区分的：如果当前是叶子节点，或者所有分支都遍历完了，那么应该继续上溯去寻找回溯点，我们就将回溯点设为无效后压栈；否则就将当前节点设为回溯点，并记录位置索引后压栈。

画线输出部分稍后讲。我们根据前面获取的索引 sub_idx 进入下一层，直到触底回溯，这时从 log 堆栈弹出回溯点， pop 有三种情况：由于第一个压栈为根节点，堆栈为空表示回溯到原点，也就标志着整个遍历结束，退出循环；否则查看回溯点是否为 NULL ，如果空如前所述继续上溯；如果存在有效回溯点，则将回溯位置索引取出，继续下一轮遍历循环。

最后讲终端输出。前面说过每一行从左至右的输出的是树的层次遍历，其实就是遍历 log 堆栈；换行输出就是树的分支遍历，就是每一轮循环。输出内容主要是三个符号：缩进、分支和节点内容。我们作如下策略：

缩进：当堆栈里回溯点无效，则不存在分支，打印空格，八个字符对齐；
分支：当堆栈里回溯点有效，表示存在分支，打印“|”和空格，八个字符对齐；
节点：当堆栈遍历到最后一个元素，表示后面将要输出节点内容，打印“+---”，八个字符对齐，后面跟节点内容。

当然你也可以自定义打印策略以便输出更美观。好了，说了一大堆，看效果吧，运行程序，一目了然。

B+树

代码在此。 B+树是关系数据库常用的底层数据结构，实现起来相当恐怖，所幸本文不讲这些，这里只是将 B+树作为多叉树示范如何打印，特别是叶子节点和非叶子节点本身定义不同的情况下。从输出实现上我们发现， log 对象记录的只是节点的指针和回溯位置，同数据节点本身没有关系。我们几乎可以原封不动地把上面的代码搬过来，运行效果如下：

从形状上可以看到 B+树的真实数据都存储在叶子节点，而且整棵树是平衡的。

红黑树（二叉树）

代码在此。理解了多叉树的实现，二叉树不过是一种特殊简化形式罢了。本文挑选了红黑树为代表，代码自己懒得写了，直接拿 Nginx 源码。

观察得出，二叉树关于回溯点的位置其实只有右边分支，也就是说回溯位置索引只有一个值，就是 1 。这样一来我们可以做个简化，将左分支索引设为 0 表示无效回溯位置，右分支索引设为 1 表示有效回溯位置，代码可以这样写：

#define RBTREE_MAX_LEVEL   64
#define RBTREE_LEFT_INDEX  0
#define RBTREE_RIGHT_INDEX 1

void rbtree_dump(struct rbtree *tree)
{
    int level = 0;
    struct rbnode *node = tree->root, *sentinel = tree->sentinel;
    struct node_backlog nbl, *p_nbl = NULL;
    struct node_backlog *top, *bottom, nbl_stack[RBTREE_MAX_LEVEL];

    top = bottom = nbl_stack;

    for (; ;) {
        if (node != sentinel) {
            /* Fetch the pop-up backlogged node's sub-id. If not backlogged, set 0. */
            int sub_index = p_nbl != NULL ? p_nbl->next_sub_idx : RBTREE_LEFT_INDEX;
            /* backlog should be reset since node has gone deep down */
            p_nbl = NULL;

            /* Backlog the node */
            if (is_leaf(node, sentinel) || sub_index == RBTREE_RIGHT_INDEX) {
                nbl.node = sentinel;
                nbl.next_sub_idx = RBTREE_LEFT_INDEX;
            } else {
                nbl.node = node;
                nbl.next_sub_idx = RBTREE_RIGHT_INDEX;
            }
            nbl_push(&nbl, &top, &bottom);
            level++;

            /* Draw lines as long as sub_idx is the first one */
            if (sub_index == RBTREE_LEFT_INDEX) {
                /* Print intent, branch and node content... */
            }

            /* Move down according to sub_idx */
            node = sub_index == RBTREE_LEFT_INDEX ? node->left : node->right;
        } else {
            /* Pop up the node backlog... */
        }
    }
}

让我们看一看输出效果……等等，我们发现对于二叉树，右孩子在左孩子的下一行打印，视觉上有点不习惯是吗？还好我贴心地将 LEFT_INDEX 和 RIGHT_INDEX 交换了一下次序，右孩子就先于左孩子输出了，这样一来你就可以歪着脑袋直观地看二叉树了（笑），同时我们还知道，“翻转”一棵二叉树是多么容易（笑）。