数据结构-二叉树

树以及常用的算法 树的概念 树(Tree)的基本概念
树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(nullempty)树。一棵非空的树包括一个根结点,还(很可能)有多个附加结点,所有结点构成一个多级分层结构。
二叉树的概念 每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。
二叉树的性质
1.若二叉树的层次从0开始,则在二叉树的第i层至多有2^i个结点(i>=0)
2.高度为k的二叉树最多有2^(k+1) - 1个结点(k>=-1)(空树的高度为-1)
3.对任何一棵二叉树,如果其叶子结点(度为0)数为m, 度为2的结点数为n, 则m = n + 1
二叉树的分类

二叉树又分为:完美二叉树,完全二叉树,完满二叉树
其中完满二叉树:除了叶子节点每个节点都有俩个孩子
完全二叉树:除了最后一层外,除了叶子节点每个节点都有俩个孩子
完美二叉树:除了叶子节点外,每一层每个节点都有俩个孩子

完美二叉树

完美二叉树

完全二叉树

完全二叉树

完满二叉树

完满二叉树

完满二叉树

完满二叉树 二叉树常见的搜索算法,借助leetcode展示 前序遍历 import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Given a binary tree, return the preorder traversal of its TreeNodes' values.
 */

public class Lc144 {

    /*
     * 前序遍历 :根左右 思路;将当前节点压入栈中,一直遍历左子树知道当前节点为空,向上弹出遍历一下右子树。
     */

    public static List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                list.add(curr.val);
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            curr = curr.right;
        }
        return list;
    }

    public static void main(String[] args) {
        Integer[] arr = new Integer[] { 12, null};
        TreeNode root = CreateNode.createTree(arr).get(0);
        List<Integer> list = preorderTraversal(root);
        list.forEach(n -> System.out.println(n));
    }

}
中顺遍历 import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Given a binary tree, return the inorder traversal of its nodes' values.
 */

public class Lc94 {

    /*
     * 中序遍历:左根右
     */

    public static List<Integer> orderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> preorder = new ArrayList<Integer>();
        TreeNode curr = root;

        while (!stack.isEmpty() || curr != null) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            preorder.add(curr.val);
            curr = curr.right;
        }
        return preorder;
    }

    public static void main(String[] args) {
        Integer[] arr = new Integer[] { 1null2nullnull3 };
        TreeNode root = CreateNode.createTree(arr).get(0);
        List<Integer> list = orderTraversal(root);
        list.forEach(n -> System.out.println(n));
    }

}
后序遍历 import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Lc145 {

    /*
     * 后续序遍历:左右根
     */

    public static List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();

        if (root == null) {
            return list;
        }

        TreeNode curr = root;
        stack.push(curr);
        while (!stack.isEmpty()) {
            curr = stack.pop();
            list.add(0, curr.val);
            if (curr.left != null) {
                stack.push(curr.left);
            }
            if (curr.right != null) {
                stack.push(curr.right);
            }
        }
        return list;
    }

    public static void main(String[] args) {
        Integer[] arr = new Integer[] { 1, null, 2 };
        TreeNode root = CreateNode.createTree(arr).get(0);
        List<Integer> list = postorderTraversal(root);
        list.forEach(n -> System.out.println(n));
    }

}
层序遍历 import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Lc102 {

    /**
     * 层序遍历
     * 
     * @param root
     * @return
     */

    public static List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> lists = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return lists;
        }

        TreeNode curr = root;
        queue.offer(curr);
        int size = queue.size();
        while (!queue.isEmpty()) {
            curr = queue.poll();
            list.add(curr.val);
            size--;
            if (curr.left != null) {
                queue.offer(curr.left);
            }
            if (curr.right != null) {
                queue.offer(curr.right);
            }
            if (size == 0) {
                lists.add(list);
                list = new ArrayList<>();
                size = queue.size();
            }

        }
        return lists;
    }

    public static void main(String[] args) {
        Integer[] arr = new Integer[] { 1234567 };
        TreeNode root = CreateNode.createTree(arr).get(0);
        List<List<Integer>> lists = levelOrder(root);
        lists.forEach(n -> {
            n.forEach(m -> {
                System.out.print(m + ",");
            });
            System.out.println();
        });

    }
}
BFS public class Lc100 {

    //bfs 递归
    public static boolean isSameTree(TreeNode p, TreeNode q{

        if (p == null || q == null) {
            return p == q ? true : false;
        } else {
            if (p.val != q.val) {
                return false;
            } else {
                return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
            }
        }

    }

    public static void main(String[] args{
        Integer[] arr = new Integer[] { 1223nullnull3 };
        TreeNode root = CreateNode.createTree(arr).get(0);
        System.out.println(isSameTree(root.left, root.right));

    }
}
介绍一个二叉树数组转换节点的工具类 使用方法,每一个main函数中都是
import java.util.ArrayList;
import java.util.List;

public class CreateNode {

    public static List<TreeNode> list = new ArrayList<TreeNode>(); // 用一个集合来存放每一个Node

    public static List<TreeNode> createTree(Integer[] array) {
        list.clear();
        for (int i = 0; i < array.length; i++) {
            TreeNode TreeNode = new TreeNode(array[i], nullnull); // 创建结点,每一个结点的左结点和右结点为null
            list.add(TreeNode); // list中存着每一个结点
        }
        // 构建二叉树
        if (list.size() > 0) {
            for (int i = 0; i < array.length / 2 - 1; i++) { // i表示的是根节点的索引,从0开始
                if (list.get(2 * i + 1) != null) {
                    // 左结点
                    list.get(i).left = list.get(2 * i + 1);
                }
                if (list.get(2 * i + 2) != null) {
                    // 右结点
                    list.get(i).right = list.get(2 * i + 2);
                }
            }
            // 判断最后一个根结点:因为最后一个根结点可能没有右结点,所以单独拿出来处理
            int lastIndex = array.length / 2 - 1;
            // 左结点
            list.get(lastIndex).left = list.get(lastIndex * 2 + 1);
            // 右结点,如果数组的长度为奇数才有右结点
            if (array.length % 2 == 1) {
                list.get(lastIndex).right = list.get(lastIndex * 2 + 2);
            }
        }
        return list;
    }

// 遍历,先序遍历
    public static void print(TreeNode TreeNode) {
        if (TreeNode != null) {
            System.out.print(TreeNode.val + " ");
            print(TreeNode.left);
            print(TreeNode.right);
        }
    }

    /**
     * @param args
     */

    public static void main(String[] args) {
        Integer[] array = { 122null3null3 };
        CreateNode.createTree(array);
        print(list.get(0));
    }
}

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wppjyz.html