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.

Binary Tree Traversal method
.

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

分类:Java 时间:2010-07-25 人气:353
分享到:
blog comments powered by Disqus

相关文章

  • Unlimited-class classification tree 2010-09-20

    <? Php echo "<meta http-equiv=\"Content-Type\" content=\"text/html; charset=utf-8\" />"; $ Directory = array (/ / List array assignment '0 '=> Array ('',' Main Menu '), '1 '=> Array ('0', 'first-level directory

  • C + + with a new dynamic to create multi-dimensional arrays 2010-06-20

    http://blog.csdn.net/gabby1985/archive/2006/05/11/724911.aspx

  • What is the root node in the hierarchical model what is the parent node, and leaf nodes 2010-12-31

    In the hierarchical model, there are several terms: the root, the father nodes, leaves on top of the current node has no other nodes, this node is called the root; Father node is the node above the current node, the node above the node is called the

  • orace find all the leaf nodes of parent node 2011-02-26

    select colunmnid, connect_by_root (colunmnid) precolumnid from Test WHERE precolumnid IS NOT null connect by prior colunmnid = precolumnid order by 1,2 Create Table Test (colunmnid Integer, precolumnid Integer) Insert Into Test Values ​​(0, Null); In

  • objective-c image array storage space 2011-01-12

    NSMutableArray * imgSheet = [NSMutableArray arrayWithCapacity: 4]; for (int i = 0; i <4; i + +) { [ImgSheet addObject: [NSNull null]]; }

  • php-array operation foreach.each.reset.list 2010-03-03

    foreach PHP 4 introduced a foreach structure, and much like Perl and other languages. This is just a convenient way to traverse the array. foreach works only on arrays, when trying to use it for other data type or an uninitialized variable will gener

  • Understanding of Array, get hold of plainly 2010-10-08

    1. <br /> <br /> Array bigger picture is a reference type array, which is meant an array of memory allocated on the managed heap, and we maintain the stack pointer is not his real array. Then we analyze the next array element, the element whic

  • perl-list and array. basic operation. qw. scalar 2010-03-07

    1, List is included in brackets the value of a sequence, can be any value can be empty, such as: (1, 5.3, "hello", 2), an empty list: (). Note: The list contains only a numeric value (such as: (43.2)) and the value itself (ie: 43.2) is different

  • Bring you in-depth understanding of Web site databases distributed memory 2010-03-06

    In the Web 2.0 era, the website will always be faced with rapidly increasing traffic, but our application of how to satisfy the user's access needs, but basically we have this situation are the performance bottlenecks are in the database, this will n

iOS 开发

Android 开发

Python 开发

JAVA 开发

开发语言

PHP 开发

Ruby 开发

搜索

前端开发

数据库

开发工具

开放平台

Javascript 开发

.NET 开发

云计算

服务器

Copyright (C) codeweblog.com, All Rights Reserved.

CodeWeblog.com 版权所有 黔ICP备15002463号-1

processed in 0.287 (s). 14 q(s)