天天看点

显示二叉树的算法

Regarding to "Binary Tree Display", I try lots of solutions to display tree, but it's difficult to solve, finally I refer to this method  displayTree() in << Data Structures and Algorithms >>. ==========================================================================

packagebinary_tree_path;

importjava.util.Stack;

classNode {

    int value;

    Node LeftN;

    Node RightN;

    publicNode(int value) {

          this.value = value;

    }

}

classBinaryTreePath {

    privateNode root;

    publicBinaryTreePath() {

          this.root = null;

    }

    public voidinsert(int value) {

          Node currentN = root;

          if(root == null) {

              root = new Node(value);

          } else{

              while (currentN != null) {

                   if(currentN.value < value) {

                       if (currentN.RightN == null) {

                             currentN.RightN= new Node(value);

                             break;

                       }

                       currentN = currentN.RightN;

                   } else{

                       if (currentN.LeftN == null) {

                             currentN.LeftN = newNode(value);

                             break;

                       }

                       currentN = currentN.LeftN;

                   }

              }

          }

    }

    public voiddisplayTree() {

          Stack<Node>globle_stack = new Stack<Node>();

          globle_stack.push(root);

          Stack<Node>local_stack;

          booleanisRowEmpty = false;

          intnBanks = 32;

          while(!isRowEmpty) {

              isRowEmpty = true;

              local_stack = newStack<Node>();

              for (int i = 0; i < nBanks; i++)

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

              while (!globle_stack.isEmpty()) {

                   Node tmpN= globle_stack.pop();

                   if(tmpN != null) {

                       System.out.print(tmpN.value);

                       local_stack.push(tmpN.LeftN);

                       local_stack.push(tmpN.RightN);

                       if (tmpN.LeftN != null || tmpN.RightN != null)

                             isRowEmpty= false;

                   } else{

                       System.out.print("**");

                       local_stack.push(null);

                       local_stack.push(null);

                   }

                   for(int i = 0; i < 2 * nBanks - 1; i++)

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

              }

              System.out.println();

              while (!local_stack.isEmpty()) {

                   globle_stack.push(local_stack.pop());

              }

              nBanks /= 2;

          }

    }

}

public classBinaryTreePathTest {

    public static voidmain(String[] args) {

          BinaryTreePath btp= new BinaryTreePath();

          btp.insert(50);

          btp.insert(80);

          btp.insert(30);

          btp.insert(60);

          btp.insert(90);

          btp.insert(17);

          btp.insert(55);

          btp.insert(15);

          btp.insert(19);

          btp.insert(16);

          btp.insert(12);

          btp.insert(35);

          btp.insert(32);

          btp.insert(37);

          btp.insert(65);

          btp.insert(85);

          btp.insert(95);

          btp.insert(100);

          btp.insert(39);

          btp.insert(82);

          btp.insert(66);

          btp.insert(52);

          btp.insert(18);

          btp.insert(20);

          btp.insert(31);

          btp.insert(33);

          btp.insert(86);

          btp.insert(93);

          btp.insert(63);

          btp.insert(56);

          btp.insert(36);

          btp.displayTree();

    }

}