文档章节

100行C代码终端打印树形结构

我的上铺叫路遥
 我的上铺叫路遥
发布于 2017/02/06 21:08
字数 3197
阅读 4025
收藏 140

讲究套路之前,先来回答三个问题。

为什么要打印树形结构

树形结构是算法里很常见的一种数据结构,从二叉树到多叉树,还有很多变种。很多涉及到算法的工作,就需要程序员自己手动实现树形结构,但出于结构本身复杂性,不太容易做对,需要一种调试工具来检测正确性。一般的调试手段无非就是加打印,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堆栈;换行输出就是树的分支遍历,就是每一轮循环。**输出内容主要是三个符号:缩进、分支和节点内容。我们作如下策略:

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

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

<center>![MIB树](https://static.oschina.net/uploads/img/201702/06211345_ILBk.png "MIB树")</center>

B+树

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

</center> ![B+树](https://static.oschina.net/uploads/img/201702/06211805_esIo.png "B+树") </center>

从形状上可以看到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交换了一下次序,右孩子就先于左孩子输出了,这样一来你就可以歪着脑袋直观地看二叉树了(笑),同时我们还知道,“翻转”一棵二叉树是多么容易(笑)。

<center>![红黑树](https://static.oschina.net/uploads/img/201702/06212006_glT5.png "红黑树")</center>

工欲善其事,必先利其器。学会了树形结构打印工具,针对这样的数据结构,只有你写不了的,没有你写不对的。最后给出一个思考题:如何用递归形式实现打印树形结构?(提示:利用参数传递)

参考源码

目录树 B+树 红黑树

© 著作权归作者所有

我的上铺叫路遥

我的上铺叫路遥

粉丝 84
博文 3
码字总数 8610
作品 4
浦东
程序员
私信 提问
加载中

评论(3)

_ashes_of_time_
_ashes_of_time_
火眼金睛容嬷嬷
火眼金睛容嬷嬷
控制台怎么表现其实是个艺术而不是技术
Liuzh_533
Liuzh_533
JS 30行的例子,没有这篇博客那么高深,但是可以玩玩:
http://blog.csdn.net/isea533/article/details/52629452
100 行 C 代码终端打印树形结构

原文出处:我的上铺叫路遥 讲究套路之前,先来回答三个问题。 为什么要打印树形结构 树形结构是算法里很常见的一种数据结构,从二叉树到多叉树,还有很多变种。很多涉及到算法的工作,就需要...

我的上铺叫路遥
2017/02/08
0
0
Go 实现的树形结构打印文件目录--GoTree

GoTree,用于在终端打印树形结构的简单的 Go 模块 GoTree 的目标是一个简单的工具,提供一个易于使用和快速的方式打印递归结构。 特点: 非常简单和快速的代码 直观的名称 易于扩展 仅使用本...

匿名
2017/01/22
384
0
Java的类加载器ClassLoader

Java类加载方式采取树形结构的双亲委托机制。如下图: Bootstrap:加载rt.jar中所有的类,C/C++编写,Java中不存在该类 ExtClassLoader:加载ext目录下所有的扩展类 AppClassLoader:加载应用...

Namikun
2018/05/16
0
0
Android程序员面试会遇到的算法(part 1 关于二叉树的那点事) 附Offer情况

今年可谓是跌宕起伏的一年,幸好结局还算是圆满。开年的时候由于和公司CTO有过节,被"打入冷宫",到下半年开始找工作,过程还是蛮艰辛。先分享一下offer的情况 国内的有 1.阿里口碑(offer) 2...

qing的世界
2017/12/29
0
0
二叉树的遍历 (二叉树遍历转换)

本题有多组数据,输入处理到文件结束。 每组数据的第一行包括一个整数n,表示这棵二叉树一共有n个节点。 接下来的一行每行包括n个整数,表示这棵树的中序遍历。 接下来的一行每行包括n个整数...

SunMoonVocano
2017/07/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

RxJava进行单元测试的方式

@Test public void completeTask_retrievedTaskIsComplete() { // Given a new task in the persistent repository final Task newTask = new Task(TITLE, ""); ......

SuShine
2分钟前
1
0
正则表达式大全

检验手机号码 # 要求:手机号码必须为11位数字,以1开头,第二位为1或5或8。import redef verify_mobile(): mob = input("请输入手机号码:") ret = re.match(r"1[358]\d{9}", m......

彩色泡泡糖
6分钟前
1
0
QT之border-image属性

一、border-image的兼容性 border-image可以说是CSS3中的一员大将,将来一定会大放光彩,其应用潜力真的是非常的惊人。可惜目前支持的浏览器有限,仅Firefox3.5,chrome浏览器,Safari3+支持...

shzwork
6分钟前
2
0
Kubernetes Operator简易教程

1. 安装operator-sdk //安装 operator-sdk$ apt-get install operator-sdk.....$ operator-sdk versionoperator-sdk version: v0.7.0$ go versiongo version go1.11.4 darwin/amd64 2......

Robotcl_Blog
7分钟前
2
0
再谈DAG任务分解和Shuffle RDD

1、DagScheduler分析 DagScheduler功能主要是负责RDD的各个stage的分解和任务提交。Stage分解是从触发任务调度过程的finalStage开始倒推寻找父stage,如果父stage没有提交任务则循环提交缺失...

守望者之父
12分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部