Binary Tree Traversal method

Jul 25 posted in Java (RSS), comments.

First, the data structure classification

(A) logical structure

Set (no series Relations)
Linear structure (linear form): array, linked lists, stacks, queues
Nonlinear structure: tree, graph, multi-dimensional arrays

(B) the storage structure

Order (array) storage structure, chain storage structure, the index storage structure, the hash storage structure

Second, related to the nature of binary tree

The degree of node: a node number of the sub-tree node record for the degree.
Tree of degree: the degree of all nodes in the degree of the largest nodule, leaf nodes of degree zero.
Height of the tree: a tree of the maximum level recorded for the number of tree height (or depth).
Ordered (unordered) tree: if the tree nodes as the subtree with the order from left to right, that can not be exchanged, claimed the tree as an ordered tree. Otherwise known as the disordered tree.
Binary i-layer (i ≥ 1) on at most 2 ^ (i-1) nodes.
Depth k of the binary tree has at most 2 ^ k-1 nodes (k ≥ 1).
Any binary tree, leaf nodes if the n0, degree 2 nodes is n2, then n0 = n2 +1.
With n nodes complete binary tree of depth ( ㏒ 2 ^ n) (rounded down) + 1.
There are n nodes on a complete binary tree nodes at different levels from top to bottom, from left to right number, then for any node i (1 ≤ i ≤ n) are: if i = 1, then node i is the binary tree roots, no parents; if i> 1, then its parents is i / 2 (rounded down). If 2i> n, then node i has no children nodes, otherwise the left child is 2i. If 2i +1> n, then node i has no right child, otherwise the right child is 2i +1.
If the depth of a binary tree with k 2 ^ k-1 nodes, claimed it as full binary tree. Full binary tree is a complete binary tree.

For the complete binary tree, the degree of a node can only be as a number or 0.
For the binary tree, if the leaf nodes to n0, the number of nodes is 1 to n1, the number of nodes is 2 to n2, then the node number n = n0 + n1 + n2.
For any tree, the total number of nodes = each node degree and + 1
Binary tree height is equal to the root and the farthest leaf node (with the most ancestral node) between the number of branches. Empty tree height is -1. Only a single element of the binary tree, its height to 0.

Third, binary tree traversal

Traversal is based on a strategy to visit each node in the tree, and only one visit.

(A) of the binary tree structure to achieve

Java code

package tree.bintree;
/ **
* Create a non-complete binary tree, complete binary tree, full binary tree
*
* As the binary tree of nodes to increase no rules, so here is a simple use of the delivery
* Views of the entire tree is created, but not to design a method of an add and delete nodes
*
* @ Author jzj
* @ Date 2009-12-23
* /
public class BinTree (/ / Bin = Binary (binary, binary)
protected Entry root; / / root
private int size; / / the tree nodes
/ **
* The tree node structure
* @ Author jzj
* @ Date 2009-12-23
* /
protected static class Entry (
int elem; / / data field, where we as a number
Entry left; / / left subtree
Entry right; / / the right subtree
public Entry (int elem) (
this. elem = elem;
)
public String toString () (
return "number =" + elem;
)
)
/ **
* According to a given number of nodes to create a complete binary tree or a full binary tree
* @ Param nodeCount the total number of nodes to create
* /
public void createFullBiTree (int nodeCount) (
root = recurCreateFullBiTree (1, nodeCount);
)
/ **
* Create a complete binary tree recursive
* @ Param num node number
* @ Param nodeCount the total number of nodes
* @ Return TreeNode return node created
* /
private Entry recurCreateFullBiTree (int num, int nodeCount) (
size + +;
Entry rootNode = new Entry (num); / / root
/ / If the left subtree is to create the left subtree
if (num * 2 <= nodeCount) (
rootNode.left = recurCreateFullBiTree (num * 2, nodeCount);
/ / If you can also create the right subtree, then create
if (num * 2 + 1 <= nodeCount) (
rootNode.right = recurCreateFullBiTree (num * 2 + 1, nodeCount);
)
)
return (Entry) rootNode;
)
/ **
* Based on a given array to create a tree, the tree can be completely normal, but also a binary tree binary tree
* Array of 0's that did not create the position of the node
* @ Param nums array specifies the number of nodes to be created, if it is 0, that does not create
* /
public void createBinTree (int [] nums) (
root = recurCreateBinTree (nums, 0);
)
/ **
* Create a binary tree recursive
* @ Param nums array specifies the number of nodes to be created, if it is 0, that does not create
* @ Param index need to use an array of which element to create the node, if the element is 0, not create
* @ Return TreeNode return node created will eventually return to the root of the tree
* /
private Entry recurCreateBinTree (int [] nums, int index) (
/ / Specify the index of the number is not zero on the nodes only need to create
if (nums [index]! = 0) (
size + +;
Entry rootNode = new Entry (nums [index ]);// root
/ / If the left subtree is to create the left subtree
if ((index + 1) * 2 <= nums.length) (
rootNode.left = (Entry) recurCreateBinTree (nums, (index + 1) * 2 - 1);
/ / If you can also create the right subtree, then create
if ((index + 1) * 2 + 1 <= nums.length) (
rootNode.right = (Entry) recurCreateBinTree (nums, (index + 1) * 2);
)
)
return (Entry) rootNode;
)
return null;
)
public int size () (
return size;
)
/ / Get the left-most node in the tree
public int getLast () (
Entry e = root;
while (e.right! = null) (
e = e.right;
)
return e.elem;
)
/ / Test
public static void main (String [] args) (
/ / Create a full binary tree
BinTree binTree = new BinTree ();
binTree.createFullBiTree (15);
System.out.println (binTree.size ());// 15
System.out.println (binTree.getLast ());// 15
/ / Create a complete binary tree
binTree = new BinTree ();
binTree.createFullBiTree (14);
System.out.println (binTree.size ());// 14
System.out.println (binTree.getLast ());// 7
/ / Create a non-complete binary tree
binTree = new BinTree ();
int [] nums = new int [] (1, 2, 3, 4, 0, 0, 5, 0, 6, 0, 0, 0, 0, 7, 8);
binTree.createBinTree (nums);
System.out.println (binTree.size ());// 8
System.out.println (binTree.getLast ());// 8
)
)

package tree.bintree;

/**
 *   Create a non-complete binary tree  .  Complete binary tree. Full binary tree  
 *
 *   Binary tree of nodes to increase because there is no rules, so here is a simple use of the delivery  
 *   Views of the whole tree created, but not to design a method of an add and delete nodes  
 * 
 * @author jzj
 * @date 2009-12-23
 */
public class BinTree {// Bin=Binary(  Binary, binary  )

        protected Entry root;//  Root  
        private int size;//  Tree nodes  

        /**
         *   Tree node structure  
         * @author jzj
         * @date 2009-12-23
         */
        protected static class Entry {
                int elem;//  Data field, where we as a number  
                Entry left;//  Left subtree  
                Entry right;//  Right subtree  

                public Entry(int elem) {
                        this.elem = elem;
                }

                public String toString() {
                        return " number=" + elem;
                }
        }

        /**
         *   According to the given number of nodes to create a complete binary tree or a full binary tree  
         * @param nodeCount   To create a total number of nodes  
         */
        public void createFullBiTree(int nodeCount) {
                root = recurCreateFullBiTree(1, nodeCount);
        }

        /**
         *   Create a complete binary tree recursive  
         * @param num   Node number  
         * @param nodeCount   Total number of nodes  
         * @return TreeNode   Return created node  
         */
        private Entry recurCreateFullBiTree(int num, int nodeCount) {
                size++;
                Entry rootNode = new Entry(num);//  Root  
                //  If the left subtree, create the left subtree  
                if (num * 2 <= nodeCount) {
                        rootNode.left = recurCreateFullBiTree(num * 2, nodeCount);
                        //  If you can also create the right subtree, then create  
                        if (num * 2 + 1 <= nodeCount) {
                                rootNode.right = recurCreateFullBiTree(num * 2 + 1, nodeCount);
                        }
                }
                return (Entry) rootNode;
        }

        /**
         *   Created according to the given array of a tree, the tree can be a complete binary tree, but also ordinary binary tree  
         *   0 array that does not create the position of the nodes  
         * @param nums   Array specifies the number of nodes to be created, if  0,  That does not create  
         */
        public void createBinTree(int[] nums) {
                root = recurCreateBinTree(nums, 0);
        }

        /**
         *   Create a binary tree recursively  
         * @param nums   Array specifies the number of nodes to be created, if  0,  That does not create  
         * @param index   Which need to use elements of the array to create a node, if the element is  0,  Not create  
         * @return TreeNode   Return the created node will eventually return to the root of the tree  
         */
        private Entry recurCreateBinTree(int[] nums, int index) {
                //  Index on the specified number is not zero only need to create nodes on the  
                if (nums[index] != 0) {
                        size++;
                        Entry rootNode = new Entry(nums[index]);//  Root  
                        //  If the left subtree, create the left subtree  
                        if ((index + 1) * 2 <= nums.length) {
                                rootNode.left = (Entry) recurCreateBinTree(nums, (index + 1) * 2 - 1);
                                //  If you can also create the right subtree, then create  
                                if ((index + 1) * 2 + 1 <= nums.length) {
                                        rootNode.right = (Entry) recurCreateBinTree(nums, (index + 1) * 2);
                                }
                        }
                        return (Entry) rootNode;
                }
                return null;

        }

        public int size() {
                return size;
        }

        //  Take the left-most node in the tree  
        public int getLast() {
                Entry e = root;
                while (e.right != null) {
                        e = e.right;
                }
                return e.elem;
        }

        //  Test  
        public static void main(String[] args) {

                //  Create a full binary tree  
                BinTree binTree = new BinTree();
                binTree.createFullBiTree(15);
                System.out.println(binTree.size());//15
                System.out.println(binTree.getLast());//15

                //  Create a complete binary tree  
                binTree = new BinTree();
                binTree.createFullBiTree(14);
                System.out.println(binTree.size());//14
                System.out.println(binTree.getLast());//7

                //  Create a non-complete binary tree  
                binTree = new BinTree();
                int[] nums = new int[] { 1, 2, 3, 4, 0, 0, 5, 0, 6, 0, 0, 0, 0, 7, 8 };
                binTree.createBinTree(nums);
                System.out.println(binTree.size());//8
                System.out.println(binTree.getLast());//8

        }
}

(B) the use of recursive binary tree traversal itself features (an internal traversal)

As the binary tree by a recursive nature, a non-empty binary tree can be seen as the root node, the left subtree and right subtree three parts, as if in turn part of the information traversing these three, also traverse the entire binary tree. In accordance with the left sub-tree to traverse the right sub-tree before the convention, according to the different locations to access the root node, the binary can be the first order, in order, the order of three kinds of traversal methods.

Java code

package tree.bintree;
/ **
* Three internal binary tree traversal: preorder, inorder, postorder
* But Either way, the left sub-tree to traverse the right subtree is traversed before traversing these three methods are
* Must follow the convention
* @ Author jzj
* @ Date 2009-12-23
* /
public class BinTreeInOrder extends BinTree (
/ **
* Node visitors can visit methods need to be rewritten
* /
static abstract class Visitor (
void visit (Object ele) (
System.out.print (ele + "");
)
)
public void preOrder (Visitor v) (
preOrder (v, root);
)
/ **
* Pre-order recursive tree traversal pre = prefix (prefix)
* @ Param node the node to traverse
* /
private void preOrder (Visitor v, Entry node) (
/ / If you come pass the node is not empty, then the traversal, note, leaf nodes of child nodes for the null
if (node! = null) (
v.visit (node.elem); / / first loop through the parent node
preOrder (v, node.left); / / and then traverse the left node
preOrder (v, node.right); / / end loop through the right node
)
)
public void inOrder (Visitor v) (
inOrder (v, root);
)
/ **
* Tree in the order recursive traversal in = infix (infix)
* @ Param node the node to traverse
* /
private void inOrder (Visitor v, Entry node) (
/ / If you come pass the node is not empty, then the traversal, note, leaf nodes of child nodes for the null
if (node! = null) (
inOrder (v, node.left); / / first loop through the left node
v.visit (node.elem); / / then loop through the parent node
inOrder (v, node.right); / / end loop through the right node
)
)
public void postOrder (Visitor v) (
postOrder (v, root);
)
/ **
* Post-order recursive tree traversal post = postfix (suffix)
* @ Param node the node to traverse
* /
private void postOrder (Visitor v, Entry node) (
/ / If you come pass the node is not empty, then the traversal, note, leaf nodes of child nodes for the null
if (node! = null) (
postOrder (v, node.left); / / first loop through the left node
postOrder (v, node.right); / / and then traverse the right node
v.visit (node.elem); / / end loop through the parent node
)
)
/ / Test
public static void main (String [] args) (
/ / Create a binary tree
int [] nums = new int [] (1, 2, 3, 4, 0, 0, 5, 0, 6, 0, 0, 0, 0, 7, 8);
BinTreeInOrder treeOrder = new BinTreeInOrder ();
treeOrder.createBinTree (nums);
System.out.print ("before traversing -");
treeOrder.preOrder (new Visitor () (
));
System.out.println ();
System.out.print ("in order traversal -");
treeOrder.inOrder (new Visitor () (
));
System.out.println ();
System.out.print ("After traversing -");
treeOrder.postOrder (new Visitor () (
));
/ *
* Output:
* Preorder traversal - 1 2 4 6 3 5 7 8
* Inorder traversal - 4 6 2 1 3 7 5 8
* After traversing - 6 4 2 7 8 5 3 1
* /
)
)

package tree.bintree;

/**
 *   Three internal binary tree     Traversal  :  Pre-order. In order  .  Postorder  
 *  But Either way, the left sub-tree traversal traverse the right subtree is traversed before traversing these three methods are  
 *   Conventions must be followed  
 * @author jzj
 * @date 2009-12-23
 */
public class BinTreeInOrder extends BinTree {

        /**
         *   Node visitor, can be rewritten  visit  Methods  
         */
        static abstract class Visitor {
                void visit(Object ele) {
                        System.out.print(ele + " ");
                }
        }

        public void preOrder(Visitor v) {
                preOrder(v, root);
        }

        /**
         *   Recursive pre-order tree traversal   pre=prefix(  Prefix  )
         * @param node   Node to traverse  
         */
        private void preOrder(Visitor v, Entry node) {
                //  If the node passed in is not empty, the traversal  ,  Note, for the leaf node's children  null
                if (node != null) {
                        v.visit(node.elem);//  The first parent node traversal  
                        preOrder(v, node.left);//  And then traverse the left node  
                        preOrder(v, node.right);//  Finally, the right node traversal  
                }
        }

        public void inOrder(Visitor v) {
                inOrder(v, root);
        }

        /**
         *   Recursively traverse the tree in order   in=infix(  Infix  )
         * @param node   Node to traverse  
         */
        private void inOrder(Visitor v, Entry node) {
                //  If the node passed in is not empty, the traversal  ,  Note, for the leaf node's children  null
                if (node != null) {
                        inOrder(v, node.left);//  First traverse the left node  
                        v.visit(node.elem);//  Parent node and then traversing  
                        inOrder(v, node.right);//  Finally, the right node traversal  
                }
        }

        public void postOrder(Visitor v) {
                postOrder(v, root);
        }

        /**
         *   Recursive postorder tree traversal   post=postfix(  Suffix  )
         * @param node   Node to traverse  
         */
        private void postOrder(Visitor v, Entry node) {
                //  If the node passed in is not empty, the traversal  ,  Note, for the leaf node's children  null
                if (node != null) {
                        postOrder(v, node.left);//  First traverse the left node  
                        postOrder(v, node.right);//  And then traverse the right child  
                        v.visit(node.elem);//  Finally, the parent node traversal  
                }
        }

        //  Test  
        public static void main(String[] args) {

                //  Create a binary tree  
                int[] nums = new int[] { 1, 2, 3, 4, 0, 0, 5, 0, 6, 0, 0, 0, 0, 7, 8 };
                BinTreeInOrder treeOrder = new BinTreeInOrder();
                treeOrder.createBinTree(nums);
                System.out.print("  Preorder traversal   - ");
                treeOrder.preOrder(new Visitor() {
                });
                System.out.println();
                System.out.print("  Inorder traversal   - ");
                treeOrder.inOrder(new Visitor() {
                });
                System.out.println();
                System.out.print("  Postorder traversal   - ");
                treeOrder.postOrder(new Visitor() {
                });
                /*
                 * output:
                 *   Preorder traversal   - 1 2 4 6 3 5 7 8 
                 *   Inorder traversal   - 4 6 2 1 3 7 5 8 
                 *   Postorder traversal   - 6 4 2 7 8 5 3 1 
                 */
        }
}

(C) non-recursive binary tree traversal (an external traversal)

1, stack and queue using non-recursive traversal of the binary tree

Java code

package tree.bintree;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Stack;
/ **
External binary tree traversal *: depth-first (first root), breadth (level) first traversal
*
* @ Author jzj
* @ Date 2009-12-23
* /
public class BinTreeOutOrder extends BinTree (
/ **
* Binary tree depth first traversal order (ie, the first root of binary tree traversal) iterator, the iterator can be used outside
* Non-recursive traversal, which is a binary tree structure in an external traversal algorithm, it does not use
* Characteristics of a binary tree structure itself (left and right sub-tree recursive) recursive traversal
* @ Author jzj
* /
private class DepthOrderIterator implements Iterator (
/ / Stack is stored in each node
private Stack stack = new Stack ();
public DepthOrderIterator (Entry node) (
/ / Root stack, but before the child nodes will be placed immediately around the stack, that is better than the left and right child nodes of the root first visit
stack.push (node);
)
/ / Does the next element
public boolean hasNext () (
if (stack.isEmpty ()) (
return false;
)
return true;
)
/ / Remove an element
public Entry next () (
if (hasNext ()) (
/ / Get the stack element
Entry treeNode = (Entry) stack.pop ();// first visit to the root
if (treeNode.right! = null) (
stack.push (treeNode.right); / / then put the right child node
)
if (treeNode.left! = null) (
stack.push (treeNode.left); / / last child node into the left, but the visit prior to the right node
)
/ / Get the node back to traverse
return treeNode;
) Else (
/ / If the stack is empty
return null;
)
)
public void remove () (
throw new UnsupportedOperationException ();
)
)
/ **
* To the outside world to provide first Traversal Iterator
* @ Return Iterator iterator returns the first Traversal
* /
public Iterator createPreOrderItr () (
return new DepthOrderIterator (root);
)
/ **
* Breadth-first traversal binary tree iterator, the iterator can be used outside
* Non-recursive traversal, which is a binary tree structure in a traversal algorithm outside, it does not use
* Characteristics of a binary tree structure itself (left and right sub-tree recursive) recursive traversal
* @ Author jzj
* /
private class LevelOrderIterator implements Iterator (
/ / Use the queue structure to achieve level traversal of the node storage queue
private LinkedList queue = new LinkedList ();
public LevelOrderIterator (Entry node) (
if (node! = null) (
/ / Will root into the team
queue.addLast (node);
)
)
/ / Does the next element
public boolean hasNext () (
if (queue.isEmpty ()) (
return false;
)
return true;
)
/ / Remove an element
public Entry next () (
if (hasNext ()) (
/ / Get the stack elements Diego
Entry treeNode = (Entry) queue.removeFirst ();
if (treeNode.left! = null) (/ / if the left subtree, ordered to join the list
queue.addLast (treeNode.left);
)
if (treeNode.right! = null) (/ / if the right subtree, ordered to join the list
queue.addLast (treeNode.right);
)
/ / Get the node back to traverse
return treeNode;
) Else (
/ / If the queue is empty
return null;
)
)
public void <