Home IT Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Java implementation chain store binary tree     - MySQL master recovery from failure using binlog (Database)

- KUbuntu / Ubuntu 14.04 (downgrade) installed SVN 1.7 (Linux)

- Iptables principle (Linux)

- CentOS 6.5 installation and configuration Cobbler (Server)

- Linux common network tools: hping Advanced Host Scan (Linux)

- Examples of Python any parameters (Programming)

- Netapp storage routine inspections and information gathering (Linux)

- Oracle database online redo logs are several methods of recovery of deleted (Database)

- Do not find ifconfig eth0 and IP address under CentOS6.5 (Linux)

- Linux development environment to build and use the directory structure and file --Linux (Linux)

- Percona MySQL 5.6 semi-synchronous replication (Database)

- Install VMware Tools in Debian (Linux)

- Build ftp server under CentOS 6.5 (Server)

- Ubuntu 12.04 kernel configuration automatically restart and crash dump (Linux)

- How to set cache valid time in Apache (Server)

- Ubuntu Telnet service settings (Linux)

- The Java utility, JavaMail (Programming)

- Java how to achieve bubble sort the problem Arraylist (Programming)

- Three details reflect the Unix system security (Linux)

- Use Nginx as a load balancer (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:      
 
- How to contribute code on GitHub uploads (Linux)
- Linux system security reinforcement system by masquerading method (Linux)
- PostgreSQL 9.3.2 Json type of use (Database)
- Observation network performance tools for Linux (Linux)
- Install Visual Studio Code in Ubuntu (Linux)
- build Android environment on Ubuntu 12.04 (Server)
- Django url () function Detailed (Programming)
- Installing software on Ubuntu: apt-get and dpkg difference (Linux)
- To install Oracle Database Details and FAQ Summary under CentOS (Database)
- Linux set to select the appropriate level of security of the network according to deployment (Linux)
- Analysis of potential problems through custom Orabbix monitoring Oracle (Database)
- MySQL separation Amoeba achieve literacy (Database)
- To install Xen in Ubuntu 12.04 (Linux)
- Ubuntu installation under Scrapy (Linux)
- CentOS 6.4 under PXE + Kickstart unattended operating system installation (Programming)
- Java concurrent programming combat (using synchronized synchronization method) (Programming)
- Build Golang development environment configuration on Ubuntu 14.04 (Linux)
- Construction CA certificate using OpenSSL command line (Server)
- grep command usage (Linux)
- To install PostgreSQL 9.4 (Database)
     
           
     
  CopyRight 2002-2016 newfreesoft.com, All Rights Reserved.