Explanation of binary tree

Preface

      Data structures are often the focus of a programming interview . Before the interview , Candidates need to master the linked list 、 Trees 、 Stack 、 Data structures such as queues and hash tables , And their operation . This blog post mainly explains the related knowledge of binary tree operation , It mainly includes the establishment of binary tree 、 Loop and recursive writing of traversal methods .

      Binary tree is an important type of tree structure . The data structure abstracted from many practical problems is often in the form of binary tree , Even ordinary trees can be transformed into binary trees , Moreover, the storage structure and algorithm of binary tree are relatively simple , So binary tree is very important .

Binary tree java Realization

      First, create a binary tree, as shown in the following figure , Then the binary tree is traversed （ The implementation of traversal operation is divided into recursive implementation and non recursive implementation ）, At the same time, it also provides some methods, such as obtaining parent nodes 、 Get left child 、 Right child, etc .

package cn.edu.ujn.nk; import java.util.Stack; /** *  Chain storage of binary trees  * @author WWX */  public class BinaryTree {           private TreeNode root=null;            public BinaryTree(){          root=new TreeNode(1,"rootNode(A)");      }            /**     *  Create a binary tree      * <pre>      *           A     *     B          C     *  D     E            F     *  </pre>      * @param root     * @author WWX     */      public void createBinTree(TreeNode root){          TreeNode newNodeB = new TreeNode(2,"B");          TreeNode newNodeC = new TreeNode(3,"C");          TreeNode newNodeD = new TreeNode(4,"D");          TreeNode newNodeE = new TreeNode(5,"E");          TreeNode newNodeF = new TreeNode(6,"F");          root.leftChild=newNodeB;          root.rightChild=newNodeC;          root.leftChild.leftChild=newNodeD;          root.leftChild.rightChild=newNodeE;          root.rightChild.rightChild=newNodeF;      }            public boolean isEmpty(){          return root==null;      }        // The height of the tree       public int height(){          return height(root);      }            // Number of nodes       public int size(){          return size(root);      }            private int height(TreeNode subTree){          if(subTree == null)              return 0;	//  Recursion ends ： The height of the empty tree is 0        else{            int i = height(subTree.leftChild);            int j = height(subTree.rightChild);            return (i < j) ? (j + 1) : (i + 1);        }    }          private int size(TreeNode subTree){          if(subTree == null){            return 0;          }else{              return 1 + size(subTree.leftChild) + size(subTree.rightChild);          }      }            // Returns the parent node       public TreeNode parent(TreeNode element){          return (root == null|| root == element) ? null : parent(root, element);    }          public TreeNode parent(TreeNode subTree,TreeNode element){          if(subTree == null)              return null;          if(subTree.leftChild == element || subTree.rightChild == element)            // Return the address of the parent node               return subTree;          TreeNode p;        //  First look in the left subtree , If not found in the left subtree , I went to Youzi tree to find           if((p = parent(subTree.leftChild, element)) != null)            // Recursively search in the left subtree               return p;          else              // Recursively search in the right subtree               return parent(subTree.rightChild, element);      }            public TreeNode getLeftChildNode(TreeNode element){          return (element != null) ? element.leftChild : null;      }            public TreeNode getRightChildNode(TreeNode element){          return (element != null) ? element.rightChild : null;      }            public TreeNode getRoot(){          return root;    }            // When releasing a node , The left and right subtrees of this node have been released ,      // So follow-up traversal should be used , When a node is accessed, the storage space of the node is released       public void destroy(TreeNode subTree){          // Delete root as subTree The subtree of           if(subTree!=null){              // Delete left subtree               destroy(subTree.leftChild);              // Delete the right subtree               destroy(subTree.rightChild);              // Delete root               subTree=null;          }      }            public void traverse(TreeNode subTree){          System.out.println("key:"+subTree.key+"--name:"+subTree.data);;          traverse(subTree.leftChild);          traverse(subTree.rightChild);      }            // The former sequence traversal       public void preOrder(TreeNode subTree){          if(subTree!=null){              visted(subTree);              preOrder(subTree.leftChild);              preOrder(subTree.rightChild);          }      }            // In the sequence traversal       public void inOrder(TreeNode subTree){          if(subTree!=null){              inOrder(subTree.leftChild);              visted(subTree);              inOrder(subTree.rightChild);          }      }            // Subsequent traversal       public void postOrder(TreeNode subTree) {          if (subTree != null) {              postOrder(subTree.leftChild);              postOrder(subTree.rightChild);              visted(subTree);          }      }            // Non recursive implementation of preorder traversal       public void nonRecPreOrder(TreeNode p){          Stack<TreeNode> stack=new Stack<TreeNode>();          TreeNode node=p;          while(node!=null||stack.size()>0){              while(node!=null){                  visted(node);                  stack.push(node);                  node=node.leftChild;              }              while(stack.size()>0){                  node=stack.pop();                  node=node.rightChild;              }           }      }            // Non recursive implementation of medium order traversal       public void nonRecInOrder(TreeNode p){          Stack<TreeNode> stack =new Stack<BinaryTree.TreeNode>();          TreeNode node =p;          while(node!=null||stack.size()>0){              // There are left subtrees               while(node!=null){                  stack.push(node);                  node=node.leftChild;              }              // The stack is not empty               if(stack.size()>0){                  node=stack.pop();                  visted(node);                  node=node.rightChild;              }          }      }            // The non recursive implementation of post order traversal       public void noRecPostOrder(TreeNode p){          Stack<TreeNode> stack=new Stack<BinaryTree.TreeNode>();          TreeNode node =p;          while(p!=null){              // Left subtree into stack               for(;p.leftChild!=null;p=p.leftChild){                  stack.push(p);              }              // The current node has no right subtree or the right subtree has been output               while(p!=null&&(p.rightChild==null||p.rightChild==node)){                  visted(p);                  // Record the last exported node                   node =p;                  if(stack.empty())                      return;                  p=stack.pop();              }              // Deal with the right subtree               stack.push(p);              p=p.rightChild;          }      }      public void visted(TreeNode subTree){          subTree.isVisted=true;          System.out.println("key:"+subTree.key+"--name:"+subTree.data);;      }                  /**     *  Node data structure of binary tree      * @author WWX     */      private class  TreeNode{        private int key = 0;        private String data = null;          private boolean isVisted = false;        private TreeNode leftChild = null;        private TreeNode rightChild = null;                    public TreeNode(){}                    /**         * @param key   Sequence code          * @param data  Data fields          */          public TreeNode(int key,String data){              this.key = key;              this.data = data;              this.leftChild = null;              this.rightChild = null;          }      }            // test       public static void main(String[] args) {          BinaryTree bt = new BinaryTree();          bt.createBinTree(bt.root);          System.out.println("the size of the tree is " + bt.size());          System.out.println("the height of the tree is " + bt.height());                    System.out.println("*** Recursive implementation ****( The former sequence traversal )[ABDECF] Traverse *****************");          bt.preOrder(bt.root);                    System.out.println("*** Recursive implementation ****( In the sequence traversal )[DBEACF] Traverse *****************");          bt.inOrder(bt.root);                   System.out.println("*** Recursive implementation ****( After the sequence traversal )[DEBFCA] Traverse *****************");          bt.postOrder(bt.root);                    System.out.println("*** Non recursive implementation ****( The former sequence traversal )[ABDECF] Traverse *****************");          bt.nonRecPreOrder(bt.root);                    System.out.println("*** Non recursive implementation ****( In the sequence traversal )[DBEACF] Traverse *****************");          bt.nonRecInOrder(bt.root);                    System.out.println("*** Non recursive implementation ****( After the sequence traversal )[DEBFCA] Traverse *****************");          bt.noRecPostOrder(bt.root);      }  }

​