四川盐亭网站制作公司

打印一棵类似于文件管理器中（tree命令下）的文件目录树的二叉树-创新互联

cmd命令行下，通过tree命令可打印当前文件夹的一棵文件目录树，如左下图

成都创新互联公司专业为企业提供西盟网站建设、西盟做网站、西盟网站设计、西盟网站制作等企业网站建设、网页设计与制作、西盟企业网站模板建站服务，十余年西盟做网站经验，不只是建网站，更提供有价值的思路和整体网络服务。

那么如何实现打印一棵类似于上述样式的二叉树呢，如右上图（靠上方为左子树）

这样的一棵二叉树可以分解成以下几个组成部分：

"│   "，         打印根节点的左子树结点的值前，在其左侧需要打印的格式控制部分

"    "、          打印根节点的右子树结点的值前，在其左侧需要打印的格式控制部分

"├── "、     即将打印根节点的左子树结点的值前，在其左侧需要打印的表示部分

"└── "、     即将打印根节点的左子树结点的值前，在其左侧需要打印的表示部分

值（除值外，均占用四个空格位置）

由于打印不可以后退，只能是从左到右，所有在打印值前，必须将值前的所有格式控制符均打印出来后，再将值打印出来。

而处于左子树或者是右子树时，所需打印的格式控制符不同，所以采用了一个char类型的数组用于指示位于父节点的左“L”或右子树“R”，祖先节点的左或右子树......(此处使用的是全局变量数组，若使用局部变量数组，需要再函数参数中多加一个字符数组参数)

函数的另一个参数depth则是指示递归到当前节点的深度（设置第一层为0），初始调用时值为0

函数体中：

一、第一个if语句中用于打印输出值前的格式控制符：

其中的for语句，在depth>=2时该句块被执行，当leftOrRight[i]=='L'时，说明该节点位于i层祖先节点的左子树处，应该打印"│   "；当leftOrRight[i]=='R'时，说明该节点位于i层祖先节点的右子树处，应该打印"    "

其中的if-else语句中，在depth>=1时该句块被执行，当leftOrRight[depth-1] == 'L'，说明该节点位于其父节点的左子树，应该打印"├── "；当leftOrRight[depth-1] == 'R'，说明该节点位于其父节点的右子树，应该打印"└── "

二、打印完其左侧格式控制部分后，若该节点为空则打印(null)，输出后return退出该层递归。否则则输出该节点的值，若其左右子树不为空，则需要进行其左右子树的递归打印

  1. leftOrRight[depth] = 'L'，把该子树的标记位设为'L'，表明以下往的是该结点的左子树递归，再递归调用该函数 outputTree(root->left, depth + 1)，depth+1表明往下递归深度加1

  2. 当 leftOrRight[depth] = 'R'时，表明返回到该层时，说明该结点左子树已经输出完毕，该子树的标记位设为'R',该向右子树遍历，outputTree(root->right, depth + 1);

调用方式：

cout<< "该树的树状结构为：(靠近上方为左子树)"<< endl;
outputTree(root, 0);

代码如下：

char leftOrRight[100] = { 'L' }; //全局变量
void outputTree(TreeNode* root, int depth) {
    //树根结点没有其他输出
    if (depth>0) {
        for (int i = 0; i<= depth - 2; i++) { //当深度大于2时才会有该深度结点左边的格式("│   "还是 "    ")输出
            if (leftOrRight[i] == 'L') cout<< "│   "; //共4个符号位
            else cout<< "    ";
        }
        //深度大于1即可有该输出，且是通过观察其母结点刚开始左边(输出"├── ")or已经遍历完左边开始右边("└── ")
        if (leftOrRight[depth-1] == 'L') cout<< "├── ";
        else cout<< "└── ";
    }
    
    if (root == NULL) {
        cout<< "(null)"<< endl;
        return;
    }
    //不为空则输出其结点值并换行
    cout<< root->val<< '\n';
    //若该结点左右为空则没必要往下递归
    if (root->left == NULL && root->right == NULL) return;

    //开始进行该结点的左右子树的递归，先把该子树的标记位设为'L',表明往的是该树的左子树递归
    leftOrRight[depth] = 'L';
    //往下递归深度加1
    outputTree(root->left, depth + 1);
    //返回到该层时，说明该结点左子树已经输出完毕，该子树的标记位设为'R',该向右子树遍历
    leftOrRight[depth] = 'R';

    outputTree(root->right, depth + 1);
}

其实这种用数组的方式来存储该结点位于其父结点、祖先节点的左或右子树的方式，也可以用于进行哈夫曼（霍夫曼）编码

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


网站名称：打印一棵类似于文件管理器中（tree命令下）的文件目录树的二叉树-创新互联
转载来于：http://scyanting.com/article/dshcps.html

其他资讯