数据结构：二叉树（1）

假设父结点下标是i，则左孩子下标为 2*i+1，右孩子下标是2*i+2

反推，如果孩子下标为i，则父结点下标是(i-1) / 2

题目

偶数个结点的完全二叉树，度为1的结点一定只有1个

而奇数个结点的，度为1的结点为0个

所以可以列个等式

2n = n0 + 1 + n2 = n0 + 1 + n0 - 1

所以 n0 = n      选A

二叉树的存储

分为顺序存储和链式存储

顺序存储：堆（可以看看我后面的博客），这篇博客讲链式存储

链式存储

初始化二叉树

目前的思路：

先创建结点，以穷举的方式造一棵二叉树，根据下面这张图来创建

public class BinaryTree {
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
 
        public TreeNode(char val) {
            this.val = val;
        }
    }
 
    public TreeNode root;
    //创建一棵二叉树，创建成功后返回根结点
    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
 
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
 
        return A;
    }
}

测试一下

煤油问题😊

二叉树的遍历

遍历指的是沿着某条路线遍历

前序遍历：根👉左子树👉右子树

遇到根就打印

 中序遍历：左子树👉根👉右子树

后序遍历：左子树👉右子树👉根

留一道题，请写出下图的前序，中序和后序遍历（答案在文章末尾）

选择题

首先把这个树画出来

画出来后就很简单了，答案就是A

怎么画出这棵树？

 根结点就是E

注意：后序遍历是可以确定树的根的，就是最后一个字母a

那放到中序遍历中，a的左边b就是左子树，a的右边dce构成右子树

后序遍历里面，a后面的c是一个子树根，根据中序，那d和e就很自然排在c的左和右了

画出来就是这样，前序遍历就是abcde

后序遍历确定根是F，那根据中序遍历F前面的ABCDE构成左子树，没有右子树

F后面每一个元素都是前一个元素的根结点，画出来就是这样

层次输出FEDCBA

问题：如果给你前序遍历和后序遍历，可以画出一棵二叉树吗？

不可以。因为前序和后序确定的都是根

代码代码！

    // 前序遍历
    void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.println(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

有点难理解？其实这段代码的分析过程跟我们在造树的过程差不多 

（图太大了只能截一部分了...）

剩下的俩就很简单了

    // 中序遍历
    void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.println(root.val + " ");
        inOrder(root.right);
    }
    // 后序遍历
    void postOrder(TreeNode root){
        if(root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.val + " ");
    }

前序遍历的存储问题 

144. 二叉树的前序遍历 - 力扣（LeetCode）

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

遍历思路：遍历到是我就存储进去

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;
    }
}

套娃存列表思想

    public List preorderTraversal(TreeNode root) {
        List list = new ArrayList<>();
        if(root == null){
            return list;
        }
        list.add(root.val);
        List leftTree = preorderTraversal(root.left);
        list.addAll(leftTree);
 
        List rightTree = preorderTraversal(root.right);
        list.addAll(rightTree);
        return list;
    }

画个图解释一下（只画了左子树） 

每次返回就把拼接好的列表归到父结点的列表中

图片遍历答案

前序：ABDEHCFG

中序：DBEHAFCG

后序：DHEBFGCA