二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。
, i>=1；
个结点(h>=1)，最少有h个结点；
（注：[ ]表示向下取整）@Setter @Getter @ToString public class BinaryTree { private Object data;//当前节点数据 private BinaryTree lChild;//当前节点左孩子 private BinaryTree rChild;//当前节点右孩子 private BinaryTree root;//根节点 //构造函数 public BinaryTree (Object data){ this.data = data; } //创建二叉树 public void creatBinaryTree (Object data[]){ //将数据转换为节点存储 List<BinaryTree> list = new ArrayList<BinaryTree>(); for (Object tmpdata:data){ list.add(new BinaryTree(tmpdata)); } //第1个节点作为根节点 root = list.get(0); //构建二叉树 for (int i=0;i<list.size()/2;i++){ //父节点位置为i，左子节点位置为i*2+1 if (i*2+1<list.size()){ list.get(i).setLChild(list.get(i*2+1)); } //父节点位置为i，左子节点位置为i*2+2 if (i*2+2<list.size()){ list.get(i).setRChild(list.get(i*2+2)); } } } }
//前序遍历(递归) public void preOrder_Recursive(BinaryTree root){ if (root!=null){ System.out.print(" "+root.getData()); preOrder_Recursive(root.getLChild()); preOrder_Recursive(root.getRChild()); } }
//中序遍历(递归) public void inOrder_Recursive(BinaryTree root){ if (root!=null){ inOrder_Recursive(root.getLChild()); System.out.print(" "+root.getData()); inOrder_Recursive(root.getRChild()); } }
//后序遍历(递归) public void postOrder_Recursive(BinaryTree root){ if (root!=null){ postOrder_Recursive(root.getLChild()); postOrder_Recursive(root.getRChild()); System.out.print(" "+root.getData()); } }
//层次遍历 public void levelOrder(BinaryTree root){ //当前节点 BinaryTree current = null; //创建队列用于临时存放节点 LinkedList<BinaryTree> queue = new LinkedList<BinaryTree>(); if (root!=null){ //根节点入队 queue.offer(root); } while(!queue.isEmpty()){ //出队队头节点 current = queue.poll(); System.out.print(" "+current.getData()); //若有左子节点，则将其入队 if (current.getLChild()!=null){ queue.offer(current.getLChild()); } //若有右子节点，则将其入队 if (current.getRChild()!=null){ queue.offer(current.getRChild()); } } }
//左视图 public void leftView(BinaryTree root){ //当前节点 BinaryTree current = null; //创建队列用于临时存放节点 LinkedList<BinaryTree> queue = new LinkedList<BinaryTree>(); if (root!=null){ //根节点入队 queue.offer(root); System.out.print(" "+root.getData()); } while(!queue.isEmpty()){ int size = queue.size(); while(size>0) { //出队队头节点 current = queue.poll(); //若有左子节点，则将其入队 if (current.getLChild() != null) { queue.offer(current.getLChild()); } //若有右子节点，则将其入队 if (current.getRChild() != null) { queue.offer(current.getRChild()); } size--; //size==0时，队列中第1个节点为下一层右边第1个节点 if (size==0 && queue.size()>0){ System.out.print(" "+queue.getFirst().getData()); } } } }
//右视图 public void rightView(BinaryTree root){ //当前节点 BinaryTree current = null; //创建队列用于临时存放节点 LinkedList<BinaryTree> queue = new LinkedList<BinaryTree>(); if (root!=null){ //根节点入队 queue.offer(root); System.out.print(" "+root.getData()); } while(!queue.isEmpty()){ int size = queue.size(); while(size>0) { //出队队头节点 current = queue.poll(); //若有右子节点，则将其入队 if (current.getRChild() != null) { queue.offer(current.getRChild()); } //若有左子节点，则将其入队 if (current.getLChild() != null) { queue.offer(current.getLChild()); } size--; //size==0时，队列中第1个节点为下一层左边第1个节点 if (size==0 && queue.size()>0){ System.out.print(" "+queue.getFirst().getData()); } } } }
原文：https://www.cnblogs.com/6970-9192/p/11495725.html