Home IT Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Java implementation chain store binary tree     - Iptables use examples (Linux)

- Use Observium to monitor your network and servers (Server)

- Use rfkill soft-switching and Bluetooth wireless capabilities in Linux (Linux)

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

- Vim useful plugin: YouCompleteMe (Linux)

- Import and export myloader accelerate mydumper (Database)

- Network security system (Network)

- Ubuntu Locale configuration problem solving Can not set LC_CTYPE (Linux)

- Ubuntu users to install voice switch instructs the applet (Linux)

- Detailed usage history command (Linux)

- Oracle how to assess the true concurrent session (Database)

- HomeKit Human Interface Guidelines (Linux)

- DRBD + Heartbeat solve NFS single point of failure (Server)

- Debian users to install FFmpeg 2.2.2 (Linux)

- Linux OOM killer mechanism (Linux)

- Elaborate .NET Multithreading: Using Task (Programming)

- Camera-based face recognition OpenCV crawl and storage format (Python) (Linux)

- The difference between Objective-C language nil, Nil, NULL, NSNull (Programming)

- Share Java-based multithreading file case (Programming)

- To use Android RecyclerView (Programming)

 
         
  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:      
 
- Shutdown - an advanced shutdown artifact (Linux)
- Ubuntu cut screen method (Linux)
- Java String type time compare the size (Programming)
- Linux dd command make U disk boot disk (Linux)
- Perl said method B if A judge (Programming)
- The difference between equals and == in Java (Programming)
- Ubuntu 15.04 install Complete Guide (Linux)
- AngularJS achieve picture upload feature (Programming)
- To achieve Linux Security (Linux)
- Ubuntu 14.04 VirtualBox can not start solution (Linux)
- The Linux-based security settings Ipchains Firewall (Linux)
- Java implementation linear table - represents the order of representation and chain (Programming)
- Zabbix system email alert Python script (Server)
- Python2 ---- function using dictionaries (Programming)
- RedHat Linux 6.5 Enterprise Edition installation Redis 3.0.3 (Database)
- Linux more command Detailed (Linux)
- To teach you a trick to find the real IP address (Linux)
- Schema snapshot rollback (Database)
- How to understand Python yield keyword (Programming)
- Using IntelliJ IDEA Import Spark Spark latest source code and compile the source code (Linux)
     
           
     
  CopyRight 2002-2016 newfreesoft.com, All Rights Reserved.