精华内容
下载资源
问答
  • 无按凹入表形式打印树形结构。(1)利用树的先根遍历方法; (2)利用结点的深度控制横向位置。
  • Java打印树形结构

    千次阅读 2017-08-11 17:11:11
    序言最近在学习算法相关的东西,有一些树形结构的数据需要打印出来开对不对,比如二分搜索树,于是我就写了一个工具类。希望能帮到大家效果源码BST(二分搜索树)package com.zgh.algorithm.search;import java.util....

    序言

    最近在学习算法相关的东西,有一些树形结构的数据需要打印出来开对不对,比如二分搜索树,于是我就写了一个工具类。希望能帮到大家

    效果

    这里写图片描述

    源码

    BST(二分搜索树)

    package com.zgh.algorithm.search;
    
    import java.util.HashMap;
    import java.util.Iterator;
    import java.util.Map;
    
    import com.zgh.algorithm.search.TreePrintUtil.TreeNode;
    
    /**
     * 二分搜索树
     * 
     * @author zhuguohui
     *
     */
    public class BST<K extends Comparable<K>, V> {
        private int count;
        private Node<K, V> root;
        private int maxLevel;
    
        public int size() {
            return count;
        }
    
        public boolean isEmpty() {
            return count == 0;
        }
    
        public void insert(K k, V v) {
            Node<K, V> node = new Node<>(k, v);
            if (insertToNode(root, node, 0)) {
                // 如果是插入则将count+1
                count++;
            }
        }
    
        public Node getRoot() {
            return root;
        }
    
        /**
         * 
         * @param parint
         * @param node
         * @return 如果新增返回true,如果只是更新返回false
         */
        private boolean insertToNode(Node<K, V> parent, Node<K, V> node, int level) {
            if (root == null) {
                root = node;
                maxLevel = 1;
                return true;
            }
            if (parent.k.compareTo(node.k) == 0) {
                // key相同则更新
                parent.v = node.v;
                return false;
            } else if (parent.k.compareTo(node.k) < 0) {
                // 如果node比parent大,则插入到右子树
                if (parent.right == null) {
                    parent.right = node;
                    if (level + 1 > maxLevel) {
                        maxLevel = level + 1;
                    }
                    return true;
                }
                return insertToNode(parent.right, node, level + 1);
            } else {
                // 如果node比parent小,则插入左字数
                if (parent.left == null) {
                    parent.left = node;
                    if (level + 1 > maxLevel) {
                        maxLevel = level + 1;
                    }
                    return true;
                }
                return insertToNode(parent.left, node, level + 1);
            }
    
        }
    
        private static class Node<K extends Comparable<K>, V> implements TreeNode {
            K k;
            V v;
            Node left, right;
    
            public Node(K k, V v) {
                this.k = k;
                this.v = v;
            }
    
            @Override
            public String toString() {
                return "[" + k + "]";
            }
    
            @Override
            public String getPrintInfo() {
    
                return toString();
            }
    
            @Override
            public TreeNode getLeftChild() {
                // TODO Auto-generated method stub
                return left;
            }
    
            @Override
            public TreeNode getRightChild() {
                // TODO Auto-generated method stub
                return right;
            }
    
        }
    }
    

    TreePrintUtil(打印树形结构工具类)

    package com.zgh.algorithm.search;
    
    import java.util.HashMap;
    import java.util.Iterator;
    import java.util.Map;
    
    public class TreePrintUtil {
        public static void pirnt(TreeNode root) {
            // 找到左边的最大偏移量
            int maxLeftOffset = findMaxOffset(root, 0, true);
            int maxRightOffset = findMaxOffset(root, 0, false);
            int offset = Math.max(maxLeftOffset, maxRightOffset);
            // 计算最大偏移量
            Map<Integer, PrintLine> lineMap = new HashMap();
            calculateLines(root, offset, lineMap, 0, true);
            Iterator<Integer> lineNumbers = lineMap.keySet().iterator();
            int maxLine = 0;
            while (lineNumbers.hasNext()) {
                int lineNumber = lineNumbers.next();
                if (lineNumber > maxLine) {
                    maxLine = lineNumber;
                }
            }
            for (int i = 0; i <= maxLine; i++) {
                PrintLine line = lineMap.get(i);
                if (line != null) {
                    System.out.println(line.getLineString());
                }
            }
    
        }
    
        private static void calculateLines(TreeNode parent, int offset, Map<Integer, PrintLine> lineMap, int level,
                boolean right) {
            if (parent == null) {
                return;
            }
            int nameoffset = parent.toString().length() / 2;
            PrintLine line = lineMap.get(level);
            if (line == null) {
                line = new PrintLine();
                lineMap.put(level, line);
            }
            line.putString(right ? offset : (offset - nameoffset), parent.toString());
            // 判断有没有下一级
            if (parent.getLeftChild() == null && parent.getRightChild() == null) {
                return;
            }
            // 如果有,添加分割线即/\
            PrintLine separateLine = lineMap.get(level + 1);
            if (separateLine == null) {
                separateLine = new PrintLine();
                lineMap.put(level + 1, separateLine);
            }
            if (parent.getLeftChild() != null) {
                separateLine.putString(offset - 1, "/");
                calculateLines(parent.getLeftChild(), offset - nameoffset - 1, lineMap, level + 2, false);
            }
            if (parent.getRightChild() != null) {
                separateLine.putString(offset + nameoffset + 1, "\\");
                calculateLines(parent.getRightChild(), offset + nameoffset + 1, lineMap, level + 2, true);
            }
    
        }
    
        /**
         * 需要打印的某一行
         * 
         * @author zhuguohui
         *
         */
        private static class PrintLine {
            /**
             * 记录了offset和String的map
             */
            Map<Integer, String> printItemsMap = new HashMap<>();
            int maxOffset = 0;
    
            public void putString(int offset, String info) {
                printItemsMap.put(offset, info);
                if (offset > maxOffset) {
                    maxOffset = offset;
                }
            }
    
            public String getLineString() {
                StringBuffer buffer = new StringBuffer();
                for (int i = 0; i <= maxOffset; i++) {
                    String info = printItemsMap.get(i);
                    if (info == null) {
                        buffer.append(" ");
                    } else {
                        buffer.append(info);
                        i += info.length();
                    }
                }
                return buffer.toString();
            }
    
        }
    
        private static int findMaxOffset(TreeNode parent, int offset, boolean findLeft) {
            if (parent != null) {
                offset += parent.toString().length();
            }
            if (findLeft && parent.getLeftChild() != null) {
                offset += 1;
                return findMaxOffset(parent.getLeftChild(), offset, findLeft);
            }
            if (!findLeft && parent.getRightChild() != null) {
                return findMaxOffset(parent.getRightChild(), offset, findLeft);
            }
            return offset;
        }
    
        public interface TreeNode {
    
            String getPrintInfo();
    
            TreeNode getLeftChild();
    
            TreeNode getRightChild();
        }
    
    }
    

    使用

    要实现打印需要有两步,

    第一步

    让你的Node类实现TreePrintUtil中的TreeNode接口

        public interface TreeNode {
            /**
             * 需要打印的信息
             * @return
             */
            String getPrintInfo();
    
            TreeNode getLeftChild();
    
            TreeNode getRightChild();
        }

    实现如下

    private static class Node<K extends Comparable<K>, V> implements TreeNode {
            K k;
            V v;
            Node left, right;
    
            public Node(K k, V v) {
                this.k = k;
                this.v = v;
            }
    
            @Override
            public String toString() {
                return "[" + k + "]";
            }
    
            @Override
            public String getPrintInfo() {
    
                return toString();
            }
    
            @Override
            public TreeNode getLeftChild() {
                // TODO Auto-generated method stub
                return left;
            }
    
            @Override
            public TreeNode getRightChild() {
                // TODO Auto-generated method stub
                return right;
            }
    
        }

    第二步

    返回根元素

        public Node getRoot() {
            return root;
        }
    

    使用如下

    package com.zgh.algorithm.search;
    
    public class Demo2 {
        public static void main(String[] args) {
            BST<Integer, String> bst = new BST<>();
            bst.insert(10, "a");
            bst.insert(12, "b");
            bst.insert(3, "d");
            bst.insert(9, "cdd");
            bst.insert(33, "cff");
            bst.insert(38, "ceee");
            bst.insert(1, "aaaa");
            bst.insert(0, "dddd");
            bst.insert(99, "dddd");
            bst.insert(100, "dddd");
            bst.insert(7, "dddd");
            bst.insert(1, "dddd");
            //从根开始打印
            TreePrintUtil.pirnt(bst.getRoot());
    
        }
    }
    
    展开全文
  • GoTree: 简单的Go模块用于在终端中打印树形结构
  • 数据结构课程设计实验2 打印树形结构.docx
  • 树实现和树形打印

    2018-07-24 21:19:18
    功能一:按照树形打印二叉树,型如: 8 7 11 4 9 10 15 功能2:实现创建一个有序的二叉树 功能3:实现平衡二叉树,对所创建的二叉树进行左旋和右旋,直到成为平衡二叉树。 功能3:按照树中数据删除某个节点,...
  • 这两天整理数据文件的时候发现,一层层的点击文件夹查看很繁琐,于是想写一个工具来递归打印出文件目录的树形结构,网上找了一些资料几乎都是使用的os.walk, 调试了以后发现返回的貌似的是一个“生成器”,只需要for...
  • 100行C代码终端打印树形结构

    千次阅读 2017-02-08 09:35:59
    为什么要打印树形结构 树形结构是算法里很常见的一种数据结构,从二叉树到多叉树,还有很多变种。很多涉及到算法的工作,就需要程序员自己手动实现树形结构,但出于结构本身复杂性,不太容易做对,需要一种调试工具...
    摘要: 这是一篇讲究套路的数据结构实战教学文,阅读需要约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堆栈;换行输出就是树的分支遍历,就是每一轮循环。输出内容主要是三个符号:缩进、分支和节点内容。我们作如下策略:

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

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

    <center>MIB树</center>

    B+树

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

    </center> 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>红黑树</center>

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


    转自:https://my.oschina.net/fullofbull/blog/832921

    展开全文
  • 使用递归算法打印文件树形结构

    使用递归算法打印文件树形结构

    思想:使用一个静态变量用于记录文件遍历的深度,然后使用一个静态集合容器装入每次迭代前的需要在路径名前输出的树形特殊结构,最后开始遍历文件数组,先判断该文件路径是不是最后一个路径名,如果不是就使用迭代持续迭代遍历,非路径的先判断其是不是最后一个文件,根据结果的的不同选择输出不同的文件树形结构

    实现代码:

    package com.filepath;
    
    import java.io.File;
    import java.util.LinkedList;
    
    public class FilePathTest02 {
    	
    	//用于记录文件路径深度
    	public static int pathDeep=0;
    	
    	private static LinkedList<String> fileList=new LinkedList<String>();
    	//文件路径打印
    	public void printFilePath(File file) {
    		//判断当前文件或路径是否存在
    		if(file.exists()) {
    			//生成一个文件数组
    			File[] fileArr=file.listFiles();
    			pathDeep++;
    			// 遍历每行时,将其分成两部分:行首和File部分。
    			// 其中File部分要先判断是目录还是文件,再判断是否是当前目录最后的一个File,在Filename前打印出相应的符号
    						
    			for(File f:fileArr) {
    				// 输出行首
    				for(int i=0;i<pathDeep-1;i++) {
    					System.out.print(fileList.get(i));
    				}
    				
    				//判断当前文件是否是路径
    				if(f.isDirectory()) {
    					//判断是不是最后一个目录
    					if(fileArr[fileArr.length-1].equals(f)) {
    						//是最后一个目录时
    						System.out.print("└─");
    						fileList.add(pathDeep-1,"  ");
    					}else {
    						//非最后一个目录时
    						fileList.add(pathDeep-1,"│ ");
    						System.out.print("├─");
    					}
    					//输出此时目录的名字
    					System.out.println(f.getName());
    					//递归遍历
    					printFilePath(f);
    					
    					//如果不是目录而是文件
    				}else {
    					//先判断当前文件是不是最后一个文件
    					if(fileArr[fileArr.length-1].equals(f)) {
    						System.out.print("└─");
    					}else {
    						System.out.print("├─");
    					}
    					System.out.println(f.getName());
    				}
    			}
    			
    		}else {
    			System.out.println("文件或路径不存在...");
    		}
    		pathDeep--;
    		
    	}
    
    	
    	public static void main(String[] args) {
    		File file=new File("E:\\0610课件与开发软件");
    		System.out.println(file.getName());
    		new FilePathTest02().printFilePath(file);
    	}
    }
    

    运行效果:

    运行效果

    展开全文
  • 树形结构的调试打印

    千次阅读 2017-02-09 17:23:01
    为什么要打印树形结构 树形结构是算法里很常见的一种数据结构,从二叉树到多叉树,还有很多变种。很多涉及到算法的工作,就需要程序员自己手动实现树形结构,但出于结构本身复杂性,不太容易做对,需要一种调试工具...

    这是一篇讲究套路的数据结构实战教学文,阅读需要约 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 交换了一下次序,右孩子就先于左孩子输出了,这样一来你就可以歪着脑袋直观地看二叉树了(笑),同时我们还知道,“翻转”一棵二叉树是多么容易(笑)。

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

    参考源码

    目录树B+树红黑树

    展开全文
  • 按照树形结构直观地打印出一棵二叉树(Java)

    千次阅读 多人点赞 2019-04-28 20:58:09
    在我们完成一棵的构建之后,如果我们想要看这棵结构,不像数组或者List等数据结构,我们可以非常方便地用各种方式将其中的所有元素打印出来,对于而言,这个过程要麻烦得多,我们可以用各种遍历方式得到这棵...
  • const list = [{ id: 1001, parentId: 0, name: 'AA' }, { id: 1002, parentId: 1001, name: 'BB' }, { id: 1003, parentId: 1001, name: 'CC' ... {
  • js 输出树形结构

    千次阅读 2018-06-22 15:15:37
    &lt;!DOCTYPE html&gt; &lt;html&gt; &lt;head&gt; &lt;meta charset="UTF-8"&gt; &lt;title&gt;&lt;/title&gt; &lt;...&am
  • php 数组转换成树形结构输出代码php 数组转换成树形结构输出代码php 数组转换成树形结构输出代码
  • 打印树形图(二叉树)

    千次阅读 2020-09-04 14:16:39
    控制台打印树形图(二叉树) 在读leetcode第337题时,发现题目中的二叉树排列的很规整、漂亮,如下: 示例一: 输入: [3,2,3,null,3,null,1] 3 / \ 2 3 \ \ 3 1 输出: 7 示例二: 输入: [3,4,5,1,3,null,1]...
  • 直观的打印树结构

    2020-05-12 00:49:04
    屏幕中输出一棵,为后续和相关的问题做准备。 #include <iostream> #include <iomanip> #include <vector> #include <map> using namespace std; int gDataWidth = 2; // 数据宽度 ...
  • 【问题描述】: 按凹入表的形式打印二叉树结构。...对于用户输入的树形结构,程序能够以凹入表的形式将其打印 二叉树的根在屏幕的最左边,二叉树的左子树在屏幕的下面,二叉树的右子树在屏幕的上面。
  • 工作中不时会遇见对树形结构数据的处理,有时候只需要遍历并获取其中一个属性值就行了(这部分内容请参考笔者的另一篇博客JS遍历树形结构方法),有时候我们则需要根据某些条件去过滤并得到新的树形结构数据。...
  • #include #include #include #define NUM 5 typedef struct _node { int value; struct _node *left; struct _node *right; }TNode,*Tree;...//add a *next in q_node is my purpose //other wise , we need
  • 《UVM实战》——3.1节UVM的树形结构

    千次阅读 2017-07-03 10:23:00
    本节书摘来自华章社区《UVM实战》一书中的第3章,第3.1节UVM的树形结构,作者 张 强,更多章节内容可以访问云栖社区“华章社区”公众号查看 3.2 UVM的树形结构在第2章中曾经提到过,UVM采用树形的组织结构来管理...
  • //调用打印树的方法  function printTree(n,m){  for(var i=1;i;i++){//打印树冠  print(i);//调用打印*号  if(i!=n){  document.write(" ");//最后一次打印完不换行  }  }  document....
  • 习题集解析部分第6章 和二叉树——《数据结构题集》-严蔚敏.吴伟民版相关测试数据下载 链接☛本习题文档的存放目录:数据结构▼配套习题解析▼06 和二叉树文档中源码的存放目录:数据结构▼配套习题解析▼06 ...
  • Ubuntu查看目录树形结构

    千次阅读 2018-01-11 18:27:00
    2019独角兽企业重金招聘Python工程师标准>>> ...
  • import java.io.*; import java.util.*; public class VisualDirectory { private static int times; public static void deepList(File file) { if(file.isFile()||file.listFiles().length==0) ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 31,451
精华内容 12,580
关键字:

打印树形结构