? ? ? ? }
? ? ? ? }? ?
? ? }
? ?
? ? //递归实现中序遍历 LNR
? ? public void inOrder(TreeNode node){
? ? ? ? if(node != null){
? ? ? ? ? ? inOrder(node.getLchild());
? ? ? ? ? ? System.out.print(node.getData() + " ");
? ? ? ? ? ? inOrder(node.getRchild());
? ? ? ? }
? ? }
? ?
? ? //非递归实现中序遍历 LNR
? ? public void nonRecInOrder(TreeNode node){
? ? ? ? Stack> nodeStack = new Stack>();
? ? ? ? TreeNode nodeTemp = node;? //nodeTemp作为遍历指针
? ? ? ? while(nodeTemp != null || !nodeStack.isEmpty()){? //当nodeTemp非空或栈非空时循环
? ? ? ? ? ? if(nodeTemp != null){? //根指针非空，遍历左子树
? ? ? ? ? ? ? ? nodeStack.push(nodeTemp);? //根指针进栈
? ? ? ? ? ? ? ? nodeTemp = nodeTemp.getLchild();? //每遇到非空二叉树先向左走
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? nodeTemp = nodeStack.pop();? //根指针退栈，访问根节点
? ? ? ? ? ? ? ? System.out.print(nodeTemp.getData() +" ");
? ? ? ? ? ? ? ? nodeTemp = nodeTemp.getRchild();? //再向右子树走
? ? ? ? ? ? }? ? ? ?
? ? ? ? }
? ? }
? ?
? ? //递归实现后序遍历 LNR
? ? public void postOrder(TreeNode node){
? ? ? ? if(node != null){
? ? ? ? ? ? postOrder(node.getLchild());
? ? ? ? ? ? postOrder(node.getRchild());
? ? ? ? ? ? System.out.print(node.getData() + " ");
? ? ? ? }
? ? }
? ?
? ? //非递归实现后序遍历 LNR
? ? public void nonRecPostOrder(TreeNode node){
? ? ? ? Stack> nodeStack = new Stack>();
? ? ? ? TreeNode nodeTemp = node; //nodeTemp作为遍历指针
? ? ? ? TreeNode preNode = null;? //表示最近一次访问的节点
? ? ? ? while(nodeTemp != null || !nodeStack.isEmpty()){? //当nodeTemp非空或栈非空时循环
? ? ? ? ? ? while(nodeTemp != null){? //一直向左走，遍历左子树
? ? ? ? ? ? ? ? nodeStack.push(nodeTemp);
? ? ? ? ? ? ? ? nodeTemp = nodeTemp.getLchild();
? ? ? ? ? ? }
? ? ? ? ? ? nodeTemp = nodeStack.peek();
? ? ? ? ? ? if(nodeTemp.getRchild()==null || nodeTemp.getRchild() == preNode){? //右子树为空或右子树已被访问时，该节点出栈
? ? ? ? ? ? ? ? nodeTemp = nodeStack.pop();
? ? ? ? ? ? ? ? System.out.print(nodeTemp.getData()+" ");
? ? ? ? ? ? ? ? preNode = nodeTemp;? //将该节点赋值给最近一个访问节点? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? nodeTemp = null;? //此处很重要，将刚出栈节点设置为空，对应于while循环的条件之一，否则陷入死循环
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? nodeTemp = nodeTemp.getRchild(); //遍历右子树
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ?
? ?
? ? //层次遍历
? ? public void levelOrder(TreeNode root){
? ? ? ? Queue> nodeQueue = new LinkedList>();
? ? ? ? TreeNode node = null;
? ? ? ? nodeQueue.add(root);? //将根节点入队? ?
? ? ? ? while(!nodeQueue.isEmpty()){? //队列不空循环
? ? ? ? ? ? node = nodeQueue.peek();
? ? ? ? ? ? System.out.print(node.getData()+" ");
? ? ? ? ? ? nodeQueue.poll();? ? //队头元素出队
? ? ? ? ? ? if(node.getLchild() != null){? ? //左子树不空，则左子树入队列
? ? ? ? ? ? ? ? nodeQueue.add(node.getLchild());
? ? ? ? ? ? }
? ? ? ? ? ? if(node.getRchild() != null){? ? //右子树不空，则右子树入队列
? ? ? ? ? ? ? ? nodeQueue.add(node.getRchild());
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ?
? ? public static void main(String args[]){
? ? ? ? //将一个数组转化为一颗完全二叉树
? ? ? ? Object[] array = {1,2,3,4,5,6,7,8};
? ? ? ? BinaryTree bt = new BinaryTree();
? ? ? ? TreeNode root = bt.buildTree(array);
? ? ? ? System.out.print("树的高度：");?
? ? ? ? System.out.println(bt.height(root));
? ? ? ? System.out.print("节点的个数：");?
? ? ? ? System.out.println(bt.size(root));
? ? ? ? System.out.println("先序遍历：");?
? ? ? ? bt.preOrder(root);
? ? ? ? System.out.println("\n"+"非递归先序遍历：");
? ? ? ? bt.nonRecPreOrder(root);
? ? ? ? System.out.println();
? ? ? ?
?
? ? ? ? System.out.println("中序遍历：");?
? ? ? ? bt.inOrder(root);?
? ? ? ? System.out.println("\n"+"非递归中序遍历：");
? ? ? ? bt.nonRecInOrder(root);
? ? ? ? System.out.println();
?
? ? ? ? System.out.println("后序遍历：");?
? ? ? ? bt.postOrder(root);?
? ? ? ? System.out.println("\n"+"非递归后序遍历：");
? ? ? ? bt.nonRecPostOrder(root);
? ? ? ? System.out.println();
? ? ? ?
? ? ? ? System.out.println("层次遍历：");?
? ? ? ? bt.levelOrder(root);
? ? ? ?
? ? ? ? //手工构建一颗二叉树
? ? ? ? TreeNode nodeA = n |