一：二叉树的概念

 

（完全二叉树简单理解：除最后一层其它层都是满的，最后一层元素从左往右依次连续。（满二叉树也是完全二叉树））

 

二：二叉树的遍历：

（1）前序遍历：根->左->右

 1 public void preOrder(){
 2     //先输出根节点
 3     System.out.println(this);
 4     //递归向左子树前序遍历
 5     if(this.left != null){
 6         this.left.preOrder();
 7     }
 8     //递归向右子树前序遍历      
 9     if(this.right != null){
10         this.right.preOrder();
11     }
12 }

（2）中序遍历：左->根->右

 1  public void preOrder(){
 2      //递归向左子树前序遍历
 3      if(this.left != null){
 4          this.left.preOrder();
 5      }
 6      //输出根节点
 7      System.out.println(this);
 8      //递归向右子树前序遍历      
 9      if(this.right != null){
10          this.right.preOrder();
11      }
12 }

（3）后续遍历：左->右->根

 1  public void preOrder(){
 2      //递归向左子树前序遍历
 3      if(this.left != null){
 4          this.left.preOrder();
 5      }
 6      //递归向右子树前序遍历      
 7      if(this.right != null){
 8          this.right.preOrder();
 9      }
10      //输出根节点
11      System.out.println(this);
12 }