数据结构--树及其常见操作(Java)

树的定义树的分类二叉树

满二叉树完全二叉树二叉查找(搜索)(排序)树

平衡二叉树 树的常见操作

遍历

前序遍历中序遍历后序遍历深度优先遍历dfs广度优先遍历bfs Leetcode226.翻转二叉树

树是一种非线性的数据结构，是由n（n >=0）个结点组成的有限集合。
有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱。

度：
对于一个结点，拥有的子树数（结点有多少分支）称为结点的度（Degree）
层次：
从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，依次类推

二叉树：每个结点最多 2 棵子树，没有其它限制了。

除叶节点外的所有节点都有两个子节点

若设二叉树的高度为h，则共有h层。除第 h 层外，其它各层 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。

首先它是二叉树，并且左子树上所有结点的值小于它根结点的值，右子树上所有结点的值大于它根结点的值。

更加准确的应该叫 “平衡二叉树”，它是 “平衡二叉搜索树” 的简称。首先它是 “二叉搜索树”，其次，它是平衡的，即是它的每一个结点的左子树的高度和右子树的高度差至多为 1。

以一种特定顺序访问数的每一个节点，适用与所有的树。

先访问根节点，再访问左节点，最后访问根节点。

Leetcode 144.二叉树的前序遍历

//递归实现
class Solution {
    List list = new ArrayList();
    public List preorderTraversal(TreeNode root) {
        if(root==null)  return list;
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }
}

先访问左子节点，在访问根节点，最后访问右子节点。

Leetcode 94.二叉树的中序遍历

//递归方式完成中序遍历
class Solution {
    List list = new ArrayList();  //定义一个list用来存放节点的值
    public List inorderTraversal(TreeNode root) {
        if(root ==null){ //如果根节点为空，直接返回list(也为空)
        return list; 
        }
        inorderTraversal(root.left);
        //中序遍历放递归中间
        list.add(root.val); //将中序遍历得到的结果加入 list
        inorderTraversal(root.right);
        return list; 
}
}

先访问左子节点，在访问根，最后访问右子节点。

Leetcode 145.二叉树的后序遍历

//递归方式完成后序遍历
class Solution { 
    List list = new ArrayList();
    public List postorderTraversal(TreeNode root) {
        if(root==null) return list;

        postorderTraversal(root.left);
        postorderTraversal(root.right);
        list.add(root.val);
        return list;
    }
}

从一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。

算法实现：使用栈后进先出的特性，每弹出一个元素，就把该元素的右子树先压入栈，左子树后压入栈。

public static void dfsWithStack(Node root) { 
        if (root == null)    return; 
        Stack stack = new Stack<>(); 
        // 先把根节点压栈 
        stack.push(root); 
        while (!stack.isEmpty()) { //栈不为空时
            Node treeNode = stack.pop(); 
            // 先压右节点 
            if (treeNode.right != null) { 
                stack.push(treeNode.right); 
            }      
            // 再压左节点 
            if (treeNode.left != null) { 
                stack.push(treeNode.left); 
            } 
        } 
    } 

广度优先遍历，指的是从图的一个未遍历的节点出发，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点。
算法实现：利用队列先进先出的特性，每出队一个元素，就把该元素的左子节点先入队，右子节点后入队。

 private static void bfs(Node root) { 
        if (root == null)   return; 
        Queue queue = new linkedList<>(); 
        queue.offer(root); //根节点入队
        while (!queue.isEmpty()) { 
            Node node = queue.poll(); 
            if (node.left != null) { 
                queue.offer(node.left); 
            } 
            if (node.right != null) { 
                queue.offer(node.right); 
            } 
        } 
    } 

递归实现：

class Solution { //递归法反转二叉树 
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;

        TreeNode left = invertTree(root.left); //递归
        TreeNode right = invertTree(root.right);
      
        root.left = right; //反转
        root.right = left;
        return root;

    }
}

迭代法实现：

class Solution { //迭代法反转二叉树(层序遍历) 
    public TreeNode invertTree(TreeNode root) {
        if(root==null) return root;
        Queue queue = new linkedList();
        queue.offer(root); //根入队
        while(!queue.isEmpty()){
            TreeNode node = queue.poll(); //创建节点拿到队头的值
            //节点交换位置
            TreeNode left = node.left;
            node.left = node.right;
            node.right = left;
            if(node.left!=null){ //左节点入队
                queue.offer(node.left);
            }
            if(node.right!=null){//右节点入队
                queue.offer(node.right);
            }
        }
        return root;
    }
}