二叉树的构造与遍历

二叉树的构造与遍历

• 节点

  package top.lphblog.tree;
  public class treeNode {
      int val;
      treeNode left;
      treeNode right;
      public treeNode(int val){
          this.val=val;
          left=right=null;
      }
      public void setLeft(treeNode left){
          this.left=left;
      }
      public void setRight(treeNode right){
          this.right=right;
      }
  }
  ​

• 手动构造

  public void setLeft(treeNode left){
          root.left=left;
      }
      public void setRight(treeNode right){
          root.right=right;
      }
      public void setRoot(int val){
          root=new treeNode(val);
      }

• 先序构造

    private treeNode  reorderStructure(){
          int n=sc.nextInt();
          treeNode node=null;
          if(n!=-1){
              node = new treeNode(n);
              node.left=reorderStructure();
              node.right=reorderStructure();
          }
          return node;
      }
      public void preCreate(){
          root=reorderStructure();
      }

• 先序遍历

     private void preTravels(treeNode node){
          if(node!=null){
              System.out.print(node.val+" ");
              preTravels(node.left);
              preTravels(node.right);
          }
      }
      public void reorderTravels(){
          preTravels(root);
      }

• 中序遍历

      private void midTravels(treeNode node){
          if(node!=null){
              midTravels(node.left);
              System.out.print(node.val+" ");
              midTravels(node.right);
          }
      }
      public void InOrderTraverse(){
          midTravels(root);
      }

• 后序遍历

      private void postorder(treeNode node){
          if(node!=null){
              postorder(node.left);
              postorder(node.right);
              System.out.print(node.val+" ");
          }
      }
      public void postOrdTravels(){
          postorder(root);
      }