精华内容
下载资源
问答
  • 打印二叉树

    2021-01-16 23:20:59
    该程序是根据先序序列打印二叉树,如果先序遍历过程中下一个结点为空结点则用空格表示。程序源码在最后。 实现思路 首先想到要把二叉树打印出来,最简单的表现形式是把一个层序遍历(代码中的tree字符串)的二叉树...

    概述

    该程序是根据先序序列打印二叉树,如果先序遍历过程中下一个结点为空结点则用空格表示。程序源码在最后。

    实现思路

    1. 首先想到要把二叉树打印出来,最简单的表现形式是把一个层序遍历(代码中的tree字符串)的二叉树打印;首先实现这个功能(程序中print_BiTree函数中init_str(str, 0, 0, strlen(str));之后的部分),实现这个功能需要首先对布局有一定的判断,即如何能将任意深度的二叉树都堆成的摆在一个平面上;
      例如:不管是打印深度3还是深度5都保证整个图形的对称。
      在这里插入图片描述

    在这里插入图片描述
    2. 将层序遍历中某些点去掉,再次打印出正确的树(即合理的删除结点以及斜杠);
    3. 最后就是利用给定的先序遍历序列对层序遍历的序列进行初始化即init_str()。如果要根据其他序列打印二叉树,即重写init_str()函数即可。

    代码

    #include <stdio.h>
    #include <math.h>
    #include <string.h>
    
    char tree[100];
    int idx = 0;
    
    int get_tree_space(int line) {
        if (line == 2) {
            return 2;
        } else {
            return 2 * get_tree_space(line - 1) + 1;
        }
    }
    
    int get_slash_space(int line) {
        return 4 + (pow(2, line - 3) - 1) * 6;
    }
    
    int get_slash_md_sp(int line) {
        return (pow(2, line - 2) - 1) * 6 + 3;
    }
    void init_str(char str[], int i, int n, int length) {
        if (str[idx] == ' ') {
            return;
        }
        tree[n] = str[idx];
        init_str(str, idx++, 2 * n + 1, length);
        init_str(str, idx++, 2 * n + 2, length);
    }
    
    void print_BiTree(char str[]) {
        for (int i = 0; i < 100; i++) {
            tree[i] = '#';
        }
        init_str(str, 0, 0, strlen(str));
        int n = strlen(tree);
        for (int i = 0; i < 100; i++) {
            if (tree[i] != '#') {
                n = i + 1;
            }
        }
        int line_num = 0;
        for (; pow(2, line_num) - 1 < n; line_num++) {}
        int line = line_num - 1;
        for (int i = 0; line_num > 1; line_num--, i++) {
            int start_space_num = get_tree_space(line_num), space_of_two_point = get_tree_space(line_num + 1);
            for (int j = 0; j < start_space_num; j++)printf(" ");
            for (int j = pow(2, i) - 1; j < pow(2, i + 1) - 1; j++) {
                if (tree[j] != '#') {
                    printf("%c", tree[j]);
                } else {
                    printf(" ");
                }
                for (int k = 0; k < space_of_two_point; k++)printf(" ");
            }
            printf("\n");
            int start_sp = get_slash_space(line_num), middle_sp = get_slash_md_sp(line_num);
            int slash_num = pow(2, i);
            for (int j = 0; j < start_sp; j++)printf(" ");
            for (int j = 0; j < slash_num; j++) {
                int slash_to_tree_index = pow(2, i) - 1 + j;
                if (tree[slash_to_tree_index] != '#' && tree[2 * slash_to_tree_index + 1] != '#' &&
                    2 * slash_to_tree_index + 1 < n) {
                    printf("/");
                } else {
                    printf(" ");
                }
                printf(" ");
                if (tree[slash_to_tree_index] != '#' && tree[2 * slash_to_tree_index + 2] != '#' &&
                    2 * slash_to_tree_index + 2 < n) {
                    printf("\\");
                } else {
                    printf(" ");
                }
                for (int k = 0; k < middle_sp; k++)printf(" ");
            }
            printf("\n");
        }
        for (int i = pow(2, line) - 1; i < n; i += 2) {
            if (tree[i] != '#') {
                printf("%c", tree[i]);
            } else {
                printf(" ");
            }
            if (i + 1 < n) {
                if (tree[i + 1] != '#') {
                    printf("   %c ", tree[i + 1]);
                } else {
                    printf("     ");
                }
            }
        }
    
    }
    
    int main() {
        char str[100];
        gets(str);
        print_BiTree(str);
        return 0;
    }
    //测试样例:f后有三个空格,如果没有会出错
    //abc  de g  f
    
    
    
    展开全文
  • 第四届蓝桥杯决赛 java高职高专组 第四题横向打印二叉树二叉树可以用于排序。其原理很简单:对于一个排序二叉树添加新节点时,先与根节点比较,若小则交给左子树继续处理,否则交给右子树。当遇到空子树时,则把该...

    第四届蓝桥杯决赛 java高职高专组 第四题

    横向打印二叉树

    二叉树可以用于排序。其原理很简单:对于一个排序二叉树添加新节点时,先与根节点比较,若小则交给左子树继续处理,否则交给右子树。

    当遇到空子树时,则把该节点放入那个位置。

    比如,10 8 5 7 12 4 的输入顺序,应该建成二叉树如图1所示。

    本题目要求:根据已知的数字,建立排序二叉树,并在标准输出中横向打印该二叉树。

    输入数据为一行空格分开的N个整数。 N<100,每个数字不超过10000。

    输入数据中没有重复的数字。

    输出该排序二叉树的横向表示。 对应上例中的数据,应输出:

    |-12

    10-|

    |-8-|

    |   |-7

    |-5-|

    |-4

    为了便于评卷程序比对空格的数目,请把空格用句点代替:

    ...|-12

    10-|

    ...|-8-|

    .......|...|-7

    .......|-5-|

    ...........|-4

    例如:

    用户输入:

    10 5 20

    则程序输出:

    ...|-20

    10-|

    ...|-5

    再例如:

    用户输入:

    5 10 20 8 4 7

    则程序输出:

    .......|-20

    ..|-10-|

    ..|....|-8-|

    ..|........|-7

    5-|

    ..|-4

    资源约定:

    峰值内存消耗(含虚拟机) < 64M

    CPU消耗  < 1000ms

    1 importjava.util.Scanner;2

    3

    4 public class横向打印二叉树 {5 /**

    6 * 节点7 */

    8 static classNode{9 //值

    10 intdata;11 Node left;12 Node right;13 //输出的值

    14 String s;15 public Node(inte){16 this.data=e;17 }18 }19

    20 public static voidmain(String[] args) {21 //int[] n = { 34, 31, 36, 47, 23, 35, 41, 14, 12, 15, 7, 10, 8, 5, 12, 7, 3, 6 };

    22 int[] n=getInput();23 Node root=new Node(n[0]);24 root.s=root.data+"-|";25

    26 for(int i=1;iroot.data){29 addRight(node, root,0);30 }else{31 addLeft(node,root,0);32 }33 }34

    35 print(root);36 }37 /**

    38 * 接收输入39 *@return

    40 */

    41 public static int[] getInput(){42 Scanner scan=newScanner(System.in);43 String s=scan.nextLine();44 String[] ss=s.split(" ");45 int[] nn=new int[ss.length];46 for(int i=0;i

    52 * 打印53 *@paramnode 根节点54 */

    55 public static voidprint(Node node){56 //始终先打印右节点,然后打印本身,最后打印左节点

    57 if(node.right!=null){58 print(node.right);59 }60 //如果没有子节点,就不打印后面的"-|“

    61 if(node.left==null&&node.right==null){62 System.out.println(node.s.substring(0, node.s.length()-2));63 }else{64 System.out.println(node.s);65 }66 if(node.left!=null){67 print(node.left);68 }69 }70 /**

    71 * 添加右节点72 *@paramnode 子节点73 *@paramroot 父节点74 *@paramflag 括号层数(0 只有一层括号,1 有多层括号)75 */

    76 public static void addRight(Node node,Node root,intflag){77 if(root.right==null){78 node.s=root.s.replaceAll("[0-9]|-", ".").substring(0, root.s.length()-1);79 if(flag==0){80 int index=node.s.lastIndexOf("|");81 if(index!=-1){82 node.s=node.s.substring(0,index)+"."+node.s.substring(index+1);83 }84 }85 node.s+="|-"+node.data+"-|";86

    87 root.right=node;88 }else if(node.data>root.right.data){89 addRight(node, root.right,0);90 }else{91 addLeft(node,root.right,1);92 }93 }94 /**

    95 * 添加左节点96 *@paramnode 子节点97 *@paramroot 父节点98 *@paramflag 括号层数(0 只有一层括号,1 有多层括号)99 */

    100 public static void addLeft(Node node,Node root,intflag){101 if(root.left==null){102 node.s=root.s.replaceAll("[0-9]|-", ".").substring(0, root.s.length()-1);103 if(flag==0){104 int index=node.s.lastIndexOf("|");105 if(index!=-1){106 node.s=node.s.substring(0,index)+"."+node.s.substring(index+1);107 }108 }109 node.s+="|-"+node.data+"-|";110 root.left=node;111 }else if(node.data>root.left.data){112 addRight(node, root.left,1);113 }else{114 addLeft(node,root.left,0);115 }116 }117 }

    版权声明:本文为博主原创文章,未经博主允许不得转载。

    展开全文
  • 从上往下打印二叉树题目:从上往下打印出二叉树的每个结点,同一层的结点按照从左向右的顺序打印。二叉树结点的定义:public static class BinaryTreeNode {int value;BinaryTreeNode left;BinaryTreeNode right;}...

    从上往下打印二叉树

    题目:从上往下打印出二叉树的每个结点,同一层的结点按照从左向右的顺序打印。

    二叉树结点的定义:

    public static class BinaryTreeNode {

    int value;

    BinaryTreeNode left;

    BinaryTreeNode right;

    }

    解题思路:

    这道题实质是考查树的遍历算法。从上到下打印二叉树的规律:每一次打印一个结点的时候,如果该结点有子结点, 则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点,重复前面的打印操作,直至队列中所有的结点都被打印出来为止。

    代码实现:

    public class Test23 {

    /**

    * 二叉树的树结点

    */

    public static class BinaryTreeNode {

    int value;

    BinaryTreeNode left;

    BinaryTreeNode right;

    }

    /**

    * 从上往下打印出二叉树的每个结点,向一层的结点按照从左往右的顺序打印。

    * 例如下的二叉树,

    * 8

    * / \

    * 6 10

    * / \ / \

    * 5 7 9 11

    * 则依次打印出8、6、10、5、3 、9、11.

    *

    * @param root 树的结点

    */

    public static void printFromToBottom(BinaryTreeNode root) {

    // 当结点非空时才进行操作

    if (root != null) {

    // 用于存放还未遍历的元素

    Queue list = new LinkedList<>();

    // 将根结点入队

    list.add(root);

    // 用于记录当前处理的结点

    BinaryTreeNode curNode;

    // 队列非空则进行处理

    while (!list.isEmpty()) {

    // 删除队首元素

    curNode = list.remove();

    // 输出队首元素的值

    System.out.print(curNode.value + " ");

    // 如果左子结点不为空,则左子结点入队

    if (curNode.left != null) {

    list.add(curNode.left);

    }

    // 如果右子结点不为空,则左子结点入队

    if (curNode.right != null) {

    list.add(curNode.right);

    }

    }

    }

    }

    public static void main(String[] args) {

    // 8

    // / \

    // 6 10

    // / \ / \

    // 5 7 9 11

    BinaryTreeNode root = new BinaryTreeNode();

    root.value = 8;

    root.left = new BinaryTreeNode();

    root.left.value = 6;

    root.left.left = new BinaryTreeNode();

    root.left.left.value = 5;

    root.left.right = new BinaryTreeNode();

    root.left.right.value = 7;

    root.right = new BinaryTreeNode();

    root.right.value = 10;

    root.right.left = new BinaryTreeNode();

    root.right.left.value = 9;

    root.right.right = new BinaryTreeNode();

    root.right.right.value = 11;

    printFromToBottom(root);

    // 1

    // /

    // 3

    // /

    // 5

    // /

    // 7

    // /

    // 9

    BinaryTreeNode root2 = new BinaryTreeNode();

    root2.value = 1;

    root2.left = new BinaryTreeNode();

    root2.left.value = 3;

    root2.left.left = new BinaryTreeNode();

    root2.left.left.value = 5;

    root2.left.left.left = new BinaryTreeNode();

    root2.left.left.left.value = 7;

    root2.left.left.left.left = new BinaryTreeNode();

    root2.left.left.left.left.value = 9;

    System.out.println("\n");

    printFromToBottom(root2);

    // 0

    // \

    // 2

    // \

    // 4

    // \

    // 6

    // \

    // 8

    BinaryTreeNode root3 = new BinaryTreeNode();

    root3.value = 0;

    root3.right = new BinaryTreeNode();

    root3.right.value = 2;

    root3.right.right = new BinaryTreeNode();

    root3.right.right.value = 4;

    root3.right.right.right = new BinaryTreeNode();

    root3.right.right.right.value = 6;

    root3.right.right.right.right = new BinaryTreeNode();

    root3.right.right.right.right.value = 8;

    System.out.println("\n");

    printFromToBottom(root3);

    // 1

    BinaryTreeNode root4 = new BinaryTreeNode();

    root4.value = 1;

    System.out.println("\n");

    printFromToBottom(root4);

    // null

    System.out.println("\n");

    printFromToBottom(null);

    }

    }

    运行结果:

    431c9f7319ae0a0860e6dfbc055319a8.png

    展开全文
  • 分享一个横向打印二叉树图形的方法分享一个横向打印二叉树图形的方法最近想起之前大二学数据结构时测试B树时写了一个打印二叉树的C语言函数,现在突然想把它记录一下,改成打印二叉树的Java实现效果上图的二叉树打印...

    分享一个横向打印二叉树图形的方法

    分享一个横向打印二叉树图形的方法

    最近想起之前大二学数据结构时测试B树时写了一个打印二叉树的C语言函数,现在突然想把它记录一下,改成打印二叉树的Java实现

    效果

    5f37786a4862c65d117365c7f69d81db.png

    上图的二叉树打印效果如下

    3cfc2481d4238a5908cb62b54349198b.png

    解释一下这个图,将图顺时针旋转90°,看见有两种箭头

    短箭头表示这是一个值,即该节点的值

    长箭头指向该节点的子树,长箭头在值的左边,则指向左子树,在值的右边则指向右子树

    算法分析

    这个算法按行打印,每一个节点,子树和值在同一个“平台”上(“平台”只他们在的一条线上),先打印右子树(有的话),再打印值,再打印左子树(有的话),打印子树时,又是按照这样的策略(先右再值再左),麻烦在于打印完一个节点的一个部分后,打印下一个部分在下一行,在打印的过程中,可能需要打印祖先节点的“平台”,也可能不用,用不用由这个条件判断:该节点在该祖先节点的子树是否是该祖先节点最后一个需要打印的子树,在二叉树里,就是指左子树。

    如节点3在节点2的右子树上,右子树不是节点2最后需要打印的子树,所以需要打印节点3时(包括子树和值),需要打印节点2的平台

    如节点0在节点2和节点1的左子树上,左子树是最后一个需要打印的子树,那么就不打印它们的平台

    那么在打印某一个节点,都需要在新的一行开始,那么怎么知道某个祖先节点的平台是否需要打印呢:用一个List存起来,里面的值为从根节点开始,每一个祖先节点是否需要打印平台(打印的子树是否是最后打印的子树),需要在遍历的过程中,由每个祖先节点放入。

    代码实现

    //树的定义

    class TreeNode {

    int val = 0;

    TreeNode left = null;

    TreeNode right = null;

    public TreeNode(int val) {

    this.val = val;

    }

    }

    //打印算法

    public void printTree(TreeNode t){

    printTree(t, new ArrayList<>());//调用重载方法

    }

    private void printTree(TreeNode t,ArrayList isLast){

    if (t == null) {

    return;

    }

    //打印新节点先打印一下平台

    System.out.println("|");

    //右子树

    if (t.right != null){

    //打印祖先节点的平台

    printBranch(isLast);

    //打印指向子树的箭头

    System.out.print("|------>");

    //打印的不是该节点最后的子树

    isLast.add(false);

    //先递归打印右子树

    printTree(t.right, isLast);

    //打印完去掉刚刚加入的判断依据,不影响后面

    isLast.remove(isLast.size()-1);

    }

    //打印指也要打印祖先节点的平台

    printBranch(isLast);

    System.out.println("|->"+t.val);

    //打印左子树,和右子树差不多

    if (t.left != null) {

    printBranch(isLast);

    System.out.print("|------>");

    //这里加入true,表示是最后打印的子树

    isLast.add(true);

    printTree(t.left, isLast);

    isLast.remove(isLast.size()-1);

    }

    }

    private void printBranch(ArrayList isLast) {

    for (int i = 0; i < isLast.size(); i++) {

    if (isLast.get(i)) {

    //不打印平台就打印个空格占位

    System.out.print(" ");

    } else {

    //打印平台

    System.out.print("|");

    }

    //用于对齐指向子树的箭头

    System.out.print(" ");

    }

    }

    分享一个横向打印二叉树图形的方法相关教程

    ffly-plus 又又又一个`gin` demo项目,带你快速上手用`gin`进行`

    ffly-plus 又又又一个`gin` demo项目,带你快速上手用`gin`进行`web`开发!!!! ffly-plus 又又又一个 gin demo项目,带你快速上手用 gin 进行 web 开发, 在这个demo项目中,你可以学到项目结构设计、 gorm 的使用、 gin 中间件的编写、 DB 设计规范、 Swagger

    Spring Boot | 使用IntelliJ IDEA 2020从零开始搭建一个springbo

    Spring Boot | 使用IntelliJ IDEA 2020从零开始搭建一个springboot项目(详细+坑点) 本文写给第一次使用IDEA搭建springboot项目的萌新们。 网上相关的教程也很多了,但自己在实际跟着操作的过程中还是碰到了一些问题,因此记录下来,希望能帮助到大家~ 最后

    Linux下一个基于socket的简单并发服务器实现

    Linux下一个基于socket的简单并发服务器实现 #include stdio.h#include stdlib.h#include unistd.h#include signal.h#include sys/wait.h#include arpa/inet.h#include sys/socket.h#define BUF_SIZE 30void error_handling(char* message){ fputs(message, s

    VS2015+QT5.9.2开发一个adb_tool.exe工具(二)

    VS2015+QT5.9.2开发一个adb_tool.exe工具(二) VS2015+QT5.9.2开发一个adb_tool.exe工具(二) 前言 开发思路 原型图 编码 总结 上一次做完adb_tool.exe的demo之后,本来想先研究一下单元测试,但是又来了几个需求说需要一个开机自启动、卸载和重启手机的功

    关于h5,页面分享到朋友圈、钉钉、微信等,(base64图片转换成文

    关于h5,页面分享到朋友圈、钉钉、微信等,(base64图片转换成文件) 实现内容:将页面分享到朋友圈、钉钉、微信。 主要思想如图: div class=header-right @click=shareDetail分享/div /** * 分享链接(微信、朋友圈、钉钉、工作圈) */ async shareDetail()

    使用位运算求和

    使用位运算求和 今天为大家分享一道本应很简单的题目,但是却因增加了特殊条件,而大幅增加了难度。话不多说,直接看题。 该题很容易出现在各大厂的面试中,属于必须掌握的题型。 连续n个数的和 求 1 2 … n ,要求不能使用乘除法、for、while、if、else、swi

    Java - 模拟一个Jedis客户端连接工具

    Java - 模拟一个Jedis客户端连接工具 手写一个简单的Redis连接工具 既然要连接Redis服务端,那么我们就要先知道客户端与redis服务端的通信协议 protocol 是怎么约定的. 通过查阅redis官方相关资料后发现 文章所涉及的代码: https://gitee.com/isidea/example-r

    快速失败和安全失败

    快速失败和安全失败 一、快速失败 在使用迭代器遍历一个集合对象时,如果遍历过程中对集合对象的结构进行了修改,比如说增加或者删除操作,那么会抛出ConcurrentModificationException 迭代器在遍历时直接访问集合中的内容,并且在遍历过程中使用一个 modCoun

    展开全文
  • C语言打印二叉树

    2014-03-25 16:51:35
    打印二叉树,高度为4内的,可完美打印二叉树
  • 摘要:这篇Java开发技术栏目下的“Java实现打印二叉树所有路径的方法”,介绍的技术点是“二叉树所有路径、Java、二叉树、路径、实现、方法”,希望对大家开发技术学习和问题解决有帮助。本文实例讲述了Java实现打印...
  • 剑指Offer_编程题——按之字形顺序打印二叉树题目描述:请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。...
  • 打印二叉树的左边界Problem statement: Given a binary tree, print the boundary sum of the tree. 问题陈述:给定二叉树,打印树的边界和。 Solution: 解: First of all we need to understand what the ...
  • 分行打印二叉树,使用队列 之字形打印二叉树,使用两个栈 #include<iostream> #include<deque> #include<stack> using namespace std; struct BinaryTreeNode { int m_nValue; ...
  • 题目描述:将二叉树从上到下按层打印二叉树,同一层结点从左至右输出,每一层输出一行 思路: 1、二叉树的广度优先遍历,使用队列实现 2、二叉树每一层输出一行,需要一个变量来统计每一行的结点数 public ...
  • 从上到下按层打印二叉树,同层的从左到右打印。打印多行。分析:可以想到层次遍历,借助队列存储结点;但是要打印成多行,所以必须设计两个变量,来表示当前打印的行的个数,和下一行打印的个数。void PrintBinary...
  • 剑指Offer_编程题——从上往下打印二叉树题目描述:从上往下打印出二叉树的每个节点,同层节点从左至右打印具体要求:时间限制: C/C++ 1秒,其他语言2秒空间限制: C/C++32M,其他语言64M具体思路:背景知识介绍 ...
  • 题目一: 从上往下打印出二叉树的每个节点,同层节点从左至...请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
  • 分层打印二叉树

    2019-09-04 14:39:34
    title: 2019-8-19 分层打印二叉树 tags: 算法,每日一题,二叉树 分层打印二叉树 1. 题目描述 从上往下打印出二叉树的每个节点,同层节点从左至右打印。 2. 题目解析 这题比较简单,就是将二叉树从根节点开始依次从...
  • 题目描述请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。思路:核心/考点:层级遍历二叉树、BFS。变形:奇数...
  • 剑指offer编程题按层打印二叉树即上到下按层打印二叉树java实现(二叉树,队列)
  • 横向打印二叉树

    2017-12-29 22:04:02
    历届试题 横向打印二叉树
  • [剑指offer]从上到下打印二叉树III 剑指offer-从上到下打印二叉树III 题目描述 请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的...
  • 层次打印二叉树

    2019-11-12 15:10:24
    1从上往下打印二叉树 题目描述: 从上往下打印出二叉树的每个节点,同层节点从左至右打印。 例如,以下二叉树层次遍历的结果为:1,2,3,4,5,6,7 解析: public ArrayList<Integer> PrintFromTopToBottom...
  • 面试题32-2:分行层序打印二叉树 从上到下按层打印二叉树,同一层的结点按从左到右的顺序打印,每一层打印到一行。 分行打印,用两个变量一个指示当前行结点数,一个指示下一行结点数。在队列里入栈和出栈时就能...
  • 从上到下打印二叉树 从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。 面试题32 - II. 从上到下打印二叉树 II 从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,155
精华内容 4,462
关键字:

打印二叉树