Home IT Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Java implementation chain store binary tree     - Linux, security encryption to transfer files between machines (Linux)

- Ubuntu: To install chat client Chatty 0.6.1 (Linux)

- ARM runtime environment built from scratch using QEMU emulator (Linux)

- CentOS 7 x64 compiler installation Tengine 2.0.3 Comments (Server)

- How do I delete a NEEDS RECOVERY rollback state of undo tablespace (Database)

- Linux file and directory management - ls, cp, mv (Linux)

- Ubuntu 12.04 LTS installation configuration JDK1.6.0_45 (Linux)

- Ubuntu How to install screen recording tool Simple Screen Recorder 0.3.1 (Linux)

- To setup NOTRACK and TRACK of conntrack in iptables (Linux)

- ACL permissions Linux command (Linux)

- Linux installation beautify early experience (Linux)

- lolcat: an output terminal rainbow effects in the Linux command-line tool (Linux)

- Pydev installed and configured on the Eclipse (Linux)

- Several Ceph performance optimization of new methods and ideas (2015 SH Ceph Day after flu reference) (Server)

- Windows 8.1 and Ubuntu 14.04 dual system uninstall Ubuntu Tutorial (Linux)

- CentOS install video converter FFmpeg and cutting tools segmenter (Linux)

- Fast Sort Algorithms (Programming)

- VirtualBox install Windows 8.1 has encountered an error 0x000000C4 solutions (Linux)

- SteamOS installation under Ubuntu 14.04 (Linux)

- The Java development environment to build under Ubuntu 14.04 (Linux)

 
         
  Java implementation chain store binary tree
     
  Add Date : 2017-08-31      
         
       
         
  Binary definition:

Binary Tree (BinaryTree) is n (n>=0) finite set of nodes, or it is an empty set (n = 0), or consists of a root and two disjoint, are referred to as the root of the left binary subtree and right subtree composition.

Binary tree traversal are: preorder (NLR), preorder (LNR), after preorder (LRN), and hierarchy traversal.

Note:

A binary tree can be uniquely determined by the sequence and the first sequence of binary sequence in order;

A binary tree can be uniquely determined by the sequence and the subsequent sequence of binary sequence;

A binary tree can be uniquely determined by the sequence and the sequence of binary sequence in order;

However, a binary tree can not be uniquely determined by the sequence and the first sequence of binary sequence after sequence.

Java implementation chain stores as well as its various binary tree traversal algorithm:

Tree node:

public class TreeNode < E> {
    private E data; // data fields
    private TreeNode < E> lchild; // Left child
    private TreeNode < E> rchild; // right child
    
    TreeNode () {}
    
    TreeNode (E e) {
        this.data = e;
    }
    
    TreeNode (E data, TreeNode < E> lchild, TreeNode < E> rchild) {
        this.data = data;
        this.lchild = lchild;
        this.rchild = rchild;
    }
    
    public void setData (E data) {
        this.data = data;
    }
    
    public E getData () {
        return this.data;
    }
    
    public void setLchild (TreeNode < E> lchild) {
        this.lchild = lchild;
    }
    
    public TreeNode < E> getLchild () {
        return this.lchild;
    }
    
    public void setRchild (TreeNode < E> rchild) {
        this.rchild = rchild;
    }
    
    public TreeNode < E> getRchild () {
        return this.rchild;
    }
}

Binary Tree Java implementation:

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/ **
 * @author Cherish
 * Storage Structure binary tree
 * @param < E>
 * /

public class BinaryTree < E> {
    private TreeNode < E> root; // root node
    private List < TreeNode> nodeList = null; // binary tree node chain structure
    
    public BinaryTree () {
        
    }
    
    public BinaryTree (TreeNode < E> root) {
        this.root = root;
    }
    
    // Put an array into a complete binary tree
    public TreeNode < E> buildTree (E [] array) {
        nodeList = new LinkedList < TreeNode> ();
        // The array element in turn is converted to TreeNode node, stored in the list
        for (int i = 0; i < array.length; i ++) {
            nodeList.add (new TreeNode (array [i]));
        }
        // Former (array.length / 2 - 1) a parent, according to the relationship between parent and child figures established complete binary tree node
        // For complete binary tree, top to bottom, left to right are numbered 0,1,2,3 .... N, then i> 0 node, its left child is (2 * i + 1 ),
        // Its right child is (2 * i + 2)
        for (int j = 0; j < (array.length / 2-1); j ++) {
            // Left child
            nodeList.get (j) .setLchild (nodeList.get (j * 2 + 1));
            // Right child
            nodeList.get (j) .setRchild (nodeList.get (j * 2 + 2));
        }
        // Last a parent: a parent because the last may not have the right child, so separate treatment
        int index = array.length / 2 -1;
        // Left child
        nodeList.get (index) .setLchild (nodeList.get (index * 2 + 1));
        // Right child: If the length of the array is odd children have the right
        if (array.length% 2 == 1) {
            nodeList.get (index) .setRchild (nodeList.get (index * 2 + 2));
        }
        root = nodeList.get (0); // set the root
        return root;
    }
    
    // Get the height of the tree
    public int height (TreeNode < E> node) {
        if (node == null) {
            return 0;
        } Else {
            int i = height (node.getLchild ());
            int j = height (node.getRchild ());
            ? Return (i < j) (j + 1) :( i + 1);
        }
    }
    
    // Get the number of nodes
    public int size (TreeNode < E> node) {
        if (node == null) {
            return 0;
        } Else {
            return 1+ size (node.getLchild ()) + size (node.getRchild ());
        }
    }
    
    // Recursive preorder NLR
    public void preOrder (TreeNode < E> node) {
        if (node! = null) {
            System.out.print (node.getData () + "");
            preOrder (node.getLchild ());
            preOrder (node.getRchild ());
        }
    }
    // Non-recursive preorder NLR
    public void nonRecPreOrder (TreeNode < E> node) {
        Stack < TreeNode < E >> nodeStack = new Stack < TreeNode < E >> ();
        TreeNode < E> nodeTemp = node; // nodeTemp as a pointer traversal
        while (nodeTemp! = null ||! nodeStack.isEmpty ()) {// When nodeTemp stack is not empty or not empty cycle
            if (nodeTemp! = null) {// non-null pointer to the root, traverse left subtree
                nodeStack.push (nodeTemp); // root pointers into the stack
                System.out.print (nodeStack.peek () getData () + "".); // Root pointer back stack, the root access
                nodeTemp = nodeTemp.getLchild (); // Every non-empty binary tree first encounter left to go
            } Else {// then go to the right subtree
                nodeTemp = nodeStack.pop ();
                nodeTemp = nodeTemp.getRchild ();
            }
        }
    }
    
    // Recursive traversal LNR
    public void inOrder (TreeNode < E> node) {
        if (node! = null) {
            inOrder (node.getLchild ());
            System.out.print (node.getData () + "");
            inOrder (node.getRchild ());
        }
    }
    
    // Non-recursive traversal LNR
    public void nonRecInOrder (TreeNode < E> node) {
        Stack < TreeNode < E >> nodeStack = new Stack < TreeNode < E >> ();
        TreeNode < E> nodeTemp = node; // nodeTemp as a pointer traversal
        while (nodeTemp! = null ||! nodeStack.isEmpty ()) {// When nodeTemp stack is not empty or not empty cycle
            if (nodeTemp! = null) {// non-null pointer to the root, traverse left subtree
                nodeStack.push (nodeTemp); // root pointers into the stack
                nodeTemp = nodeTemp.getLchild (); // Every non-empty binary tree first encounter left to go
            } Else {
                nodeTemp = nodeStack.pop (); // root pointer back stack, the root access
                System.out.print (nodeTemp.getData () + "");
                nodeTemp = nodeTemp.getRchild (); // then go to the right subtree
            }
        }
    }
    
    // Recursive realization after preorder LNR
    public void postOrder (TreeNode < E> node) {
        if (node! = null) {
            postOrder (node.getLchild ());
            postOrder (node.getRchild ());
            System.out.print (node.getData () + "");
        }
    }
    
    After // non-recursive preorder LNR
    public void nonRecPostOrder (TreeNode < E> node) {
        Stack < TreeNode < E >> nodeStack = new Stack < TreeNode < E >> ();
        TreeNode < E> nodeTemp = node; // nodeTemp as a pointer traversal
        TreeNode < E> preNode = null; // node represents the last visit
        while (nodeTemp! = null ||! nodeStack.isEmpty ()) {// When nodeTemp stack is not empty or not empty cycle
            while (nodeTemp! = null) {// has been left, traverse left subtree
                nodeStack.push (nodeTemp);
                nodeTemp = nodeTemp.getLchild ();
            }
            nodeTemp = nodeStack.peek ();
            if (nodeTemp.getRchild () == null || nodeTemp.getRchild () == preNode) {// right subtree is empty or the right subtree has been accessed, the node stack
                nodeTemp = nodeStack.pop ();
                System.out.print (nodeTemp.getData () + "");
                preNode = nodeTemp; // the node assigned to the most recent access node
                nodeTemp = null; // here is very important, just out of the stack node set is empty, while one of the conditions corresponding to the loop, otherwise endless loop
            } Else {
                nodeTemp = nodeTemp.getRchild (); // Traverse the right subtree
            }
        }
    }
    
    
    // Traverse the level
    public void levelOrder (TreeNode < E> root) {
        Queue < TreeNode < E >> nodeQueue = new LinkedList < TreeNode < E >> ();
        TreeNode < E> node = null;
        nodeQueue.add (root); // root node into the team
        while (! nodeQueue.isEmpty ()) {// queue is not empty cycle
            node = nodeQueue.peek ();
            System.out.print (node.getData () + "");
            nodeQueue.poll (); // team head element from the team
            if (node.getLchild ()! = null) {// the left sub-tree is not empty, then the left subtree into the queue
                nodeQueue.add (node.getLchild ());
            }
            if (node.getRchild ()! = null) {// right subtree is not empty, then the right subtree into the queue
                nodeQueue.add (node.getRchild ());
            }
        }
    }
    
    public static void main (String args []) {
        // An array into a complete binary tree
        Object [] array = {1,2,3,4,5,6,7,8};
        BinaryTree bt = new BinaryTree ();
        TreeNode root = bt.buildTree (array);
        System.out.print ( "height of the tree:");
        System.out.println (bt.height (root));
        System.out.print ( "node number:");
        System.out.println (bt.size (root));
        System.out.println ( "preorder:");
        bt.preOrder (root);
        System.out.println ( "\ n" + "non-recursive preorder:");
        bt.nonRecPreOrder (root);
        System.out.println ();
        
  
        System.out.println ( "preorder:");
        bt.inOrder (root);
        System.out.println ( "\ n" + "non-recursive traversal:");
        bt.nonRecInOrder (root);
        System.out.println ();
  
        System.out.println ( "postorder:");
        bt.postOrder (root);
        System.out.println ( "\ n" + "after the non-recursive preorder:");
        bt.nonRecPostOrder (root);
        System.out.println ();
        
        System.out.println ( "traverse the level:");
        bt.levelOrder (root);
        
        // Manual build a binary tree
        TreeNode nodeA = new TreeNode ( "A");
        TreeNode nodeB = new TreeNode ( "B");
        TreeNode nodeC = new TreeNode ( "C");
        TreeNode nodeD = new TreeNode ( "D");
        TreeNode nodeE = new TreeNode ( "E");
        TreeNode nodeF = new TreeNode ( "F");
        TreeNode nodeG = new TreeNode ( "G");
        TreeNode nodeH = new TreeNode ( "H");
        TreeNode nodeI = new TreeNode ( "I");
        nodeA.setLchild (nodeB);
        nodeA.setRchild (nodeD);
        nodeB.setRchild (nodeC);
        nodeD.setLchild (nodeE);
        nodeD.setRchild (nodeF);
        nodeF.setLchild (nodeG);
        nodeF.setRchild (nodeI);
        nodeG.setRchild (nodeH);
        
        
        System.out.println ( "\ n \ n" + "*****************");
        System.out.print ( "height of the tree:");
        System.out.println (bt.height (nodeA));
        System.out.print ( "node number:");
        System.out.println (bt.size (nodeA));
        System.out.println ( "preorder:");
        bt.preOrder (nodeA);
        System.out.println ();
  
        System.out.println ( "preorder:");
        bt.inOrder (nodeA);
        System.out.println ();
  
        System.out.println ( "postorder:");
        bt.postOrder (nodeA);
        System.out.println ();
        
        System.out.println ( "traverse the level:");
        bt.levelOrder (nodeA);
    }
}

Run a result of the program:

Height of the tree: 4
The number of nodes: 8
Preorder:
12485367
Nonrecursive preorder:
12485367
Preorder:
84251637
Nonrecursive preorder:
84251637
Postorder:
84526731
After the non-recursive preorder:
84526731
Traverse the level:
12345678

*****************
Height of the tree: 5
The number of nodes: 9
Preorder:
A B C D E F G H I
Preorder:
B C A E D G H F I
Postorder:
C B E H G I F D A
Traverse the level:
A B D C E F G I H
     
         
       
         
  More:      
 
- ssh using scp: / directory: Permission denied (Server)
- MySQL error: ERROR 1175: You are using safe update mode solution (Database)
- 20 Linux commands interview questions and answers (Linux)
- C ++ Fundamentals study notes (Programming)
- Ubuntu configuration SVN and http mode access (Server)
- Use cmake to compile and install MySQL 5.5 (Database)
- Installation Yarock 1.1.4 Music Player in Ubuntu (Linux)
- Using Maven to download Spring (Linux)
- Apache Tomcat integration and resin (Server)
- Difference Docker mirror and containers (Server)
- Asynchronous JavaScript loading (Programming)
- Docker in the development and practice of IFTTT (Server)
- Linux Nginx installation and configuration instructions (Server)
- Pydev installed and configured on the Eclipse (Linux)
- Linux System Getting Started Learning: Linux how to install 7zip (Linux)
- Linux linux system security (Linux)
- Gnu Linux - Ubuntu System Clean-term consolidation (Linux)
- Using IntelliJ IDEA Import Spark Spark latest source code and compile the source code (Linux)
- Linux kernel panic (because glibc result) Repair (Linux)
- Binary tree traversal: the first sequence in order preorder recursive and non-recursive and traversal sequence (Programming)
     
           
     
  CopyRight 2002-2016 newfreesoft.com, All Rights Reserved.