二叉树的排序算法（先序遍历，中序遍历，后序遍历，宽度优先遍历）

二叉树的排序算法（先序遍历，中序遍历，后序遍历，宽度优先遍历）

引用

CSDN

1.

https://m.blog.csdn.net/zuoysharon/article/details/142313519

二叉树是计算机科学中一种基础而强大的数据结构，广泛应用于各种算法和问题的解决方案中。本文将深入探讨二叉树的基本概念、主要类型以及常见的排序算法，旨在帮助读者全面理解如何利用二叉树优化程序性能和解决实际问题。

二叉树

二叉树是一种特殊的树结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。它的特点是每个节点的子节点数量被限制在两个以内。二叉树的类型包括完全二叉树、满二叉树和二叉搜索树等，每种类型有不同的特性和应用场景。通过这种结构，可以高效地进行数据的存储和检索操作。

下面是一个简单的代码示例：

Class TreeNode{
    public TreeNode left;
    public TreeNode right;
    public int val;
    public TreeNode(int data){
        this.val=date;
    }
}

先序遍历

二叉树遍历方式的命名顺序都是根据根节点的位置命名的，所以先序遍历的意思是“根左右”，如图所示的例子中按照线序遍历的排序为：FDBACEGIHJ

当我们遍历二叉树时最后的目标是想让他按照我们规定的顺序弹出，所以我们想到用栈来完成这个问题

代码：

public void preOrder(TreeNode root){
   if (root != null){
       Stack<Node> stack=new Stack<>();//创建一个栈
       stack.push(root);
       while (!stack.isEmpty()){
                root=stack.pop();
                System.out.println(root.val+" "); //第一步：在栈中弹出一个元素
                if (root.right!=null){
                    stack.push(root.right);
                }if (root.left!=null){
                    stack.push(root.left);//如果左右都不为空先压右再压左
                }
            }
        }
        System.out.println();
}

因为最后的顺序是先左后右，而栈的特点是先进后出，所以在代码中要压入右子树再压入左子树

中序遍历

同理来说，中序遍历的顺序就是“左根右”，还是用栈来实现。最后的排序是“左”在第一位，所以我们要从根节点开始先完成对左子树的操作，将沿途节点全部压入栈中直到左子树为空弹出一个节点，这个节点就是我们最后排序过程中的第一个节点。在处理完左子树之后我们就该弹出根节点，所以我们使用栈不为空的条件来接着向下弹出根节点，最后处理右子树循环往复。

代码：

public void inOrder(TreeNode root){
    if(root != null){
        Stack<TreeNode> s1 = new Stack<>();
        while(root != null || !s1.empty()){
            if(root != null){
            s1.push(root); //将沿途节点压入栈中
            root = root.left;
            }else{
                root= s1.pop(); //弹出最左侧节点
                System.out.println(root.val+" ");
                root = root.right; //同理处理右子树
                }
        }
    }
}

后序遍历

后序遍历的顺序是左右根，这就需要最后处理最先进入栈的根节点，是遍历算法中最复杂的一个。由于栈的特性是先进后出，所以我们需要两个栈来完成排序。

代码：

public void postOrder(TreeNode root){
    if(root != null){
    Stack<TreeNode> s1 = new Stack<>();
    Stack<TreeNode> s2 = new Stack<>();
    
    s1.push(root); //压入头节点
    while(!s1.empty()){
        root = s1.pop();
        s2.push(root); //因为第一个进栈的节点要最后一个出所以将根要放到s2中
        //如果有左右子树就先压左再压右，因为右在左后面
        if(root.left != null){
            s1.push(root.left);
        }
        if(root.right != null){
            s1.push(root.right);
        }
    }
    }
    //遍历s2，得到的就是正确的顺序
    while(!s2.empty()){
    TreeNode node = s2.pop();
    System.out.println(node.val+"");
}
}

宽度优先遍历

顾名思义就是横向遍历二叉树，以文章开头的二叉树为例，宽度优先遍历的顺序为：ABCDEFG

原理很简单就是根节点然后遍历左节点和右节点

以下是一道经典例题，返回二叉树的最大宽度

代码：

 public int wide(Node head){
        if (head == null){
            return 0;
        }
        Queue queue=new LinkedList<>();
        queue.add(head);//把头节点压入队中
        HashMap<Node,Integer> levelMap=new HashMap<>();
        //创建一个map集合用来记录当前结点正处于第几层
        levelMap.put(head,1);//初始值在第一层
        int curlevel=1;//表示当前层次
        int curlevelNodes=0;//当前层节点数
        int max=Integer.MIN_VALUE;//用来记录最大宽度是多少
        while (!queue.isEmpty()){
            Node cur = (Node) queue.poll();
            int curlNodelevel=levelMap.get(cur);//得到当前结点得层数
            if (curlNodelevel==curlevel){//当前结点得层数如果与当前层数相同
                curlevelNodes++;
            }else {
                max=Math.max(max,curlevelNodes);//更新最大值
                curlevel++;
                curlevelNodes=1;//节点数回归
            }
            //然后左一个右一个进队
            if (cur.left!=null){
                levelMap.put(cur.left,curlNodelevel+1);
                queue.add(head.left);
            }if (cur.right!=null){
                levelMap.put(cur.right,curlNodelevel+1);
                queue.add(head.right);
            }
        }
        return max;
    }