二叉树相关问题（JAVA实现）

二叉树(Binarry Tree)是n(n大于等于0)个数据元素的有限集，它或为空集(n=0),或者有唯一的根的元素，且其余元素分成两个互不相交的子集，每个子集自身也是一棵二叉树，分别称为左子树和右子树。（二叉树中的左子树和右子树是两棵互不相交的二叉树）。 二叉树中其左，右子树均为空的结点称为叶子结点，所有非叶子结点称为分支结点。二叉树中叶子结点的最大层次数定义为二叉树的深度。 满二叉树：二叉树中所有的分支结点的度数都为2，且叶子结点都在同一层次；
二叉树的基本性质： (1). 在二叉树的第 i 层上至多有 2^(i-1) 个结点（i 大于等于1）； (2). 深度为 k 的二叉树 至多有 2^k -1 个结点 （k 大于等于1）； (3). 对任何一棵树 T，如果其终端结点电数为No ,度为2 的结点数为N2  ，则No=N2+1  ;
结点定义： class TreeNode {       boolean visited =false;       int data;       TreeNode left;       TreeNode right; } 主函数：  public static void main(String[] args) {
 
  TreeNode root = new TreeNode();
  root.data = 9;
  TreeNode temp01 = new TreeNode();
  temp01.data = 2;
  root.left = temp01;
  TreeNode temp02 = new TreeNode();
  temp02.data = 5;
  root.right = temp02;
  TreeNode temp03 = new TreeNode();
  temp03.data = 1;
  root.left.left = temp03;
  TreeNode temp04 = new TreeNode();
  temp04.data = 4;
  root.left.right = temp04;
  TreeNode temp05 = new TreeNode();
  temp05.data = 7;
  root.right.left = temp05;
  TreeNode temp06 = new TreeNode();
  temp06.data = 8;
  root.left.left.left = temp06;
  TreeNode temp07 = new TreeNode();
  temp07.data = 3;
  root.left.left.right = temp07;    System.out.println("--------先序遍历----------");
  PreSelectTree1(root);
  System.out.println();
  System.out.println("---------中序遍历---------");
  InSelectTree(root);
  System.out.println();
  System.out.println("---------后序遍历---------");
  SelectTree2(root);
  System.out.println();
  System.out.println("----------叶节点个数-----------");
  int i = leafNum(root);
  System.out.println(i);
  System.out.println("----------层次遍历二叉树-----------------");
  levelOrder(root);
  System.out.println();
  int n=getNodeNum(root);
  System.out.println("---------结点个数-------");
  System.out.println(n);
  
  System.out.println();
  int H=getDepth(root);
  System.out.println("---------深度---------");
  System.out.println(H);
  System.out.println();
}   // 二叉树遍历 （1）. 中序遍历 a.如果二叉树为空，则为空操作； b.如果二叉树不为空，则中序遍历，先遍历左子树，再访问根结点，最后遍历右子树；  public static void InSelectTree(TreeNode root) {
      if (root == null)
          return ;
        SelectTree(root.left);
        System.out.print(root.data + " ");
        SelectTree(root.right);
 }  (2) . 先序遍历 a. 如果二叉树为空，则为空操作； b. 如果二叉树不为空，则先序遍历，先访问根结点，再遍历左子树，最后遍历有右子树； public static void PreSelectTree(TreeNode root) {
  if (root == null)
   return;
  System.out.print(root.data + " ");
  SelectTree1(root.left);
  SelectTree1(root.right);
 } （3）.后序遍历 a.如果二叉树为空，则为空操作； b.如果二叉树不为空，则后序遍历，先遍历左子树，再遍历右子树，最后访问根节点。 public static void SelectTree(TreeNode root) {     if (root == null)
              return;
      SelectTree(root.left);
      SelectTree(root.right);
      System.out.print(root.data + " "); } (4). 层次遍历（从上往下，从左往右） a.使用队列实现遍历；首先对队列进行初始化，将根结点送入队列中； b.当队列不为空时，从队列中退出一个结点，若左孩子不为空，访问左孩子，则将左孩子入队列，再访问其右孩子；  public static void levelOrder(TreeNode node)
 {
     if (node == null)
          return;
       Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
       queue.add(node);
     while (!queue.isEmpty())
        {
            TreeNode temp = queue.poll();
            System.out.print(temp.data+" ");
            if (temp.left != null)
            queue.add(temp.left);
            if (temp.right != null)
            queue.add(temp.right);
       }
 } //二叉树结点个数 a.如果二叉树为空，则结点个数为0； b.如果二叉树不为空，则结点个数为左子树结点个数+右子树结点个数； 在这我使用的是递归的方法；   public static int getNodeNum(TreeNode node)
  {
      if(node==null)
       {
           return 0;
       }
           else
      {
          return getNodeNum(node.left)+getNodeNum(node.right)+1;
      }
  } //二叉树深度 a.如果二叉树为空，则二叉树深度为0； b.如果二叉树不为空，则求取二叉树左子树深度和右子树深度，那个字树的深度深，则为二叉树的深度；   public static int getDepth(TreeNode node)
  {
       int DepthL,DepthR;
      if(node==null)
            return 0;
      else
            DepthL=getDepth(node.left);
            DepthR=getDepth(node.right);
            return (DepthL<DepthR)? (DepthR+1):(DepthL+1);
  }