Binary Tree Traversal method

First, the data structure classification

(A) logical structure

  1. Set (no series Relations)
  2. Linear structure (linear form): array, linked lists, stacks, queues
  3. 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.

Binary Tree Traversal method

  • 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
  1. package tree.bintree;
  2. / **
  3. * Create a non-complete binary tree, complete binary tree, full binary tree
  4. *
  5. * As the binary tree of nodes to increase no rules, so here is a simple use of the delivery
  6. * Views of the entire tree is created, but not to design a method of an add and delete nodes
  7. *
  8. * @ Author jzj
  9. * @ Date 2009-12-23
  10. * /
  11. public class BinTree (/ / Bin = Binary (binary, binary)
  12. protected Entry root; / / root
  13. private int size; / / the tree nodes
  14. / **
  15. * The tree node structure
  16. * @ Author jzj
  17. * @ Date 2009-12-23
  18. * /
  19. protected static class Entry (
  20. int elem; / / data field, where we as a number
  21. Entry left; / / left subtree
  22. Entry right; / / the right subtree
  23. public Entry (int elem) (
  24. this. elem = elem;
  25. )
  26. public String toString () (
  27. return "number =" + elem;
  28. )
  29. )
  30. / **
  31. * According to a given number of nodes to create a complete binary tree or a full binary tree
  32. * @ Param nodeCount the total number of nodes to create
  33. * /
  34. public void createFullBiTree (int nodeCount) (
  35. root = recurCreateFullBiTree (1, nodeCount);
  36. )
  37. / **
  38. * Create a complete binary tree recursive
  39. * @ Param num node number
  40. * @ Param nodeCount the total number of nodes
  41. * @ Return TreeNode return node created
  42. * /
  43. private Entry recurCreateFullBiTree (int num, int nodeCount) (
  44. size + +;
  45. Entry rootNode = new Entry (num); / / root
  46. / / If the left subtree is to create the left subtree
  47. if (num * 2 <= nodeCount) (
  48. rootNode.left = recurCreateFullBiTree (num * 2, nodeCount);
  49. / / If you can also create the right subtree, then create
  50. if (num * 2 + 1 <= nodeCount) (
  51. rootNode.right = recurCreateFullBiTree (num * 2 + 1, nodeCount);
  52. )
  53. )
  54. return (Entry) rootNode;
  55. )
  56. / **
  57. * Based on a given array to create a tree, the tree can be completely normal, but also a binary tree binary tree
  58. * Array of 0's that did not create the position of the node
  59. * @ Param nums array specifies the number of nodes to be created, if it is 0, that does not create
  60. * /
  61. public void createBinTree (int [] nums) (
  62. root = recurCreateBinTree (nums, 0);
  63. )
  64. / **
  65. * Create a binary tree recursive
  66. * @ Param nums array specifies the number of nodes to be created, if it is 0, that does not create
  67. * @ Param index need to use an array of which element to create the node, if the element is 0, not create
  68. * @ Return TreeNode return node created will eventually return to the root of the tree
  69. * /
  70. private Entry recurCreateBinTree (int [] nums, int index) (
  71. / / Specify the index of the number is not zero on the nodes only need to create
  72. if (nums [index]! = 0) (
  73. size + +;
  74. Entry rootNode = new Entry (nums [index ]);// root
  75. / / If the left subtree is to create the left subtree
  76. if ((index + 1) * 2 <= nums.length) (
  77. rootNode.left = (Entry) recurCreateBinTree (nums, (index + 1) * 2 - 1);
  78. / / If you can also create the right subtree, then create
  79. if ((index + 1) * 2 + 1 <= nums.length) (
  80. rootNode.right = (Entry) recurCreateBinTree (nums, (index + 1) * 2);
  81. )
  82. )
  83. return (Entry) rootNode;
  84. )
  85. return null;
  86. )
  87. public int size () (
  88. return size;
  89. )
  90. / / Get the left-most node in the tree
  91. public int getLast () (
  92. Entry e = root;
  93. while (e.right! = null) (
  94. e = e.right;
  95. )
  96. return e.elem;
  97. )
  98. / / Test
  99. public static void main (String [] args) (
  100. / / Create a full binary tree
  101. BinTree binTree = new BinTree ();
  102. binTree.createFullBiTree (15);
  103. System.out.println (binTree.size ());// 15
  104. System.out.println (binTree.getLast ());// 15
  105. / / Create a complete binary tree
  106. binTree = new BinTree ();
  107. binTree.createFullBiTree (14);
  108. System.out.println (binTree.size ());// 14
  109. System.out.println (binTree.getLast ());// 7
  110. / / Create a non-complete binary tree
  111. binTree = new BinTree ();
  112. int [] nums = new int [] (1, 2, 3, 4, 0, 0, 5, 0, 6, 0, 0, 0, 0, 7, 8);
  113. binTree.createBinTree (nums);
  114. System.out.println (binTree.size ());// 8
  115. System.out.println (binTree.getLast ());// 8
  116. )
  117. )

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
  1. package tree.bintree;
  2. / **
  3. * Three internal binary tree traversal: preorder, inorder, postorder
  4. * But Either way, the left sub-tree to traverse the right subtree is traversed before traversing these three methods are
  5. * Must follow the convention
  6. * @ Author jzj
  7. * @ Date 2009-12-23
  8. * /
  9. public class BinTreeInOrder extends BinTree (
  10. / **
  11. * Node visitors can visit methods need to be rewritten
  12. * /
  13. static abstract class Visitor (
  14. void visit (Object ele) (
  15. System.out.print (ele + "");
  16. )
  17. )
  18. public void preOrder (Visitor v) (
  19. preOrder (v, root);
  20. )
  21. / **
  22. * Pre-order recursive tree traversal pre = prefix (prefix)
  23. * @ Param node the node to traverse
  24. * /
  25. private void preOrder (Visitor v, Entry node) (
  26. / / If you come pass the node is not empty, then the traversal, note, leaf nodes of child nodes for the null
  27. if (node! = null) (
  28. v.visit (node.elem); / / first loop through the parent node
  29. preOrder (v, node.left); / / and then traverse the left node
  30. preOrder (v, node.right); / / end loop through the right node
  31. )
  32. )
  33. public void inOrder (Visitor v) (
  34. inOrder (v, root);
  35. )
  36. / **
  37. * Tree in the order recursive traversal in = infix (infix)
  38. * @ Param node the node to traverse
  39. * /
  40. private void inOrder (Visitor v, Entry node) (
  41. / / If you come pass the node is not empty, then the traversal, note, leaf nodes of child nodes for the null
  42. if (node! = null) (
  43. inOrder (v, node.left); / / first loop through the left node
  44. v.visit (node.elem); / / then loop through the parent node
  45. inOrder (v, node.right); / / end loop through the right node
  46. )
  47. )
  48. public void postOrder (Visitor v) (
  49. postOrder (v, root);
  50. )
  51. / **
  52. * Post-order recursive tree traversal post = postfix (suffix)
  53. * @ Param node the node to traverse
  54. * /
  55. private void postOrder (Visitor v, Entry node) (
  56. / / If you come pass the node is not empty, then the traversal, note, leaf nodes of child nodes for the null
  57. if (node! = null) (
  58. postOrder (v, node.left); / / first loop through the left node
  59. postOrder (v, node.right); / / and then traverse the right node
  60. v.visit (node.elem); / / end loop through the parent node
  61. )
  62. )
  63. / / Test
  64. public static void main (String [] args) (
  65. / / Create a binary tree
  66. int [] nums = new int [] (1, 2, 3, 4, 0, 0, 5, 0, 6, 0, 0, 0, 0, 7, 8);
  67. BinTreeInOrder treeOrder = new BinTreeInOrder ();
  68. treeOrder.createBinTree (nums);
  69. System.out.print ("before traversing -");
  70. treeOrder.preOrder (new Visitor () (
  71. ));
  72. System.out.println ();
  73. System.out.print ("in order traversal -");
  74. treeOrder.inOrder (new Visitor () (
  75. ));
  76. System.out.println ();
  77. System.out.print ("After traversing -");
  78. treeOrder.postOrder (new Visitor () (
  79. ));
  80. / *
  81. * Output:
  82. * Preorder traversal - 1 2 4 6 3 5 7 8
  83. * Inorder traversal - 4 6 2 1 3 7 5 8
  84. * After traversing - 6 4 2 7 8 5 3 1
  85. * /
  86. )
  87. )

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
  1. package tree.bintree;
  2. import java.util.Iterator;
  3. import java.util.LinkedList;
  4. import java.util.Stack;
  5. / **
  6. External binary tree traversal *: depth-first (first root), breadth (level) first traversal
  7. *
  8. * @ Author jzj
  9. * @ Date 2009-12-23
  10. * /
  11. public class BinTreeOutOrder extends BinTree (
  12. / **
  13. * Binary tree depth first traversal order (ie, the first root of binary tree traversal) iterator, the iterator can be used outside
  14. * Non-recursive traversal, which is a binary tree structure in an external traversal algorithm, it does not use
  15. * Characteristics of a binary tree structure itself (left and right sub-tree recursive) recursive traversal
  16. * @ Author jzj
  17. * /
  18. private class DepthOrderIterator implements Iterator (
  19. / / Stack is stored in each node
  20. private Stack stack = new Stack ();
  21. public DepthOrderIterator (Entry node) (
  22. / / 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
  23. stack.push (node);
  24. )
  25. / / Does the next element
  26. public boolean hasNext () (
  27. if (stack.isEmpty ()) (
  28. return false;
  29. )
  30. return true;
  31. )
  32. / / Remove an element
  33. public Entry next () (
  34. if (hasNext ()) (
  35. / / Get the stack element
  36. Entry treeNode = (Entry) stack.pop ();// first visit to the root
  37. if (treeNode.right! = null) (
  38. stack.push (treeNode.right); / / then put the right child node
  39. )
  40. if (treeNode.left! = null) (
  41. stack.push (treeNode.left); / / last child node into the left, but the visit prior to the right node
  42. )
  43. / / Get the node back to traverse
  44. return treeNode;
  45. ) Else (
  46. / / If the stack is empty
  47. return null;
  48. )
  49. )
  50. public void remove () (
  51. throw new UnsupportedOperationException ();
  52. )
  53. )
  54. / **
  55. * To the outside world to provide first Traversal Iterator
  56. * @ Return Iterator iterator returns the first Traversal
  57. * /
  58. public Iterator createPreOrderItr () (
  59. return new DepthOrderIterator (root);
  60. )
  61. / **
  62. * Breadth-first traversal binary tree iterator, the iterator can be used outside
  63. * Non-recursive traversal, which is a binary tree structure in a traversal algorithm outside, it does not use
  64. * Characteristics of a binary tree structure itself (left and right sub-tree recursive) recursive traversal
  65. * @ Author jzj
  66. * /
  67. private class LevelOrderIterator implements Iterator (
  68. / / Use the queue structure to achieve level traversal of the node storage queue
  69. private LinkedList queue = new LinkedList ();
  70. public LevelOrderIterator (Entry node) (
  71. if (node! = null) (
  72. / / Will root into the team
  73. queue.addLast (node);
  74. )
  75. )
  76. / / Does the next element
  77. public boolean hasNext () (
  78. if (queue.isEmpty ()) (
  79. return false;
  80. )
  81. return true;
  82. )
  83. / / Remove an element
  84. public Entry next () (
  85. if (hasNext ()) (
  86. / / Get the stack elements Diego
  87. Entry treeNode = (Entry) queue.removeFirst ();
  88. if (treeNode.left! = null) (/ / if the left subtree, ordered to join the list
  89. queue.addLast (treeNode.left);
  90. )
  91. if (treeNode.right! = null) (/ / if the right subtree, ordered to join the list
  92. queue.addLast (treeNode.right);
  93. )
  94. / / Get the node back to traverse
  95. return treeNode;
  96. ) Else (
  97. / / If the queue is empty
  98. return null;
  99. )
  100. )
  101. public void <


Tree traversal mode | Share - branch and bound method (for finding optimal loading)

  • 02:32
  • View (0)
  • Comments (0)
  • Related Recommendation


Comment


Comment
  • del.icio.us
  • StumbleUpon
  • Digg
  • TwitThis
  • Mixx
  • Technorati
  • Facebook
  • NewsVine
  • Reddit
  • Google
  • LinkedIn
  • YahooMyWeb

Related Posts of Binary Tree Traversal method

  • XSL Study Notes 6 XSLT built-in template rules

    XSL Study Notes 6 XSLT built-in template rules The definition of the correct template rules to match the XML tree node is the key to XSLT applications. In order for the source document tree nodes in the absence of a clear case of matching rules can b ...

  • XSL Study Notes 4 XSLT pattern matching syntax

    XSL Study Notes 4 XSLT pattern matching syntax Template rule through the use of models to match the document tree nodes. Mode specifies a set of conditions, is used to select the node to deal with. Pattern matching syntax not only able to match the e ...

  • subtree

    In the Faceye basic version (open source), the use of a large number of tree structure, such as Taiwan and Taiwan management of the tree, the user RSS subscription and classification tree, classification of user blog site navigation tree, open source ...

  • Image linked to yui-ext Site - Ext JS

    I was looking through Firebug and found that an image from a tree is linking to this site. The code <li> <div> <span/> <span unselectable="on">Automotive</span> </div> <ul/> It didn't copy that well from Fireb

  • The design of user rights management (database)

    Since the project needs! Need to develop a set of permissions on the existing system management system! Prior to first talk about how the management of the authority of the bar. At that time, the limited time available. Therefore, only temporary admi ...

  • Black Box Testing & white-box testing

    Any work product (Note that any work product) can use one of the following two methods for testing. Black Box Testing: the function of a known product design specifications that can be achieved for each test to prove whether it meets the requirements ...

  • AJAX + XML-based XLoadTree dynamic loading of components of the document tree JS

    Tree node has recently started to load and read a good article, look around them to share BeanSoft evaluation: This component tree is not perfect, but it is based on self-object-oriented, based on the AJAX + XML + DOM, the head is also relatively small, r

  • Ext tree icon displayed abnormal solutions

    tree graph shows abnormal solutions 1, tree involved in the js or jsp page insert: Ext.BLANK_IMAGE_URL = 'ext / resources / images / default / tree / s.gif'; Or (jsp Medium) <script type="text/javascript"> Ext.BLANK_IMAGE_URL ...

  • Learn Flex

    Flex for the most need to know 10 things 1. Flex is a web standard MXML is a Flex application's standard language, which allows developers to customize the structure of applications, including not only the layout also includes the class structure, and

  • WEB test summary (architecture, design) the best part

    1, for a total test architecture 1) thin-client, business logic rules in the server-side implementation of the majority. Such as news sites, portals, information websites. 2) fat client, a high security requirements, frequent interaction, complex bus ...

blog comments powered by Disqus
Recent
Recent Entries
Tag Cloud
Random Entries