二叉树的相关操作（二）

 

package dubletree;

import java.util.Scanner;
import java.util.Stack;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * 二叉树，创建类似数据结构试验74页的二叉树，以该例子为原型
 *
 * @author dell
 *
 */
public class DoubleTree {
 private TreeNode root;// 树根
 int count = 0;// 用来储存节点的个数，计数器
 private TreeNode parents = null;// 用来记录某节点的父节点或者定位所要查找的节点,初始时为空

 public TreeNode getParents() {
  return parents;
 }

 public void setParents(TreeNode parents) {
  this.parents = parents;
 }

 public int getCount() {
  return count;
 }

 public void setCount(int count) {
  this.count = count;
 }

 /**
  * 初始化根节点
  *
  * @param root
  */
 public DoubleTree(TreeNode root) {
  this.root = root;
 }

 public TreeNode getRoot() {
  return root;
 }

 public void setRoot(TreeNode root) {
  this.root = root;
 }

 /**
  * 递归创建二叉树，画图，仔细分析，分析递归的执行步骤
  *
  * @param root
  * @return返回root，也就是返回整个的一个二叉树
  */
 public TreeNode creat(TreeNode root) {
  Scanner in = new Scanner(System.in);
  System.out.println("请输入树的值：");

  double value = in.nextDouble();// 二叉树的值

  // 如果输入是0的话，就创建赋值为空
  if (value == 0) {
   root = null;
  } else {
   root = new TreeNode(value);
   root.setLeft(creat(root));
   root.setRight(creat(root));
  }

  return root;// 返回root
 }

 /**
  * 前序遍历树DLR
  *
  * @param root
  *            要遍历的树根，也就是当前要遍历的二叉树
  */
 public void visitBefore(TreeNode root) {
  if (root != null) {
   System.out.print(root.getValue() + "  ");
   visitBefore(root.getLeft());
   visitBefore(root.getRight());
  }

  // return root;
 }

 /**
  *后续遍历二叉树LRD
  *
  * @param root
  *            要遍历的树根，也就是当前要遍历的二叉树
  */
 public void visitAfter(TreeNode root) {
  if (root != null) {
   visitAfter(root.getLeft());
   visitAfter(root.getRight());
   System.out.print(root.getValue() + "  ");
  }
 }

 /**
  * LDR 中序遍历二叉树，要遍历的树根，也就是当前要遍历的二叉树
  *
  * @param root
  */
 public void visitCenter(TreeNode root) {
  if (root != null) {
   visitCenter(root.getLeft());
   System.out.print(root.getValue() + "  ");
   visitCenter(root.getRight());
  }
 }

 /**
  * 输出二叉树的叶子,也就是加一个判断条件： 当一个节点的左右儿子都为空时，说明该节点就是 个叶子， 输出即可
  *
  * @param root
  */
 public void visitLeaf(TreeNode root) {
  if (root != null) {
   if (root.getLeft() == null && root.getRight() == null)
    System.out.print(root.getValue() + "  ");
   visitLeaf(root.getLeft());
   visitLeaf(root.getRight());
  }
 }

 public void countLeaf(TreeNode root) {
  if (root != null) {
   if (root.getLeft() == null && root.getRight() == null)
    count++;

   countLeaf(root.getLeft());
   countLeaf(root.getRight());

  }
 }

 /**
  * 查找值为x的节点的双亲节点,用全局变量来存储该双亲节点
  *
  * @param root二叉树双亲节点
  * @param t当前节点
  * @param x值
  * @return beelean
  */
 public boolean findParents(TreeNode root, TreeNode t, double x) {
  if (t != null) {
   if (t.getValue() == x) {// 如果当前节点的值和x相等
    parents = root;// 指向父节点
    return true;
   } else if (!findParents(t, t.getLeft(), x)) {// 左节点没有找到
    if (!findParents(t, t.getRight(), x))// 从有节点开始找
     return false;
   }
   return true;
  }
  // 如果树为空，直接返回false
  return false;

 }

 /**
  * 输出二叉树的双亲，在输出叶子方法的问题上改动一个条 件 当节点的左儿子或者右儿子不为空时，输出该节点的值即可
  *
  * @param root
  */
 public void visitParents(TreeNode root) {
  if (root != null) {
   if (root.getLeft() != null || root.getRight() != null)
    System.out.print(root.getValue() + "  ");
   visitParents(root.getLeft());
   visitParents(root.getRight());
  }
 }

 /**
  * 根据某一个值查找某一个节点
  *
  * @param root
  *            TreeNode 二叉树
  * @param x
  *            要查找的那个树
  */
 public void find(TreeNode root, double x) {
  if (root != null) {
   if (root.getValue() == x) {
    parents = root;// 存储查找到的那个节点
   } else {
    find(root.getLeft(), x);
    find(root.getRight(), x);
   }
  }
 }

 public void count(TreeNode root) {
  if (root != null) {
   count(root.getLeft());
   count++;
   count(root.getRight());
  }
 }

 /**
  * 输出节点的个数，方法二
  *
  * @param args
  */

 public void count1(TreeNode root) {
  if (root != null) {
   count1(root.getLeft());
   count1(root.getRight());
   count++;
  }
 }

 // public boolean isAllTree(TreeNode )

 /**
  * 有关输出的操作
  *
  * @param message
  *            String 要输出的信息
  */
 public static void println(String message) {
  System.out.println(message + " ");
 }

 /**
  * 非递归中序访问二叉树，在出栈的过程中，要注意 标志指针要指向出战元素的有孩子 具体思路见课本132页
  *
  * @param root要遍历的二叉树
  */
 public void LDR(TreeNode root) {

  Stack stack = new Stack();
  while (!stack.isEmpty() || root != null) {
   if (root != null) {
    stack.push(root);
    root = root.getLeft();
   } else {
    TreeNode pop = (TreeNode) stack.pop();
    System.out.print(pop.getValue() + " ");
    root = pop.getRight();
   }
  }
 }

 /**
  * 层序遍历二叉树的非递归算法 画出图形可以加深理解
  *
  * @param root要遍历的树
  * @throws InterruptedException
  */
 public void cengXu(TreeNode root) throws InterruptedException {
  ArrayBlockingQueue<TreeNode> abq = new ArrayBlockingQueue<TreeNode>(
    count);// 队列
  if (root != null) {
   abq.put(root);// 第一个节点入队
   while (!abq.isEmpty()) {
    TreeNode tn = abq.take();// 拿出第一个节点
    System.out.print(tn.getValue() + " ");// 输出接点的值
    if (tn.getLeft() == null) {// 如果左儿子为空而有儿子不为空则把有儿子入队
     if (tn.getRight() != null) {
      abq.put(tn.getRight());
     }
    } else {// 如果左儿子不为空，而且右儿子不为空，则把左右儿子相继入队
     abq.put(tn.getLeft());
     if (tn.getRight() != null) {
      abq.put(tn.getRight());
     }

    }
   }
  }
 }

 /**
  * 思路先把根结点入栈，然后先把右结点入栈，在把左节点入栈，
  * 最后让根节点指针指向栈顶。画图理解之，其原理是始终让左儿子在栈的顶部
  * 然后取栈顶元素，并输出其值即可
  */

 public void DLR(TreeNode root) {
  Stack stack = new Stack();

  if (root != null) {
   stack.add(root);
   while (!stack.isEmpty()) {
    System.out.print(root.getValue() + "  ");
    if (root.getRight() != null)
     stack.add(root.getRight());
    if (root.getLeft() != null)
     stack.add(root.getLeft());
    root = (TreeNode) stack.pop();
   }
  }

 }
    /**;
     *
     * 求二叉树的深度
     * ，其思想就是，若为空，则其深度为0，否则，其深度等于左子树和右子树的深度的最大值加1：
     * @param args
     * @throws InterruptedException
     */
 public int depth(TreeNode root){
  int h1;
  int h2;
  if(root==null)
   return 0;
  h1 = depth(root.getLeft());
  h2 = depth(root.getRight());
  
     return h1>h2?h1+1:h2+1;
 }
 public static void main(String args[]) throws InterruptedException {
  DoubleTree dt = new DoubleTree(new TreeNode(1));

  TreeNode root = dt.creat(dt.getRoot());// 得到要创建好的树根，也就得到了创建好的树
  println("创建完毕");

  // println("********");
  //
  // println("前序遍历：");
  // dt.visitBefore(root);
  //
  // println("********");
  //
  // println("后续遍历：");
  // dt.visitAfter(root);
  //
  // println("********");
  //
  // println("中序遍历：");
  // dt.visitCenter(root);
  //
  // println("********");
  //
  // println("输出二叉树的叶子：");
  // dt.visitLeaf(root);
  //
  // println("********");
  //
  // println("输出二叉树的双亲：");
  // dt.visitParents(root);
  //
  // println("********");
  //
  // println("二叉树的节点数(方法一)：");
  // dt.count(root);
  // println(dt.getCount() + "");
  //
  // dt.setCount(0);// 清零
  //
  // println("二叉树的节点数(方法二：");
  // dt.count1(root);
  // println(dt.getCount() + "");
  //
  // println("********");
  //
  // println("查找某一个节点：");
  // dt.find(root, 3);
  // println(dt.getParents().getValue() + "");
  //  
  //  
  // println("********");
  // println("查找某一个父亲节点：");
  // boolean b = dt.findParents(null,root,3);
  // println(dt.getParents().getValue() + "");

  // dt.setCount(0);// 计数器清零
  //
  // println("********");
  // println("叶子的个数是：");

  // dt.countLeaf(root);
  // println(dt.getCount() + "");

  // println("********");
  // println("非递归LDR遍历 ：");
  //
  // dt.LDR(root);

  // println("********");
  // println("非递归层序遍历：");
  // dt.cengXu(root);

//  println("********");
//  println("非递归DLR遍历 ：");

//  dt.DLR(root);

  println("********");
  println("二叉树的深度 ：");

  println(dt.depth(root) + "");

 }
}