Bagaimana cara mencetak diagram pohon biner?

163

Bagaimana saya bisa mencetak pohon biner di Jawa sehingga hasilnya seperti:

   4 
  / \ 
 2   5 

Simpul saya:

public class Node<A extends Comparable> {
    Node<A> left, right;
    A data;

    public Node(A data){
        this.data = data;
    }
}
Tian
sumber
5
Itu yang rumit. Saya pikir Anda harus menentukan kedalaman pohon terlebih dahulu. Secara pribadi, saya hanya akan membuang graph node ke graphviz dan membiarkannya menghadapinya. :-)
Omnifarious
Sepertinya jika Anda memiliki banyak elemen, elemen root akan memiliki tepi BESAR yang berasal darinya.
Saya punya metode getDept () di pohon
Tian
1
Hanya karena ide itu menghibur saya, saya menulis kode dalam C ++ dan memuntahkannya format grafik Graphviz. Pohon-pohon yang diformat dengan indah.
Mahakuasa
vanya.jp.net/vtree
humble_wolf

Jawaban:

238

Saya telah membuat printer pohon biner sederhana. Anda dapat menggunakan dan memodifikasinya seperti yang Anda inginkan, tetapi itu tetap tidak dioptimalkan. Saya pikir banyak hal dapat diperbaiki di sini;)

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BTreePrinterTest {

    private static Node<Integer> test1() {
        Node<Integer> root = new Node<Integer>(2);
        Node<Integer> n11 = new Node<Integer>(7);
        Node<Integer> n12 = new Node<Integer>(5);
        Node<Integer> n21 = new Node<Integer>(2);
        Node<Integer> n22 = new Node<Integer>(6);
        Node<Integer> n23 = new Node<Integer>(3);
        Node<Integer> n24 = new Node<Integer>(6);
        Node<Integer> n31 = new Node<Integer>(5);
        Node<Integer> n32 = new Node<Integer>(8);
        Node<Integer> n33 = new Node<Integer>(4);
        Node<Integer> n34 = new Node<Integer>(5);
        Node<Integer> n35 = new Node<Integer>(8);
        Node<Integer> n36 = new Node<Integer>(4);
        Node<Integer> n37 = new Node<Integer>(5);
        Node<Integer> n38 = new Node<Integer>(8);

        root.left = n11;
        root.right = n12;

        n11.left = n21;
        n11.right = n22;
        n12.left = n23;
        n12.right = n24;

        n21.left = n31;
        n21.right = n32;
        n22.left = n33;
        n22.right = n34;
        n23.left = n35;
        n23.right = n36;
        n24.left = n37;
        n24.right = n38;

        return root;
    }

    private static Node<Integer> test2() {
        Node<Integer> root = new Node<Integer>(2);
        Node<Integer> n11 = new Node<Integer>(7);
        Node<Integer> n12 = new Node<Integer>(5);
        Node<Integer> n21 = new Node<Integer>(2);
        Node<Integer> n22 = new Node<Integer>(6);
        Node<Integer> n23 = new Node<Integer>(9);
        Node<Integer> n31 = new Node<Integer>(5);
        Node<Integer> n32 = new Node<Integer>(8);
        Node<Integer> n33 = new Node<Integer>(4);

        root.left = n11;
        root.right = n12;

        n11.left = n21;
        n11.right = n22;

        n12.right = n23;
        n22.left = n31;
        n22.right = n32;

        n23.left = n33;

        return root;
    }

    public static void main(String[] args) {

        BTreePrinter.printNode(test1());
        BTreePrinter.printNode(test2());

    }
}

class Node<T extends Comparable<?>> {
    Node<T> left, right;
    T data;

    public Node(T data) {
        this.data = data;
    }
}

class BTreePrinter {

    public static <T extends Comparable<?>> void printNode(Node<T> root) {
        int maxLevel = BTreePrinter.maxLevel(root);

        printNodeInternal(Collections.singletonList(root), 1, maxLevel);
    }

    private static <T extends Comparable<?>> void printNodeInternal(List<Node<T>> nodes, int level, int maxLevel) {
        if (nodes.isEmpty() || BTreePrinter.isAllElementsNull(nodes))
            return;

        int floor = maxLevel - level;
        int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0)));
        int firstSpaces = (int) Math.pow(2, (floor)) - 1;
        int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1;

        BTreePrinter.printWhitespaces(firstSpaces);

        List<Node<T>> newNodes = new ArrayList<Node<T>>();
        for (Node<T> node : nodes) {
            if (node != null) {
                System.out.print(node.data);
                newNodes.add(node.left);
                newNodes.add(node.right);
            } else {
                newNodes.add(null);
                newNodes.add(null);
                System.out.print(" ");
            }

            BTreePrinter.printWhitespaces(betweenSpaces);
        }
        System.out.println("");

        for (int i = 1; i <= endgeLines; i++) {
            for (int j = 0; j < nodes.size(); j++) {
                BTreePrinter.printWhitespaces(firstSpaces - i);
                if (nodes.get(j) == null) {
                    BTreePrinter.printWhitespaces(endgeLines + endgeLines + i + 1);
                    continue;
                }

                if (nodes.get(j).left != null)
                    System.out.print("/");
                else
                    BTreePrinter.printWhitespaces(1);

                BTreePrinter.printWhitespaces(i + i - 1);

                if (nodes.get(j).right != null)
                    System.out.print("\\");
                else
                    BTreePrinter.printWhitespaces(1);

                BTreePrinter.printWhitespaces(endgeLines + endgeLines - i);
            }

            System.out.println("");
        }

        printNodeInternal(newNodes, level + 1, maxLevel);
    }

    private static void printWhitespaces(int count) {
        for (int i = 0; i < count; i++)
            System.out.print(" ");
    }

    private static <T extends Comparable<?>> int maxLevel(Node<T> node) {
        if (node == null)
            return 0;

        return Math.max(BTreePrinter.maxLevel(node.left), BTreePrinter.maxLevel(node.right)) + 1;
    }

    private static <T> boolean isAllElementsNull(List<T> list) {
        for (Object object : list) {
            if (object != null)
                return false;
        }

        return true;
    }

}

Output 1:

         2               
        / \       
       /   \      
      /     \     
     /       \    
     7       5       
    / \     / \   
   /   \   /   \  
   2   6   3   6   
  / \ / \ / \ / \ 
  5 8 4 5 8 4 5 8 

Output 2:

       2               
      / \       
     /   \      
    /     \     
   /       \    
   7       5       
  / \       \   
 /   \       \  
 2   6       9   
    / \     /   
    5 8     4   
michal.kreuzman
sumber
1
bagaimana cara mengubah output ini menjadi horizontal?
jijesh Aj
Untuk output horisontal lebih baik menggunakan solusi Vasya Novikov.
michal.kreuzman
3
Akan sangat bagus jika Anda dapat menguraikan memilih 2 ^ n - 1 sebagai spasi pertama dan 2 ^ (n + 1) - 1 sebagai ruang antar
DJ '
Ini bagus untuk pohon seimbang karena saya mencobanya untuk salah satu pohon miring kanan dengan nilai 15 dan menjadi sangat tidak terkendali untuk melihat cetakannya.
akhil_mittal
3
Pohon saya adalah 44 lapisan, jadi java crash ketika mencoba untuk mencetak 8796093022207 spasi putih. Jadi berhati-hatilah.
CX gamer
286

Cetak pohon [besar] demi baris.

contoh output:

z
├── c
   ├── a
   └── b
├── d
├── e
   └── asdf
└── f

kode:

public class TreeNode {

    final String name;
    final List<TreeNode> children;

    public TreeNode(String name, List<TreeNode> children) {
        this.name = name;
        this.children = children;
    }

    public String toString() {
        StringBuilder buffer = new StringBuilder(50);
        print(buffer, "", "");
        return buffer.toString();
    }

    private void print(StringBuilder buffer, String prefix, String childrenPrefix) {
        buffer.append(prefix);
        buffer.append(name);
        buffer.append('\n');
        for (Iterator<TreeNode> it = children.iterator(); it.hasNext();) {
            TreeNode next = it.next();
            if (it.hasNext()) {
                next.print(buffer, childrenPrefix + "├── ", childrenPrefix + "│   ");
            } else {
                next.print(buffer, childrenPrefix + "└── ", childrenPrefix + "    ");
            }
        }
    }
}

PS Jawaban ini tidak persis berfokus pada pohon "biner" - sebagai gantinya, ia mencetak semua jenis pohon. Solusi diilhami oleh perintah "tree" di linux.

VasiliNovikov
sumber
Apakah solusi ini menangani pohon biner miring kanan?
patentfox
@VasyaNovikov bagaimana Anda menulis ulang children.get(children.size() - 1)jika HashMap digunakan untuk anak-anak? Saya berhasil memodifikasi setiap bagian selain bagian ini.
Le Nguyen Duy Anh
@LeNguyenDuyAnh apa tanda tangan tipe yang diusulkan HashMap? HashMap<String, List<String>>?
VasiliNovikov
Saya telah mengimplementasikan pohon saya sebagai HashMap<String, Node>. String adalah id Node.
Le Nguyen Duy Anh
Saya benar-benar mengimplementasikan sesuatu yang serupa di perpustakaan Java kecil yang disebut text-tree . Mungkin itu membantu seseorang.
barfuin
47

Saya telah membuat algoritma yang ditingkatkan untuk ini, yang menangani node dengan ukuran yang berbeda. Mencetak top-down menggunakan garis.

package alg;

import java.util.ArrayList;
import java.util.List;


/**
 * Binary tree printer
 * 
 * @author MightyPork
 */
public class TreePrinter
{
    /** Node that can be printed */
    public interface PrintableNode
    {
        /** Get left child */
        PrintableNode getLeft();


        /** Get right child */
        PrintableNode getRight();


        /** Get text to be printed */
        String getText();
    }


    /**
     * Print a tree
     * 
     * @param root
     *            tree root node
     */
    public static void print(PrintableNode root)
    {
        List<List<String>> lines = new ArrayList<List<String>>();

        List<PrintableNode> level = new ArrayList<PrintableNode>();
        List<PrintableNode> next = new ArrayList<PrintableNode>();

        level.add(root);
        int nn = 1;

        int widest = 0;

        while (nn != 0) {
            List<String> line = new ArrayList<String>();

            nn = 0;

            for (PrintableNode n : level) {
                if (n == null) {
                    line.add(null);

                    next.add(null);
                    next.add(null);
                } else {
                    String aa = n.getText();
                    line.add(aa);
                    if (aa.length() > widest) widest = aa.length();

                    next.add(n.getLeft());
                    next.add(n.getRight());

                    if (n.getLeft() != null) nn++;
                    if (n.getRight() != null) nn++;
                }
            }

            if (widest % 2 == 1) widest++;

            lines.add(line);

            List<PrintableNode> tmp = level;
            level = next;
            next = tmp;
            next.clear();
        }

        int perpiece = lines.get(lines.size() - 1).size() * (widest + 4);
        for (int i = 0; i < lines.size(); i++) {
            List<String> line = lines.get(i);
            int hpw = (int) Math.floor(perpiece / 2f) - 1;

            if (i > 0) {
                for (int j = 0; j < line.size(); j++) {

                    // split node
                    char c = ' ';
                    if (j % 2 == 1) {
                        if (line.get(j - 1) != null) {
                            c = (line.get(j) != null) ? '┴' : '┘';
                        } else {
                            if (j < line.size() && line.get(j) != null) c = '└';
                        }
                    }
                    System.out.print(c);

                    // lines and spaces
                    if (line.get(j) == null) {
                        for (int k = 0; k < perpiece - 1; k++) {
                            System.out.print(" ");
                        }
                    } else {

                        for (int k = 0; k < hpw; k++) {
                            System.out.print(j % 2 == 0 ? " " : "─");
                        }
                        System.out.print(j % 2 == 0 ? "┌" : "┐");
                        for (int k = 0; k < hpw; k++) {
                            System.out.print(j % 2 == 0 ? "─" : " ");
                        }
                    }
                }
                System.out.println();
            }

            // print line of numbers
            for (int j = 0; j < line.size(); j++) {

                String f = line.get(j);
                if (f == null) f = "";
                int gap1 = (int) Math.ceil(perpiece / 2f - f.length() / 2f);
                int gap2 = (int) Math.floor(perpiece / 2f - f.length() / 2f);

                // a number
                for (int k = 0; k < gap1; k++) {
                    System.out.print(" ");
                }
                System.out.print(f);
                for (int k = 0; k < gap2; k++) {
                    System.out.print(" ");
                }
            }
            System.out.println();

            perpiece /= 2;
        }
    }
}

Untuk menggunakan ini untuk Pohon Anda, biarkan Nodekelas Anda menerapkan PrintableNode.

Contoh output:

                                         2952:0                                             
                    ┌───────────────────────┴───────────────────────┐                       
                 1249:-1                                         5866:0                     
        ┌───────────┴───────────┐                       ┌───────────┴───────────┐           
     491:-1                  1572:0                  4786:1                  6190:0         
  ┌─────┘                                               └─────┐           ┌─────┴─────┐     
339:0                                                      5717:0      6061:0      6271:0   
MightyPork
sumber
Saya mencoba meniru teknik "jawaban yang dipilih". Tapi saya pikir ini salah satu jawaban terbaik di sini. Jadi Kuat dan ringkas.
Vikrant Goel
Setelah menerapkan ini tampaknya berhasil, tetapi hanya untuk pohon seimbang. Ketidakseimbangan apa pun menghasilkan hasil yang aneh.
mitbanip
Saya mendapatkan ???????????alih-alih garis antara node tetapi harus hanya beberapa masalah barang UTF8 ans. Bagaimanapun, hal-hal hebat, saya harus katakan. Jawaban terbaik bagi saya karena sangat mudah digunakan.
Fitz
Ya itu saja. Hanya harus mengubah semua karakter khusus dari baris dan spasi paragraf Anda.
Fitz
Bagus, untuk mendukung pencetakan berbagai elemen, membuat inti yang hanya melakukan itu menggunakan logika @MightyPork untuk mencetak pohon. Lihatpublic static <T> void print(T[] elems)
Neo
40
public static class Node<T extends Comparable<T>> {
    T value;
    Node<T> left, right;

    public void insertToTree(T v) {
        if (value == null) {
            value = v;
            return;
        }
        if (v.compareTo(value) < 0) {
            if (left == null) {
                left = new Node<T>();
            }
            left.insertToTree(v);
        } else {
            if (right == null) {
                right = new Node<T>();
            }
            right.insertToTree(v);
        }
    }

    public void printTree(OutputStreamWriter out) throws IOException {
        if (right != null) {
            right.printTree(out, true, "");
        }
        printNodeValue(out);
        if (left != null) {
            left.printTree(out, false, "");
        }
    }
    private void printNodeValue(OutputStreamWriter out) throws IOException {
        if (value == null) {
            out.write("<null>");
        } else {
            out.write(value.toString());
        }
        out.write('\n');
    }
    // use string and not stringbuffer on purpose as we need to change the indent at each recursion
    private void printTree(OutputStreamWriter out, boolean isRight, String indent) throws IOException {
        if (right != null) {
            right.printTree(out, true, indent + (isRight ? "        " : " |      "));
        }
        out.write(indent);
        if (isRight) {
            out.write(" /");
        } else {
            out.write(" \\");
        }
        out.write("----- ");
        printNodeValue(out);
        if (left != null) {
            left.printTree(out, false, indent + (isRight ? " |      " : "        "));
        }
    }

}

akan dicetak:

                 /----- 20
                 |       \----- 15
         /----- 14
         |       \----- 13
 /----- 12
 |       |       /----- 11
 |       \----- 10
 |               \----- 9
8
 |               /----- 7
 |       /----- 6
 |       |       \----- 5
 \----- 4
         |       /----- 3
         \----- 2
                 \----- 1

untuk input

8 4 12 2 6 10 14 1 3 5 7 9 11 13 20 15

ini adalah varian dari jawaban @ anurag - itu menggangguku untuk melihat ekstra | s

Laurent Demailly
sumber
Akan luar biasa jika Anda bisa memutarnya 90 °.
Abhijit Sarkar
34

Diadaptasi dari Vasya Novikov 's jawaban untuk membuatnya lebih biner , dan menggunakan StringBuilderuntuk efisiensi (concatenating Stringbenda bersama-sama di Jawa umumnya tidak efisien).

public StringBuilder toString(StringBuilder prefix, boolean isTail, StringBuilder sb) {
    if(right!=null) {
        right.toString(new StringBuilder().append(prefix).append(isTail ? "│   " : "    "), false, sb);
    }
    sb.append(prefix).append(isTail ? "└── " : "┌── ").append(value.toString()).append("\n");
    if(left!=null) {
        left.toString(new StringBuilder().append(prefix).append(isTail ? "    " : "│   "), true, sb);
    }
    return sb;
}

@Override
public String toString() {
    return this.toString(new StringBuilder(), true, new StringBuilder()).toString();
}

Keluaran:

       ┌── 7
   ┌── 6
      └── 5
└── 4
       ┌── 3
    └── 2
        └── 1
            └── 0
Todd Davies
sumber
Ini tidak berfungsi untuk pohon ketika kita memasukkan nilai: 30,40,50,60,70,80 ke dalam BST. Ketika itu menciptakan pohon miring kanan. Nilai untuk isTail harus salah ketika. right != nullSaya melakukan edit dan mengujinya, itu berfungsi dengan baik.
akhil_mittal
Terima kasih atas masukannya, saya baru mengedit jawabannya, apakah itu lebih baik?
Todd Davies
Terima kasih, @Vasya Novikov menjawab dengan baik, tetapi saya memerlukan versi tautannya, dan jawaban Anda sesuai dengan kasus saya.
hychou
Dalam semua jawaban, ini menghasilkan pohon yang paling cantik, dan kodenya sangat bersih!
p-sun
15

michal.kreuzman bagus saya harus katakan.

Saya merasa malas membuat program sendiri dan mencari kode di internet ketika saya menemukan ini sangat membantu saya.

Tetapi saya takut melihat bahwa itu hanya berfungsi untuk satu digit saja seolah-olah Anda akan menggunakan lebih dari satu digit, karena Anda menggunakan spasi dan tidak tab struktur akan salah tempat dan program akan kehilangan penggunaannya.

Adapun kode saya nanti saya butuh beberapa input yang lebih besar (setidaknya lebih dari 10) ini tidak bekerja untuk saya, dan setelah mencari banyak di internet ketika saya tidak menemukan apa-apa, saya membuat program sendiri.

Ini memiliki beberapa bug sekarang, lagi sekarang saya merasa malas untuk memperbaikinya tetapi mencetak sangat indah dan node dapat mengambil nilai besar.

Pohon itu tidak akan seperti pertanyaan yang disebutkan tetapi dirotasi 270 derajat :)

public static void printBinaryTree(TreeNode root, int level){
    if(root==null)
         return;
    printBinaryTree(root.right, level+1);
    if(level!=0){
        for(int i=0;i<level-1;i++)
            System.out.print("|\t");
            System.out.println("|-------"+root.val);
    }
    else
        System.out.println(root.val);
    printBinaryTree(root.left, level+1);
}    

Tempatkan fungsi ini dengan TreeNode yang Anda tentukan sendiri dan pertahankan level awalnya 0, dan selamat menikmati!

Berikut adalah beberapa contoh keluaran:

|       |       |-------11
|       |-------10
|       |       |-------9
|-------8
|       |       |-------7
|       |-------6
|       |       |-------5
4
|       |-------3
|-------2
|       |-------1


|       |       |       |-------10
|       |       |-------9
|       |-------8
|       |       |-------7
|-------6
|       |-------5
4
|       |-------3
|-------2
|       |-------1

Satu-satunya masalah adalah dengan cabang yang diperluas; Saya akan mencoba menyelesaikan masalah sesegera mungkin tetapi sampai saat itu Anda dapat menggunakannya juga.

Anurag Agarwal
sumber
14

Pohon Anda membutuhkan jarak dua kali lipat untuk setiap lapisan:

       Sebuah
      / \
     / \
    / \
   / \
   bc
  / \ / \
 / \ / \
 defg
/ \ / \ / \ / \
hijklmno

Anda dapat menyimpan pohon Anda dalam array array, satu array untuk setiap kedalaman:

[[a], [b, c], [d, e, f, g], [h, i, j, k, l, m, n, o]]

Jika pohon Anda tidak penuh, Anda harus memasukkan nilai kosong dalam array itu:

       Sebuah
      / \
     / \
    / \
   / \
   bc
  / \ / \
 / \ / \
 defg
/ \ \ / \ \
hiklmo
[[a], [b, c], [d, e, f, g], [h, i,, k, l, m,, o]]

Kemudian Anda dapat beralih di atas array untuk mencetak pohon Anda, mencetak spasi sebelum elemen pertama dan antara elemen tergantung pada kedalaman dan mencetak garis tergantung pada apakah elemen yang sesuai dalam array untuk lapisan berikutnya diisi atau tidak. Jika nilai Anda bisa lebih dari satu karakter, Anda harus menemukan nilai terpanjang sambil membuat representasi array dan melipatgandakan semua lebar dan jumlah garis yang sesuai.

hd42
sumber
Bagaimana jika pohon itu tidak lengkap? Dalam hal ini sepertinya Anda harus dapat melakukan ini tanpa menggandakan ruang di setiap level.
templatetypedef
Ya, tetapi hanya dalam beberapa kasus yang sangat terbatas di mana sebagian besar sub pohon dihubungkan daftar, bukan pohon dari tingkat yang sama ke bawah atau Anda akan menggambar pohon bawah berbeda dengan jarak antar lapisan yang berbeda ...
hd42
13

Saya menemukan jawaban VasyaNovikov sangat berguna untuk mencetak pohon umum yang besar, dan memodifikasinya untuk pohon biner

Kode:

class TreeNode {
    Integer data = null;
    TreeNode left = null;
    TreeNode right = null;

    TreeNode(Integer data) {this.data = data;}

    public void print() {
        print("", this, false);
    }

    public void print(String prefix, TreeNode n, boolean isLeft) {
        if (n != null) {
            System.out.println (prefix + (isLeft ? "|-- " : "\\-- ") + n.data);
            print(prefix + (isLeft ? "|   " : "    "), n.left, true);
            print(prefix + (isLeft ? "|   " : "    "), n.right, false);
        }
    }
}

Output sampel:

\-- 7
    |-- 3
    |   |-- 1
    |   |   \-- 2
    |   \-- 5
    |       |-- 4
    |       \-- 6
    \-- 11
        |-- 9
        |   |-- 8
        |   \-- 10
        \-- 13
            |-- 12
            \-- 14
Nitin K
sumber
8

Solusi dalam bahasa Scala , analog dengan apa yang saya tulis di java :

case class Node(name: String, children: Node*) {

    def toTree: String = toTree("", "").mkString("\n")

    private def toTree(prefix: String, childrenPrefix: String): Seq[String] = {
        val firstLine = prefix + this.name

        val firstChildren = this.children.dropRight(1).flatMap { child =>
            child.toTree(childrenPrefix + "├── ", childrenPrefix + "│   ")
        }
        val lastChild = this.children.takeRight(1).flatMap { child =>
            child.toTree(childrenPrefix + "└── ", childrenPrefix + "    ")
        }
        firstLine +: firstChildren ++: lastChild
    }

}

Contoh keluaran:

vasya
├── frosya
   ├── petya
      └── masha
   └── kolya
└── frosya2
VasiliNovikov
sumber
1
Dengan Lambda yang tersedia di Jawa juga, mungkin Anda ingin memperbarui solusi Java Anda?
Tintin
@Tintin Scala sama sekali bukan hanya tentang fungsi lambda. Tetapi jika Anda memiliki peningkatan yang baik untuk Jawa, jangan ragu untuk "mengedit", yang kemudian akan diterima oleh komunitas StackOverflow jika dianggap bermanfaat.;)
VasiliNovikov
5

Saya tahu kalian semua memiliki solusi hebat; Saya hanya ingin berbagi milik saya - mungkin itu bukan cara terbaik, tetapi itu sempurna untuk diri saya sendiri!

Dengan pythondan pipterus, itu benar-benar sangat sederhana! LEDAKAN!

Di Mac atau Ubuntu (milik saya adalah mac)

  1. terminal terbuka
  2. $ pip install drawtree
  3. $python, masukkan konsol python; Anda bisa melakukannya dengan cara lain
  4. from drawtree import draw_level_order
  5. draw_level_order('{2,1,3,0,7,9,1,2,#,1,0,#,#,8,8,#,#,#,#,7}')

DIBUAT!

        2
       / \
      /   \
     /     \
    1       3
   / \     / \
  0   7   9   1
 /   / \     / \
2   1   0   8   8
       /
      7

Pelacakan sumber:

Sebelum saya melihat posting ini, saya pergi ke google "binary tree plain text"

Dan saya menemukan ini https://www.reddit.com/r/learnpython/comments/3naiq8/draw_binary_tree_in_plain_text/ , mengarahkan saya ke https://github.com/msbanik/drawtree ini

Sean L
sumber
@DenysVitali oh ya Anda benar): Saya mungkin harus memindahkan ini ke 'cara mencetak pohon dari traversal urutan tingkat serial (bahasa / python)'.
Sean L
3
Saya tidak ingin terlihat kasar, tetapi ketika pengguna menandai pertanyaan saat javadia mengharapkan jawaban Java :)
Denys Vitali
3
public void printPreety() {
    List<TreeNode> list = new ArrayList<TreeNode>();
    list.add(head);
    printTree(list, getHeight(head));
}

public int getHeight(TreeNode head) {

    if (head == null) {
        return 0;
    } else {
        return 1 + Math.max(getHeight(head.left), getHeight(head.right));
    }
}

/**
 * pass head node in list and height of the tree 
 * 
 * @param levelNodes
 * @param level
 */
private void printTree(List<TreeNode> levelNodes, int level) {

    List<TreeNode> nodes = new ArrayList<TreeNode>();

    //indentation for first node in given level
    printIndentForLevel(level);

    for (TreeNode treeNode : levelNodes) {

        //print node data
        System.out.print(treeNode == null?" ":treeNode.data);

        //spacing between nodes
        printSpacingBetweenNodes(level);

        //if its not a leaf node
        if(level>1){
            nodes.add(treeNode == null? null:treeNode.left);
            nodes.add(treeNode == null? null:treeNode.right);
        }
    }
    System.out.println();

    if(level>1){        
        printTree(nodes, level-1);
    }
}

private void printIndentForLevel(int level){
    for (int i = (int) (Math.pow(2,level-1)); i >0; i--) {
        System.out.print(" ");
    }
}

private void printSpacingBetweenNodes(int level){
    //spacing between nodes
    for (int i = (int) ((Math.pow(2,level-1))*2)-1; i >0; i--) {
        System.out.print(" ");
    }
}


Prints Tree in following format:
                4                               
        3               7               
    1               5       8       
      2                       10   
                             9   
Sujit Kamthe
sumber
2

Ini adalah solusi yang sangat sederhana untuk mencetak pohon. Ini tidak cantik, tetapi sangat sederhana:

enum { kWidth = 6 };
void PrintSpace(int n)
{
  for (int i = 0; i < n; ++i)
    printf(" ");
}

void PrintTree(struct Node * root, int level)
{
  if (!root) return;
  PrintTree(root->right, level + 1);
  PrintSpace(level * kWidth);
  printf("%d", root->data);
  PrintTree(root->left, level + 1);
}

Output sampel:

      106
            105
104
            103
                  102
                        101
      100
Wenguang Wang
sumber
2

Berdasarkan jawaban VasyaNovikov. Ditingkatkan dengan beberapa sihir Java: Antarmuka Generik dan Fungsional.

/**
 * Print a tree structure in a pretty ASCII fromat.
 * @param prefix Currnet previx. Use "" in initial call!
 * @param node The current node. Pass the root node of your tree in initial call.
 * @param getChildrenFunc A {@link Function} that returns the children of a given node.
 * @param isTail Is node the last of its sibblings. Use true in initial call. (This is needed for pretty printing.)
 * @param <T> The type of your nodes. Anything that has a toString can be used.
 */
private <T> void printTreeRec(String prefix, T node, Function<T, List<T>> getChildrenFunc, boolean isTail) {
    String nodeName = node.toString();
    String nodeConnection = isTail ? "└── " : "├── ";
    log.debug(prefix + nodeConnection + nodeName);
    List<T> children = getChildrenFunc.apply(node);
    for (int i = 0; i < children.size(); i++) {
        String newPrefix = prefix + (isTail ? "    " : "│   ");
        printTreeRec(newPrefix, children.get(i), getChildrenFunc, i == children.size()-1);
    }
}

Contoh panggilan awal:

Function<ChecksumModel, List<ChecksumModel>> getChildrenFunc = node -> getChildrenOf(node)
printTreeRec("", rootNode, getChildrenFunc, true);

Akan menampilkan sesuatu seperti

└── rootNode
    ├── childNode1
    ├── childNode2
       ├── childNode2.1
       ├── childNode2.2
       └── childNode2.3
    ├── childNode3
    └── childNode4
Robert
sumber
2

Saya menulis printer pohon biner di Jawa.

Kode ada di GitHub di sini .

Ini belum dioptimalkan untuk efisiensi waktu berjalan, tetapi karena kita berbicara tentang mencetak di ASCII, saya pikir itu tidak akan digunakan pada pohon yang sangat besar. Itu memang memiliki beberapa fitur yang bagus.

  1. Itu membuat penggunaan ruang yang efisien dalam hal subtree besar meluas di bawah yang lebih kecil sebanyak mungkin.
  2. Ada parameter untuk mengatur ruang horizontal minimum antara label node.
  3. Label simpul adalah string yang panjangnya sewenang-wenang.
  4. Selain metode untuk mencetak pohon tunggal, ada metode untuk mencetak daftar pohon secara horizontal di seluruh halaman (dengan parameter untuk lebar halaman), menggunakan baris sebanyak yang diperlukan.
  5. Ada pilihan untuk mencetak pohon dengan cabang diagonal (menggunakan karakter garis miring dan garis miring terbalik) atau dengan cabang horisontal (menggunakan karakter menggambar kotak ascii). Yang terakhir lebih kompak dan membuat tingkat pohon lebih jelas secara visual.
  6. Berhasil.

Beberapa program demo / uji disertakan.

Contoh pohon biner yang dihasilkan secara acak, seperti yang dicetak oleh program, berikut. Ini menggambarkan penggunaan ruang yang efisien, dengan subtree kanan besar memanjang di bawah subtree kiri kecil:

             seven                                        
              / \                                         
             /   \                                        
            /     \                                       
           /       \                                      
          /         \                                     
         /           \                                    
       five        thirteen                               
       / \           / \                                  
      /   \         /   \                                 
     /     \       /     \                                
  three    six    /       \                               
   / \           /         \                              
  /   \         /           \                             
one   four     /             \                            
  \           /               \                           
  two        /                 \                          
           nine            twenty four                    
           / \                 / \                        
          /   \               /   \                       
         /     \             /     \                      
      eight   twelve        /       \                     
               /           /         \                    
             ten          /           \                   
               \         /             \                  
              eleven    /               \                 
                       /                 \                
                      /                   \               
                     /                     \              
                 eighteen              twenty seven       
                   / \                     / \            
                  /   \                   /   \           
                 /     \                 /     \          
                /       \               /       \         
               /         \             /         \        
              /           \           /           \       
             /             \    twenty five   twenty eight
            /               \         \             \     
           /                 \     twenty six      thirty 
       fourteen            nineteen                 /     
           \                   \              twenty nine 
         sixteen           twenty three                   
           / \                 /                          
          /   \           twenty two                      
         /     \             /                            
        /       \         twenty                          
       /         \           \                            
   fifteen    seventeen   twenty one                      

Contoh mencetak semua lima pohon simpul biner (dengan label berurutan) di seluruh halaman:

one           one         one          one        one       one         one     
  \             \           \            \          \         \           \     
  two           two         two          two        two      three       three  
    \             \           \            \          \       / \         / \   
   three         three        four         five       five  two four    two five
      \             \         / \          /          /           \         /   
      four          five     /   \      three       four          five    four  
        \           /     three  five      \        /                           
        five      four                     four  three                          



one          one        one        one       one       one         one        two        
  \            \          \          \         \         \           \        / \        
  four         four       five       five      five      five        five    /   \       
  / \          / \        /          /         /         /           /     one  three    
two five      /   \     two        two      three      four        four            \     
  \        three  five    \          \       / \       /           /               four  
 three      /            three       four  two four  two        three                \   
          two               \        /                 \         /                   five
                            four  three               three    two                       



   two          two          two        two      three         three         three    
   / \          / \          / \        / \       / \           / \           / \     
  /   \       one four     one five   one five  one four       /   \        two four  
one  three        / \          /          /       \   \       /     \       /     \   
        \        /   \      three       four      two five  one     five  one     five
        five  three  five      \        /                     \     /                 
        /                      four  three                    two four                
      four                                                                            



   three      four      four         four         four            four       five    
    / \       / \       / \          / \          / \             / \        /       
  two five  one five  one five     two five      /   \           /   \     one       
  /   /       \         \          / \        three  five     three  five    \       
one four      two      three      /   \        /               /             two     
                \       /       one  three   one             two               \     
               three  two                      \             /                three  
                                               two         one                   \   
                                                                                 four



  five      five      five      five       five         five      five        five
  /         /         /         /          /            /         /           /   
one       one       one       one        two          two      three       three  
  \         \         \         \        / \          / \       / \         / \   
  two      three      four      four    /   \       one four  one four    two four
    \       / \       /         /     one  three        /       \         /       
    four  two four  two      three            \      three      two     one       
    /                 \       /               four                                
 three               three  two                                                   



    five      five         five        five          five
    /         /            /           /             /   
  four      four         four        four          four  
  /         /            /           /             /     
one       one          two        three         three    
  \         \          / \         /             /       
  two      three      /   \      one           two       
    \       /       one  three     \           /         
   three  two                      two       one 

Berikut ini adalah contoh dari pohon yang sama dicetak 4 cara yang berbeda, dengan jarak horizontal 1 dan 3, dan dengan cabang diagonal dan horizontal.

                   27        
             ┌─────┴─────┐   
             13          29  
      ┌──────┴──────┐  ┌─┴─┐ 
      8             23 28  30
   ┌──┴──┐       ┌──┴──┐     
   4     11      21    26    
 ┌─┴─┐  ┌┴┐    ┌─┴─┐  ┌┘     
 2   5  9 12   18  22 24     
┌┴┐  └┐ └┐   ┌─┴─┐    └┐     
1 3   6  10  17  19    25    
      └┐    ┌┘   └┐          
       7    15    20         
          ┌─┴─┐              
          14  16             


                 27        
                / \        
               /   \       
              13    29     
             / \   / \     
            /   \ 28  30   
           /     \         
          /       \        
         /         \       
        /           \      
       8             23    
      / \           / \    
     /   \         /   \   
    4     11      /     \  
   / \   / \     21      26
  2   5 9   12  / \     /  
 / \   \ \     18  22  24  
1   3   6 10  / \       \  
         \   17  19      25
          7 /     \        
           15      20      
          / \              
         14  16            


                             27            
                    ┌────────┴────────┐    
                    13                29   
          ┌─────────┴─────────┐    ┌──┴──┐ 
          8                   23   28    30
     ┌────┴────┐         ┌────┴────┐       
     4         11        21        26      
  ┌──┴──┐    ┌─┴─┐    ┌──┴──┐     ┌┘       
  2     5    9   12   18    22    24       
┌─┴─┐   └┐   └┐    ┌──┴──┐        └┐       
1   3    6    10   17    19        25      
         └┐       ┌┘     └┐                
          7       15      20               
               ┌──┴──┐                     
               14    16                    


                      27         
                     / \         
                    /   \        
                   /     \       
                  /       \      
                 13        29    
                / \       / \    
               /   \     /   \   
              /     \   28    30 
             /       \           
            /         \          
           /           \         
          /             \        
         /               \       
        8                 23     
       / \               / \     
      /   \             /   \    
     /     \           /     \   
    4       11        /       \  
   / \     / \       21        26
  2   5   9   12    / \       /  
 / \   \   \       /   \     24  
1   3   6   10    18    22    \  
         \       / \           25
          7     /   \            
               17    19          
              /       \          
             15        20        
            / \                  
           /   \                 
          14    16               
Bill Vanyo
sumber
Sangat menyenangkan bahwa Anda menulis proyek yang diterbitkan ini. Sepertinya itu melakukan pekerjaan dengan baik, tetapi pada dasarnya hanya sebuah tautan ke perpustakaan Anda tidak memberikan jawaban yang baik pada Stack Overflow. Minimal, Anda harus memasukkan kode yang diperlukan untuk menggunakan perpustakaan Anda untuk menampilkan contoh yang Anda berikan, sehingga orang tahu apa yang terlibat dengan menggunakan perpustakaan Anda. Saat ini, ini hanya iklan untuk repo GitHub Anda. Itu bukan hal yang buruk, jika Anda menunjukkan kepada orang-orang bagaimana cara menggunakannya.
Makyen
BTW: Jika Anda mengedit kode contoh, silakan ping saya di sini dengan memasukkan @Makyenkomentar.
Makyen
2

Ini pertanyaan yang menarik, dan saya juga menulis proyek untuk itu.

binary-tree-printer

Berikut ini beberapa contohnya:

Cetak BST acak.

BTPrinter.printRandomBST(100, 100);
                              38                                  
                              / \                                 
                             /   \                                
                            /     \                               
                           /       \                              
                          /         \                             
                         /           \                            
                        /             \                           
                       /               \                          
                      /                 \                         
                     /                   \                        
                    /                     \                       
                   /                       \                      
                  /                         \                     
                 /                           \                    
                /                             \                   
               /                               \                  
              28                               82                 
             / \                               / \                
            /   \                             /   \               
           /     \                           /     \              
          /       \                         /       \             
         5        31                       /         \            
        / \       / \                     /           \           
       /   \     30 36                   /             \          
      /     \   /   / \                 /               \         
     /       \ 29  33 37               /                 \        
    /         \   / \                 /                   \       
   /           \ 32 35               65                   95      
  1            14   /               / \                   / \     
 / \           / \ 34              /   \                 94 97    
0   2         /   \               /     \               /   / \   
     \       12   24             /       \             93  96 98  
      3     / \   / \           /         \           /         \ 
       \   9  13 16 25         /           \         84         99
        4 / \   / \   \       /             \       / \           
         7  10 15 23  26     59             74     83 86          
        / \   \   /     \   / \             / \       / \         
       6   8  11 22     27 56 60           73 76     85 91        
                /         / \   \         /   / \       / \       
               20        /   \  61       67  75 79     88 92      
              / \       40   58   \     / \     / \   / \         
             18 21     / \   /    62   66 72   78 80 87 89        
            / \       39 54 57      \     /   /     \     \       
           17 19         / \        64   69  77     81    90      
                        50 55       /   / \                       
                       / \         63  68 70                      
                      /   \                 \                     
                     /     \                71                    
                    47     53                                     
                   / \     /                                      
                  /   \   52                                      
                 42   49 /                                        
                / \   / 51                                        
               41 43 48                                           
                    \                                             
                    46                                            
                    /                                             
                   45                                             
                  /                                               
                 44     

Print tree dari larik urutan tingkat gaya leetcode, '#' berarti terminator jalur di mana tidak ada simpul di bawah ini.

BTPrinter.printTree("1,2,3,4,5,#,#,6,7,8,1,#,#,#,#,#,#,2,3,4,5,6,7,8,9,10,11,12,13,14,15");
        1              
       / \             
      2   3            
     / \               
    /   \              
   4     5             
  / \   / \            
 6   7 8   1           
          / \          
         /   \         
        /     \        
       /       \       
      /         \      
     2           3     
    / \         / \    
   /   \       /   \   
  4     5     6     7  
 / \   / \   / \   / \ 
8   9 10 11 12 13 14 15
afkbrb
sumber
1

Saya perlu mencetak pohon biner di salah satu proyek saya, untuk itu saya telah menyiapkan kelas java TreePrinter, salah satu contoh hasil adalah:

                [+]
               /   \
              /     \
             /       \
            /         \
           /           \
        [*]             \
       /   \             [-]
[speed]     [2]         /   \
                    [45]     [12]

Ini adalah kode untuk kelas TreePrinterbersama dengan kelas TextNode. Untuk mencetak pohon apa saja, Anda cukup membuat pohon setara dengan TextNodekelas.


import java.util.ArrayList;

public class TreePrinter {

    public TreePrinter(){
    }

    public static String TreeString(TextNode root){
        ArrayList layers = new ArrayList();
        ArrayList bottom = new ArrayList();

        FillBottom(bottom, root);  DrawEdges(root);

        int height = GetHeight(root);
        for(int i = 0; i  s.length()) min = s.length();

            if(!n.isEdge) s += "[";
            s += n.text;
            if(!n.isEdge) s += "]";

            layers.set(n.depth, s);
        }

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i  temp = new ArrayList();

            for(int i = 0; i  0) temp.get(i-1).left = x;
                temp.add(x);
            }

            temp.get(count-1).left = n.left;
            n.left.depth = temp.get(count-1).depth+1;
            n.left = temp.get(0);

            DrawEdges(temp.get(count-1).left);
        }
        if(n.right != null){
            int count = n.right.x - (n.x + n.text.length() + 2);
            ArrayList temp = new ArrayList();

            for(int i = 0; i  0) temp.get(i-1).right = x;
                temp.add(x);
            }

            temp.get(count-1).right = n.right;
            n.right.depth = temp.get(count-1).depth+1;
            n.right = temp.get(0);  

            DrawEdges(temp.get(count-1).right);
        }
    }

    private static void FillBottom(ArrayList bottom, TextNode n){
        if(n == null) return;

        FillBottom(bottom, n.left);

        if(!bottom.isEmpty()){            
            int i = bottom.size()-1;
            while(bottom.get(i).isEdge) i--;
            TextNode last = bottom.get(i);

            if(!n.isEdge) n.x = last.x + last.text.length() + 3;
        }
        bottom.add(n);
        FillBottom(bottom, n.right);
    }

    private static boolean isLeaf(TextNode n){
        return (n.left == null && n.right == null);
    }

    private static int GetHeight(TextNode n){
        if(n == null) return 0;

        int l = GetHeight(n.left);
        int r = GetHeight(n.right);

        return Math.max(l, r) + 1;
    }
}


class TextNode {
    public String text;
    public TextNode parent, left, right;
    public boolean isEdge;
    public int x, depth;

    public TextNode(String text){
        this.text = text;
        parent = null; left = null; right = null;
        isEdge = false;
        x = 0; depth = 0;
    }
}

Akhirnya di sini adalah kelas uji untuk mencetak sampel yang diberikan:


public class Test {

    public static void main(String[] args){
        TextNode root = new TextNode("+");
        root.left = new TextNode("*");            root.left.parent = root;
        root.right = new TextNode("-");           root.right.parent = root;
        root.left.left = new TextNode("speed");   root.left.left.parent = root.left;
        root.left.right = new TextNode("2");      root.left.right.parent = root.left;
        root.right.left = new TextNode("45");     root.right.left.parent = root.right;
        root.right.right = new TextNode("12");    root.right.right.parent = root.right;

        System.out.println(TreePrinter.TreeString(root));
    }
}
anuragsn7
sumber
1

Anda dapat menggunakan applet untuk memvisualisasikannya dengan sangat mudah. Anda perlu mencetak item berikut.

  1. Cetak node sebagai lingkaran dengan jari-jari yang terlihat

    • Dapatkan koordinat untuk setiap node.

    • Koordinat x dapat divisualisasikan sebagai jumlah node yang dikunjungi sebelum node dikunjungi dalam inorder traversal.

    • Koordinat y dapat divisualisasikan sebagai kedalaman simpul tertentu.


  1. Cetak garis antara orang tua dan anak-anak

    • Ini dapat dilakukan dengan mempertahankan koordinat x dan y dari node dan orang tua dari setiap node dalam daftar yang terpisah.

    • Untuk setiap node kecuali root, gabungkan setiap node dengan induknya dengan mengambil koordinat x dan y dari anak dan induknya.

kaushalpranav
sumber
bisakah Anda memvisualisasikan dan memberikan solusi yang lebih baik daripada jawaban yang ada?
Enamul Hassan
1
private StringBuilder prettyPrint(Node root, int currentHeight, int totalHeight) {
        StringBuilder sb = new StringBuilder();
        int spaces = getSpaceCount(totalHeight-currentHeight + 1);
        if(root == null) {
            //create a 'spatial' block and return it
            String row = String.format("%"+(2*spaces+1)+"s%n", "");
            //now repeat this row space+1 times
            String block = new String(new char[spaces+1]).replace("\0", row);
            return new StringBuilder(block);
        }
        if(currentHeight==totalHeight) return new StringBuilder(root.data+"");
        int slashes = getSlashCount(totalHeight-currentHeight +1);
        sb.append(String.format("%"+(spaces+1)+"s%"+spaces+"s", root.data+"", ""));
        sb.append("\n");
        //now print / and \
        // but make sure that left and right exists
        char leftSlash = root.left == null? ' ':'/';
        char rightSlash = root.right==null? ' ':'\\';
        int spaceInBetween = 1;
        for(int i=0, space = spaces-1; i<slashes; i++, space --, spaceInBetween+=2) {
            for(int j=0; j<space; j++) sb.append(" ");
            sb.append(leftSlash);
            for(int j=0; j<spaceInBetween; j++) sb.append(" ");
            sb.append(rightSlash+"");
            for(int j=0; j<space; j++) sb.append(" ");
            sb.append("\n");
        }
        //sb.append("\n");

        //now get string representations of left and right subtrees
        StringBuilder leftTree = prettyPrint(root.left, currentHeight+1, totalHeight);
        StringBuilder rightTree = prettyPrint(root.right, currentHeight+1, totalHeight);
        // now line by line print the trees side by side
        Scanner leftScanner = new Scanner(leftTree.toString());
        Scanner rightScanner = new Scanner(rightTree.toString());
//      spaceInBetween+=1;
        while(leftScanner.hasNextLine()) {
            if(currentHeight==totalHeight-1) {
                sb.append(String.format("%-2s %2s", leftScanner.nextLine(), rightScanner.nextLine()));
                sb.append("\n");
                spaceInBetween-=2;              
            }
            else {
                sb.append(leftScanner.nextLine());
                sb.append(" ");
                sb.append(rightScanner.nextLine()+"\n");
            }
        }

        return sb;

    }
private int getSpaceCount(int height) {
        return (int) (3*Math.pow(2, height-2)-1);
    }
private int getSlashCount(int height) {
        if(height <= 3) return height -1;
        return (int) (3*Math.pow(2, height-3)-1);
    }

https://github.com/murtraja/java-binary-tree-printer

hanya berfungsi untuk 1 hingga 2 digit bilangan bulat (saya malas membuatnya generik)

miring penuh

Murtaza Raja
sumber
1

Ini adalah solusi paling sederhana untuk tampilan horizontal. Mencoba dengan banyak contoh. Bekerja dengan baik untuk tujuan saya. Diperbarui dari jawaban @ nitin-k.

public void print(String prefix, BTNode n, boolean isLeft) {
    if (n != null) {
        print(prefix + "     ", n.right, false);
        System.out.println (prefix + ("|-- ") + n.data);
        print(prefix + "     ", n.left, true);
    }
}

Panggilan:

bst.print("", bst.root, false);

Larutan:

                         |-- 80
                    |-- 70
               |-- 60
          |-- 50
     |-- 40
|-- 30
     |-- 20
          |-- 10
navderm
sumber
1
  1. Anda harus menyamakan urutan melintasi pohon Anda.
  2. Pilih panjang simpul dan panjang spasi .
  3. Dapatkan lebar dasar pohon relatif terhadap setiap level yang ada node_length * nodes_count + space_length * spaces_count*.
  4. Temukan hubungan antara percabangan, jarak, indentasi dan lebar dasar yang dihitung.

Kode pada GitHub: YoussefRaafatNasry / bst-ascii-visualisasi

                                             07                     
                                             /\                     
                                            /  \                    
                                           /    \                   
                                          /      \                  
                                         /        \                 
                                        /          \                
                                       /            \               
                                      /              \              
                                     /                \             
                                    /                  \            
                                   /                    \           
                                 03                      11         
                                 /\                      /\         
                                /  \                    /  \        
                               /    \                  /    \       
                              /      \                /      \      
                             /        \              /        \     
                           01          05          09          13   
                           /\          /\          /\          /\   
                          /  \        /  \        /  \        /  \  
                        00    02    04    06    08    10    12    14
YoussefRaafatNasry
sumber
Saya akan mengatakan kode ini cukup pendek sehingga Anda dapat menanamkannya ke dalam jawaban Anda.
m02ph3u5
Kode bukan hanya visualizefungsi, itu adalah seluruh visualizerkelas yang sekitar 200 loc termasuk file header.
YoussefRaafatNasry
1

Bagi mereka yang mencari solusi Rust:

pub struct Node {
  pub value: i32,
  left: Option<Box<Node>>,
  right: Option<Box<Node>>
}

impl Node {

  pub fn new(val: i32) -> Node {
    Node {
      value: val,
      left: None,
      right: None
    }
  }

  pub fn getLeftNode(&self) -> Option<&Node> {
   self.left.as_deref()
  }

  pub fn getRightNode(&self) -> Option<&Node> {
   self.right.as_deref()
  }

  pub fn setLeftNode(&mut self, val: i32) -> &mut Node {
   self.left = Some(Box::new(Node::new(val)));
   self.left.as_deref_mut().unwrap()
  }

  pub fn setRightNode(&mut self, val: i32) -> &mut Node {
   self.right = Some(Box::new(Node::new(val)));
   self.right.as_deref_mut().unwrap()
  }

  fn visualizeTree(&self, level: u16, is_tail: bool, columns: &mut HashSet<u16>) {
    let left = self.getLeftNode();
    let right = self.getRightNode();

    if right.is_some() {
      right.unwrap().visualizeTree(level+1, false, columns);
    }

    if level > 0 {
      for i in 0..level-1 {
          if columns.contains(&i) {
            print!("│   ");
          } else {
            print!("    ");
          }
      }
      if is_tail {
        println!("└── {}", self.value);
        columns.remove(&(level-1));
        columns.insert(level);
      } else {
        println!("┌── {}", self.value);
        columns.insert(level);
        columns.insert(level-1);
      }
    } else {
      println!("{}", self.value);
    }

    if left.is_some() {
      left.unwrap().visualizeTree(level+1, true, columns);
    }
  }

  pub fn printTree(&self) {
    let mut columns = HashSet::new();
    columns.insert(0);
    self.visualizeTree(0, true, &mut columns);
  }
}

Outputnya kira-kira seperti ini:

┌── 17
      ┌── 3
         └── 9
   └── 2
       └── 1
20
   ┌── 7
         ┌── 16
      └── 15
└── 8
       ┌── 11
    └── 4
        └── 13
Arsenius
sumber
0

Cetak di Konsol:

                                                500
                       700                                             300   
    200                                   400                                                                                          

Kode sederhana:

public int getHeight()
    {
        if(rootNode == null) return -1;
        return getHeight(rootNode);
    }

    private int getHeight(Node node)
    {
        if(node == null) return -1;

        return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    }

    public void printBinaryTree(Node rootNode)
    {
        Queue<Node> rootsQueue = new LinkedList<Node>();
        Queue<Node> levelQueue = new LinkedList<Node>();
        levelQueue.add(rootNode);
        int treeHeight = getHeight();
        int firstNodeGap;
        int internalNodeGap;
        int copyinternalNodeGap;
        while(true)
        {
            System.out.println("");
            internalNodeGap = (int)(Math.pow(2, treeHeight + 1) -1);  
            copyinternalNodeGap = internalNodeGap;
            firstNodeGap = internalNodeGap/2;

            boolean levelFirstNode = true;

            while(!levelQueue.isEmpty())
            {
                internalNodeGap = copyinternalNodeGap;
                Node currNode = levelQueue.poll();
                if(currNode != null)
                {
                    if(levelFirstNode)
                    {
                        while(firstNodeGap > 0)
                        {
                            System.out.format("%s", "   ");
                            firstNodeGap--; 
                        }
                        levelFirstNode =false;
                    }
                    else
                    {
                        while(internalNodeGap>0)
                        {
                            internalNodeGap--;
                            System.out.format("%s", "   ");
                        }
                    }
                    System.out.format("%3d",currNode.data);
                    rootsQueue.add(currNode);
                }
            }

            --treeHeight;

            while(!rootsQueue.isEmpty())
            {
                Node currNode = rootsQueue.poll();
                if(currNode != null)
                {
                    levelQueue.add(currNode.left);
                    levelQueue.add(currNode.right);
                }
            }

            if(levelQueue.isEmpty()) break;
        }

    }
Divang
sumber
0

Ini printer pohon yang sangat serbaguna. Bukan yang paling cantik, tetapi menangani banyak kasus. Jangan ragu untuk menambahkan garis miring jika Anda dapat menemukannya. masukkan deskripsi gambar di sini

package com.tomac120.NodePrinter;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by elijah on 6/28/16.
 */
public class NodePrinter{
    final private List<List<PrintableNodePosition>> nodesByRow;
    int maxColumnsLeft = 0;
    int maxColumnsRight = 0;
    int maxTitleLength = 0;
    String sep = " ";
    int depth = 0;

    public NodePrinter(PrintableNode rootNode, int chars_per_node){
        this.setDepth(rootNode,1);
        nodesByRow = new ArrayList<>(depth);
        this.addNode(rootNode._getPrintableNodeInfo(),0,0);
        for (int i = 0;i<chars_per_node;i++){
            //sep += " ";
        }
    }

    private void setDepth(PrintableNode info, int depth){
        if (depth > this.depth){
            this.depth = depth;
        }
        if (info._getLeftChild() != null){
            this.setDepth(info._getLeftChild(),depth+1);
        }
        if (info._getRightChild() != null){
            this.setDepth(info._getRightChild(),depth+1);
        }
    }

    private void addNode(PrintableNodeInfo node, int level, int position){
        if (position < 0 && -position > maxColumnsLeft){
            maxColumnsLeft = -position;
        }
        if (position > 0 && position > maxColumnsRight){
            maxColumnsRight = position;
        }
        if (node.getTitleLength() > maxTitleLength){
           maxTitleLength = node.getTitleLength();
        }
        List<PrintableNodePosition> row = this.getRow(level);
        row.add(new PrintableNodePosition(node, level, position));
        level++;

        int depthToUse = Math.min(depth,6);
        int levelToUse = Math.min(level,6);
        int offset = depthToUse - levelToUse-1;
        offset = (int)(Math.pow(offset,Math.log(depthToUse)*1.4));
        offset = Math.max(offset,3);


        PrintableNodeInfo leftChild = node.getLeftChildInfo();
        PrintableNodeInfo rightChild = node.getRightChildInfo();
        if (leftChild != null){
            this.addNode(leftChild,level,position-offset);
        }
        if (rightChild != null){
            this.addNode(rightChild,level,position+offset);
        }
    }

    private List<PrintableNodePosition> getRow(int row){
        if (row > nodesByRow.size() - 1){
            nodesByRow.add(new LinkedList<>());
        }
        return nodesByRow.get(row);
    }

    public void print(){
        int max_chars = this.maxColumnsLeft+maxColumnsRight+1;
        int level = 0;
        String node_format = "%-"+this.maxTitleLength+"s";
        for (List<PrintableNodePosition> pos_arr : this.nodesByRow){
            String[] chars = this.getCharactersArray(pos_arr,max_chars);
            String line = "";
            int empty_chars = 0;
            for (int i=0;i<chars.length+1;i++){
                String value_i = i < chars.length ? chars[i]:null;
                if (chars.length + 1 == i || value_i != null){
                    if (empty_chars > 0) {
                        System.out.print(String.format("%-" + empty_chars + "s", " "));
                    }
                    if (value_i != null){
                        System.out.print(String.format(node_format,value_i));
                        empty_chars = -1;
                    } else{
                        empty_chars = 0;
                    }
                } else {
                    empty_chars++;
                }
            }
            System.out.print("\n");

            int depthToUse = Math.min(6,depth);
            int line_offset = depthToUse - level;
            line_offset *= 0.5;
            line_offset = Math.max(0,line_offset);

            for (int i=0;i<line_offset;i++){
                System.out.println("");
            }


            level++;
        }
    }

    private String[] getCharactersArray(List<PrintableNodePosition> nodes, int max_chars){
        String[] positions = new String[max_chars+1];
        for (PrintableNodePosition a : nodes){
            int pos_i = maxColumnsLeft + a.column;
            String title_i = a.nodeInfo.getTitleFormatted(this.maxTitleLength);
            positions[pos_i] = title_i;
        }
        return positions;
    }
}

Kelas NodeInfo

package com.tomac120.NodePrinter;

/**
 * Created by elijah on 6/28/16.
 */
public class PrintableNodeInfo {
    public enum CLI_PRINT_COLOR {
        RESET("\u001B[0m"),
        BLACK("\u001B[30m"),
        RED("\u001B[31m"),
        GREEN("\u001B[32m"),
        YELLOW("\u001B[33m"),
        BLUE("\u001B[34m"),
        PURPLE("\u001B[35m"),
        CYAN("\u001B[36m"),
        WHITE("\u001B[37m");

        final String value;
        CLI_PRINT_COLOR(String value){
            this.value = value;
        }

        @Override
        public String toString() {
            return value;
        }
    }
    private final String title;
    private final PrintableNode leftChild;
    private final PrintableNode rightChild;
    private final CLI_PRINT_COLOR textColor;

    public PrintableNodeInfo(String title, PrintableNode leftChild, PrintableNode rightChild){
        this(title,leftChild,rightChild,CLI_PRINT_COLOR.BLACK);
    }

    public PrintableNodeInfo(String title, PrintableNode leftChild, PrintableNode righthild, CLI_PRINT_COLOR textColor){
        this.title = title;
        this.leftChild = leftChild;
        this.rightChild = righthild;
        this.textColor = textColor;
    }

    public String getTitle(){
        return title;
    }

    public CLI_PRINT_COLOR getTextColor(){
        return textColor;
    }

    public String getTitleFormatted(int max_chars){
        return this.textColor+title+CLI_PRINT_COLOR.RESET;
        /*
        String title = this.title.length() > max_chars ? this.title.substring(0,max_chars+1):this.title;
        boolean left = true;
        while(title.length() < max_chars){
            if (left){
                title = " "+title;
            } else {
                title = title + " ";
            }
        }
        return this.textColor+title+CLI_PRINT_COLOR.RESET;*/
    }

    public int getTitleLength(){
        return title.length();
    }

    public PrintableNodeInfo getLeftChildInfo(){
        if (leftChild == null){
            return null;
        }
        return leftChild._getPrintableNodeInfo();
    }

    public PrintableNodeInfo getRightChildInfo(){
        if (rightChild == null){
            return null;
        }
        return rightChild._getPrintableNodeInfo();
    }
}

Kelas NodePosition

package com.tomac120.NodePrinter;

/**
 * Created by elijah on 6/28/16.
 */
public class PrintableNodePosition implements Comparable<PrintableNodePosition> {
    public final int row;
    public final int column;
    public final PrintableNodeInfo nodeInfo;
    public PrintableNodePosition(PrintableNodeInfo nodeInfo, int row, int column){
        this.row = row;
        this.column = column;
        this.nodeInfo = nodeInfo;
    }

    @Override
    public int compareTo(PrintableNodePosition o) {
        return Integer.compare(this.column,o.column);
    }
}

Dan, akhirnya, Node Interface

package com.tomac120.NodePrinter;

/**
 * Created by elijah on 6/28/16.
 */
public interface PrintableNode {
    PrintableNodeInfo _getPrintableNodeInfo();
    PrintableNode _getLeftChild();
    PrintableNode _getRightChild();
}
pengguna1122069
sumber
0

Solusi Scala, diadaptasi dari jawaban Vasya Novikov dan khusus untuk pohon biner:

/** An immutable Binary Tree. */
case class BTree[T](value: T, left: Option[BTree[T]], right: Option[BTree[T]]) {

  /* Adapted from: http://stackoverflow.com/a/8948691/643684 */
  def pretty: String = {
    def work(tree: BTree[T], prefix: String, isTail: Boolean): String = {
      val (line, bar) = if (isTail) ("└── ", " ") else ("├── ", "│")

      val curr = s"${prefix}${line}${tree.value}"

      val rights = tree.right match {
        case None    => s"${prefix}${bar}   ├── ∅"
        case Some(r) => work(r, s"${prefix}${bar}   ", false)
      }

      val lefts = tree.left match {
        case None    => s"${prefix}${bar}   └── ∅"
        case Some(l) => work(l, s"${prefix}${bar}   ", true)
      }

      s"${curr}\n${rights}\n${lefts}"

    }

    work(this, "", true)
  }
}
Colin Woodbury
sumber
BTW, saya telah memutuskan untuk mengirim solusi Scala, juga: stackoverflow.com/a/43348945/1091436
VasiliNovikov
0

Lihat juga jawaban ini .

Khususnya itu tidak terlalu sulit untuk menggunakan TreeLayout untuk menghasilkan hasil yang ditunjukkan di bawah ini dengan pengaturan default.

Jika Anda mencoba alat itu, perhatikan peringatan ini: Mencetak anak-anak sesuai urutan penambahannya. Untuk BST di mana masalah kiri vs kanan, saya menemukan perpustakaan ini menjadi tidak pantas tanpa modifikasi.

Juga, metode untuk menambahkan anak-anak hanya membutuhkan a parentdan childsimpul sebagai parameter. (Jadi untuk memproses banyak node, Anda harus mengambil yang pertama secara terpisah untuk membuat root.)

Saya akhirnya menggunakan solusi ini di atas, memodifikasinya untuk mengambil tipe <Node>sehingga memiliki akses ke Nodekiri dan kanan (anak-anak).

pohon dibuat dengan abego TreeLayout

TT--
sumber
0

Berikut ini cara lain untuk memvisualisasikan struktur pohon Anda: simpan node sebagai file xml dan kemudian biarkan browser Anda menunjukkan hierarki:

class treeNode{
    int key;
    treeNode left;
    treeNode right;

    public treeNode(int key){
        this.key = key;
        left = right = null;
    }

    public void printNode(StringBuilder output, String dir){
        output.append("<node key='" + key + "' dir='" + dir + "'>");
        if(left != null)
            left.printNode(output, "l");
        if(right != null)
            right.printNode(output, "r");
        output.append("</node>");
    }
}

class tree{
    private treeNode treeRoot;

    public tree(int key){
        treeRoot = new treeNode(key);
    }

    public void insert(int key){
        insert(treeRoot, key);
    }

    private treeNode insert(treeNode root, int key){
        if(root == null){
            treeNode child = new treeNode(key);
            return child;
        }

        if(key < root.key)
            root.left = insert(root.left, key);
        else if(key > root.key)
            root.right = insert(root.right, key);

        return root;
    }

    public void saveTreeAsXml(){
        StringBuilder strOutput = new StringBuilder();
        strOutput.append("<?xml version=\"1.0\" encoding=\"UTF-8\"?>");
        treeRoot.printNode(strOutput, "root");
        try {
            PrintWriter writer = new PrintWriter("C:/tree.xml", "UTF-8");
            writer.write(strOutput.toString());
            writer.close();
        }
        catch (FileNotFoundException e){

        }
        catch(UnsupportedEncodingException e){

        }
    }
}

Ini kode untuk mengujinya:

    tree t = new tree(1);
    t.insert(10);
    t.insert(5);
    t.insert(4);
    t.insert(20);
    t.insert(40);
    t.insert(30);
    t.insert(80);
    t.insert(60);
    t.insert(50);

    t.saveTreeAsXml();

Dan hasilnya terlihat seperti ini:

masukkan deskripsi gambar di sini

pengguna4617883
sumber
0
using map...
{
Map<Integer,String> m = new LinkedHashMap<>();

         tn.printNodeWithLvl(node,l,m);

        for(Entry<Integer, String> map :m.entrySet()) {
            System.out.println(map.getValue());
        }
then....method


   private  void printNodeWithLvl(Node node,int l,Map<Integer,String> m) {
       if(node==null) {
           return;
       }
      if(m.containsKey(l)) {
          m.put(l, new StringBuilder(m.get(l)).append(node.value).toString());
      }else {
          m.put(l, node.value+"");
      }
      l++;
      printNodeWithLvl( node.left,l,m);
      printNodeWithLvl(node.right,l,m);

    }
}
satish
sumber
0

ini adalah salah satu versi paling sederhana yang bisa saya terapkan. Saya harap ini membantu Anda

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def add(self, data):

        if data < self.data:
            if self.left is None:
                self.left = Node(data)
            else:
                self.left.add(data)
        if data > self.data:
            if self.right is None:
                self.right = Node(data)
            else:
                self.right.add(data)

    def display(self):
        diff = 16
        start = 50
        c = ' '

        this_level = [(self, start)]

        while this_level:
            next_level = list()
            last_line = ''

            for node, d in this_level:
                line = last_line + c*(d - len(last_line)) + str(node.data)
                print(line, end='\r')
                last_line = line

                if node.left:
                    next_level.append((node.left, d - diff))
                if node.right:
                    next_level.append((node.right, d + diff))
                this_level = next_level
                diff = max(diff//2, 2)
            print('\n')


if __name__ == '__main__':
    from random import randint, choice
    values = [randint(0, 100) for _ in range(10)]
    bst = Node(choice(values))
    for data in values:
        bst.add(data)

    bst.display()

sourabh gupta
sumber