Home IT Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Java implementation chain store binary tree     - Comparison of one-time transaction and CTE insert data (Database)

- How to configure security services under Linux (Linux)

- Docker Private Registry Installation Guide at CentOS6.X (Linux)

- Linux package management operations Basic entry (Linux)

- Ubuntu U disk do not have write privileges can only read but not write (Linux)

- Git uses a standard process (Linux)

- Linux environment to configure Apache + Django + wsgi (Server)

- Ubuntu prompt / lack of boot space solutions (Linux)

- Fragment Android developers learning to resolve (Programming)

- How to install Ubuntu strategy game Wesnoth 1.12.0 (Linux)

- Make Windows boot disk to install USB in Ubuntu Linux (Linux)

- Linux, ls command to achieve (Linux)

- Ubuntu Gitolite management Git Server code base permissions (Server)

- Analysis JavaBean (Programming)

- 11 examples in Linux df command (Linux)

- Gitolite how to import other Git repositories (Server)

- Install the open source database PostgreSQL 9.4 and phpMyAdmin on Ubuntu (Database)

- Use eCryptFS encrypt files and directories on Linux (Linux)

- Difference in MySQL VARCHAR and CHAR data format (Database)

- Use Ansible efficient delivery Docker container (Server)

 
         
  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:      
 
- DataGuard the MRP can not start to analyze and solve problems (Database)
- CentOS / RHEL 6 was repeated prohibited under the SNMP connection log (Server)
- Detailed software to run UnixBench (Linux)
- MySQL stored procedures and triggers (Database)
- Hackers is how the invasion and control of Things devices? (Linux)
- C ++ containers (Programming)
- Linux md5sum verify file integrity (Linux)
- How to set the default Fedora from the command line (Linux)
- Simple solution CC attack under Linux VPS (Linux)
- Go powerful development server simple example (Server)
- Hibernate4 The Hello World (basic environmental structures) (Programming)
- Android Studio commonly used shortcuts and how to follow the Eclipse Shortcuts (Linux)
- Under CentOS Linux automatic backup MySQL database daily (Database)
- Qt shared memory interprocess communication (Programming)
- Hadoop + Zookeeper NameNode achieve high availability (Server)
- Using Linux / Unix Text processing (Linux)
- Windows Remote Desktop Management CentOS 6.4 (Linux)
- C # compiler to achieve functional use in the runtime (Programming)
- Hadoop 2.5 Pseudo distribution installation (Server)
- Oracle Linux 6.4 (BOND) dual NIC teaming combat - Annotated (Linux)
     
           
     
  CopyRight 2002-2016 newfreesoft.com, All Rights Reserved.