二叉树的先、中、后序遍历的递归和非递归实现及广度优先遍历、深度优先遍历及其高度

Love The Way You Lie 2022-05-28 04:19 197阅读 0赞

// 构造二叉树
                  1
              /      \
             2        3
            /      /     \
           4      5      7
             \         /
              6       8

一、二叉树的前、中、后序遍历(递归与非递归实现)

二、二叉树的广度、深度优先遍历

三、求二叉树的高度

import java.util.*;
    //二叉树的深度和广度遍历
    public class TreeSearch{
          
        //二叉树节点的定义
        public static class BinaryTreeNode{
    
    	   int value;
    	   BinaryTreeNode left;
    	   BinaryTreeNode right;
    	    //构造函数
        public BinaryTreeNode(int v)
        {
           this.value=v;
        }
        //第二个构造函数
        public BinaryTreeNode(int v,BinaryTreeNode left,BinaryTreeNode right)
        {
            super();
            this.value=v;
            this.left=left;
            this.right=left;
        }
      }
        //访问二叉树的节点
        public static void visit(BinaryTreeNode node)
        {
            System.out.print(node.value+" ");
        }
    //******************************************************** 
        //递归实现二叉树的先，中，后序遍历
        public static void preOrder(BinaryTreeNode node)
        {
        	if(node!=null)
        	{
        		 visit(node);
        		 preOrder(node.left);
        		 preOrder(node.right);
        	}
    
        }
        public static void inOrder(BinaryTreeNode node)
        {
        	if(node!=null)
        	{
        		 
        		 inOrder(node.left);
        		 visit(node);
        		 inOrder(node.right);
        	}
    
        }
        public static void postOrder(BinaryTreeNode node)
        {
        	if(node!=null)
        	{
        		 postOrder(node.left);
        		 postOrder(node.right);
        		 visit(node);
        	}
    
        }
       //*************非递归实现二叉树的先，中，后序遍历********************
      
         /** 非递归实现二叉树的先序遍历 */
        public static void iterativePreorder(BinaryTreeNode node) {
            Stack<BinaryTreeNode> stack = new Stack<>();
            if (node != null) {
                stack.push(node);
                while (!stack.empty()) {
                    node = stack.pop();
                    // 先访问节点
                    visit(node);
                    // 把右子结点压入栈
                    if (node.right != null) {
                        stack.push(node.right);
                    }
                    // 把左子结点压入栈
                    if (node.left != null) {
                        stack.push(node.left);
                    }
                }
            }
        }
    
        /** 非递归实现二叉树的中序遍历 */
        public static void iterativeInOrder(BinaryTreeNode root) {
            Stack<BinaryTreeNode> stack = new Stack<>();
            BinaryTreeNode node = root;
            while (node != null || stack.size() > 0) {
                // 把当前节点的所有左侧子结点压入栈
                while (node != null) {
                    stack.push(node);
                    node = node.left;
                }
                // 访问节点，处理该节点的右子树
                if (stack.size() > 0) {
                    node = stack.pop();
                    visit(node);
                    node = node.right;
                }
            }
        }
    
        /** 非递归使用单栈实现二叉树后序遍历 */
        public static void iterativePostOrder(BinaryTreeNode root) {
            Stack<BinaryTreeNode> stack = new Stack<>();
            BinaryTreeNode node = root;
            // 访问根节点时判断其右子树是够被访问过
            BinaryTreeNode preNode = null;
            while (node != null || stack.size() > 0) {
                // 把当前节点的左侧节点全部入栈
                while (node != null) {
                    stack.push(node);
                    node = node.left;
                }
                if (stack.size() > 0) {
                    BinaryTreeNode temp = stack.peek().right;
                    // 一个根节点被访问的前提是：无右子树或右子树已被访问过
                    if (temp == null || temp == preNode) {
                        node = stack.pop();
                        visit(node);
                        preNode = node;// 记录刚被访问过的节点
                        node = null;
                    } else {
                        // 处理右子树
                        node = temp;
                    }
                }
            }
        }
    
        /** 非递归使用双栈实现二叉树后序遍历 */
        public static void iterativePostOrderByTwoStacks(BinaryTreeNode root) {
            Stack<BinaryTreeNode> stack = new Stack<>();
            Stack<BinaryTreeNode> temp = new Stack<>();
            BinaryTreeNode node = root;
            while (node != null || stack.size() > 0) {
                // 把当前节点和其右侧子结点推入栈
                while (node != null) {
                    stack.push(node);
                    temp.push(node);
                    node = node.right;
                }
                // 处理栈顶节点的左子树
                if (stack.size() > 0) {
                    node = stack.pop();
                    node = node.left;
                }
            }
            while (temp.size() > 0) {
                node = temp.pop();
                visit(node);
            }
        }
    
    //**************************************************************
        //二叉树的广度优先遍历
        public static void levelSearchBinaryTree(BinaryTreeNode root)
        {
        	Queue<BinaryTreeNode>queue=new LinkedList<>(); //存储每一层的节点
        	if(root!=null)
        	{
        		queue.add(root);
        		while(!queue.isEmpty())
        	   {
    
        	   	  BinaryTreeNode node=queue.poll();
        	   	  visit(node);
        	   	  if(node.left!=null)
        	   	  {
        	   	  	 queue.add(node.left);
        	   	  }
        	   	  if(node.right!=null)
        	   	  {
        	   	  	 queue.add(node.right);
        	   	  }
        	   }
        	}	
        }
       //二叉树的深度优先遍历
        public static void deepSearchBinaryTree(BinaryTreeNode root)
        { 
              Stack <BinaryTreeNode>stack=new Stack<>();
               if(root!=null)
               {
               	 stack.push(root);
               	 while(!stack.isEmpty())
               	 {
               	 	 root=stack.pop();
               	 	 visit(root);
               	 	 if(root.right!=null) //把右边的节点压入栈底
               	 	 {
               	 	 	 stack.push(root.right);
               	 	 }
               	 	 if(root.left!=null)
               	 	 {
               	 	 	stack.push(root.left);
               	 	 }
               	 }
    
               }
    
        }
        //求二叉树的高度
        public static int BinaryTreeHeight(BinaryTreeNode root)
        {
        	if(root==null)
        	{
        		 return 0;
        	}
        	int height=0;
        	if(root!=null)
        	{
        		int left=BinaryTreeHeight(root.left);
        		int right=BinaryTreeHeight(root.right);
        		height=left>right?left+1:right+1;
        	}
        	return height;
    
        }
    	public static void main(String[]args)
    	 {
            System.out.println("Hello World!");
              // 构造二叉树
            // 1
            // / \
            // 2 3
            // / / \
            // 4 5 7
            // \  /
            // 6 8
            BinaryTreeNode root = new BinaryTreeNode(1);
            BinaryTreeNode node2 = new BinaryTreeNode(2);
            BinaryTreeNode node3 = new BinaryTreeNode(3);
            BinaryTreeNode node4 = new BinaryTreeNode(4);
            BinaryTreeNode node5 = new BinaryTreeNode(5);
            BinaryTreeNode node6 = new BinaryTreeNode(6);
            BinaryTreeNode node7 = new BinaryTreeNode(7);
            BinaryTreeNode node8 = new BinaryTreeNode(8);
    
            root.left = node2;
            root.right = node3;
            node2.left = node4;
            node3.left = node5;
            node3.right = node7;
            node4.right = node6;
            node7.left = node8;
            System.out.println("二叉树先序递归遍历");
            preOrder(root);
            System.out.println();
            System.out.println("二叉树先序遍历非递归");
            iterativePreorder(root);
             System.out.println();
            System.out.println("二叉树中序递归遍历");
            inOrder(root);
             System.out.println();
            System.out.println("二叉树中序遍历非递归");
            iterativeInOrder(root);
             System.out.println();
            System.out.println("二叉树后序递归遍历");
            postOrder(root);
             System.out.println();
            System.out.println("二叉树单栈非递归后序遍历");
            iterativePostOrder(root);
             System.out.println();
            System.out.println("二叉树双栈非递归后序遍历");
            iterativePostOrderByTwoStacks(root);
             System.out.println();
            System.out.println("二叉树广度(层次)遍历");
            levelSearchBinaryTree(root);
             System.out.println();
            System.out.println("二叉树深度遍历");
            deepSearchBinaryTree(root);
             System.out.println();
            System.out.println("二叉树的高度");
            System.out.println(BinaryTreeHeight(root));
    	 }
    }