高级数据结构—二叉树

树是一种一对多的数据结构,之前的数组,栈这些都是一对一的数据结构。

树是n个结点的有限集。n=0称空树。在随便一棵非空树中:有且仅有一个根(root)结点;n>1时,其余结点可分为m个互不相交的的有限集,其中每个聚集又是一棵树,称为根的子树。

高级数据结构---二叉树

 

前面三个都是树,最后一个不是树,由于最后一个的数据相交了。

树结构中的术语:

以下图为例

高级数据结构---二叉树

 

结点:树上面的元素

父子关系:结点之间相连的边

子树:当结点大于1时,其余的结点分为的互不相交的聚集称为子树.

度:一个结点拥有的子树数目称为结点的度(Aroot结点度是2B的度是2D的度是1)

叶子:度为0的结点(H,E,F,G)

孩子:结点的子树的根称为孩子结点

双亲:和孩子结点对应,一个孩子只有一个双亲(A是B的双亲)

兄弟:统一个双亲结点(B,C

森林:由个互不相交的树组成深林

结点高度:结点到叶子结点的最长路径(A的高度3B的高度2H的高度0

结点深度:根结点到该结点的边个数(B结点深度1H结点深度3

结点的层数:结点的深度加1

树的高度:根结点的高度

树的深度:树的高度+1

树的示意方式:

双亲示意法:由孩子来记着双亲的位置

public class TreeNode<T> {
    private T data;
    private TreeNode<T> parent;
    
}

 

孩子示意法:由双亲来记着所有孩子的位置

public class TreeNode<T> {
    private T data;
    private TreeNode<T> leftChild;
    private TreeNode<T> rightChild;
}

 

二叉树:

二叉树是由一个根结点和两棵互不相交的,划分称为根结点的左子树和右子树的二叉树组成。二叉树的每个最多有两棵子树。也就说二叉树每个结点的度是不会跨越2的。

好比上面的ABCDEFGH就是一棵二叉树。二叉树异常适合用于每个阶段都存在两种效果的情形的建模。好比开关,01,真假,上下,对错,正反,选不选(前面动态计划剖析的谁人图)

特殊的二叉树:

斜树:所有结点都只有左子树的叫做左斜树,所有结点只有右子树的叫做右斜树

高级数据结构---二叉树      高级数据结构---二叉树

 满二叉树:所有结点都存在左右子树,而且所有的叶子都在统一层

高级数据结构---二叉树

 

完全二叉树:每一层的叶子结点都是相邻的没有距离,满二叉树也是一种特殊的完全二叉树

 高级数据结构---二叉树             高级数据结构---二叉树

路径跟踪 PathMeasure的简朴使用

 

后面的就不是完全二叉树,由于EG不相邻了。完全二叉树可以基于数组存储。前面也有说到数组可以基于下标查询,而且它在内存中是延续,CPU有会预读相邻的区域的。

完全二叉树怎么用数组存储呢?

双亲索引为i,那么它的左孩子就是2i,右孩子就是2i+1

好比上面这个完全二叉树转换成数组示意:

 高级数据结构---二叉树

 

FC的左孩子:C3F6,刚好是2n

非完全二叉树也用数组存储的话,会导致许多内存虚耗,分配了却没有使用。

 

二叉树的遍历

遍历如下这个二叉树:

高级数据结构---二叉树

 

先来用代码来构建这棵二叉树:

 

    /**
     * 组织二叉树
     * @param dataList
     * @param <T>
     * @return
     */
    public static <T> TreeNode<T> createBinaryTree(LinkedList<T> dataList) {
        TreeNode<T> node = null;
        if (dataList == null || dataList.isEmpty()) {
            return null;
        }
        T data = dataList.removeFirst();
        if (data != null) {
            node = new TreeNode(data);
            node.setLeftChild((createBinaryTree(dataList)));
            node.setRightChild((createBinaryTree(dataList)));
        }
        return node;
    }

 

挪用方式:

        LinkedList<String> inputList = new LinkedList<>(
                Arrays.asList(new String[]{"A","B","D","H",null,null,null,"E",null,null,"C","F",null,null,"G"}));
        TreeNode<String> treeNode = createBinaryTree(inputList);

挪用内里传的部门null值,是由于有些结点没有孩子结点,好比H,凭据写的组织树方式(createBinaryTree)的逻辑传入合适的null值。

 

遍历有要害点:不管哪种遍历,根据其顺序遇根输出

前序遍历:

根据根左右的顺序,遇根输出,再去找左

上面这棵树的效果应该是ABDHECFG

由于遍历的时刻 对于每个节点的操作都是一样的,以是我们首先想到的就是使用递归

    /**
     * 前序遍历 根 左子树 右子树
     * @param node
     */
    public static<T> void preOrderTraversal(TreeNode<T> node) {
        if(node == null){
            return;
        }
        //遇根先输出,再去找左右
        System.out.print(node.getData());
        preOrderTraversal(node.getLeftChild());
        preOrderTraversal(node.getRightChild());
    }

 

也可以行使栈的特征来实现递归回溯的功效

    /**
     * 行使栈前序遍历二叉树
     * @param root
     */
    public static <T> void preOrderTraversalByStack(TreeNode<T> root) {
        Stack<TreeNode<T>> stack = new Stack<>();
        TreeNode<T> node = root;
        while(node != null || !stack.isEmpty()) {
            //节点不为空,遍历节点,并入栈用于回溯
            while(node != null) {
                System.out.print(node.getData());
                stack.push(node);
                node = node.getLeftChild();
            }
            //没有左节点,弹出该栈顶节点(回溯),接见右节点
            if(!stack.isEmpty()) {
                node = stack.pop();
                node = node.getRightChild();
            }
        }
    }

 

中序遍历:左

HDBEAFCG

    /**
     * 二叉树中序遍历 左子树 根 右子树
     * @param node   二叉树节点
     */
    public static<T> void inOrderTraversal(TreeNode<T> node){
        if(node == null){
            return;
        }
        //先找左再输出根,再去找右
        inOrderTraversal(node.getLeftChild());
        System.out.print(node.getData());
        inOrderTraversal(node.getRightChild());
    }

 

后序遍历:左

HDEBFGCA

    /**
     * 二叉树后序遍历  左子树 右子树 根
     * @param node   二叉树节点
     */
    public static<T> void postOrderTraversal(TreeNode<T> node){
        if(node == null){
            return;
        }
        //先找左右,最后输出根
        postOrderTraversal(node.getLeftChild());
        postOrderTraversal(node.getRightChild());
        System.out.print(node.getData());
    }

 

条理遍历:按层来遍历

ABCDEFGH

条理遍历的时刻,行使行列的特征,将所有的孩子依次入队举行操作。

 

    public static <T> void levelOrder(TreeNode<T> root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);  //入队
        while (!queue.isEmpty()) {
            TreeNode<T> node = queue.poll(); //取出
            if (node != null) {
                System.out.print(node.getData());
                queue.offer(node.getLeftChild());   //左孩子入队
                queue.offer(node.getRightChild());  //右孩子入队
            }
        }
    }

 

原创文章,作者:28qn新闻网,如若转载,请注明出处:https://www.28qn.com/archives/5221.html