数据结构：二叉树（1）

目录

树的概念

树的表示形式

二叉树

二叉树的性质

题目

二叉树的存储

链式存储

初始化二叉树

二叉树的遍历

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

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

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

选择题

代码代码！

前序遍历的存储问题 

---

树的概念

树是一种非线性的数据结构，是由n（n>=0）个有限结点组成一个具有层次关系的集合

它像是一颗倒挂的树，即根朝上，叶（结点）朝下

注意：

除了根结点外，每个节点有且只有一个父结点 

一棵n个结点的树由n-1条边

---

结点的度：一个结点含有子树的个数，上面A的度就是6

树的度：所有结点度的最大值（max(node degree)），上面树的度就是6

叶结点/终端结点：度为0的结点，上面B,C,H,I,K,L,M,N,P,Q就是叶结点

父结点：一个结点如果有条线连着上面一个结点，那上面这个结点就是这个结点的父结点

比如：A是B的父结点

子节点：结点含有的子树的根结点，B是A的子结点

根结点：没有父结点的结点

结点层次：根是第一层，其子结点是第2层。。。。

树的高度：树结点最大层次，树高度为4

分支结点：度不为0的结点，比如：D,E,J....

兄弟结点：有相同父结点的结点

堂兄弟结点：双亲在同一层的结点互为堂兄弟，如H,I就是堂兄弟结点

---

树的表示形式

孩子兄弟表达法

---

二叉树

一颗二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上左子树和右子树的二叉树组成

特点：

二叉树不存在度大于2的结点，所以他的每颗子树都是二叉树

满二叉树：每层结点树都达到最大值。如果一棵二叉树的层数为k，且结点总数是2^k-1，那它就是一棵满二叉树

完全二叉树：对于深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。

满二叉树是一种特殊的完全二叉树

二叉树的性质

1.若规定的根结点层数是1，那一棵非空二叉树的第i层上最多有2^(i-1)个结点

2.规定只有根结点的二叉树深度为1，则深度为k的二叉树最大结点数是2^k -1

3.对于任意一棵二叉树，如果叶结点个数为n0，度为2的非叶结点个数为n2，则有n0 = n2+1

换句话说，叶结点(度为0)的个数总是要比度为2的结点个数多1个

如上图，叶结点的个数有6个，度为2的结点个数为5个 5+1 = 6

推导公式

等式1：假设一棵树有n个结点，度为0的有n0个，度为1的有n1个，度为2的有n2个，那么

n = n0 + n1 + n2

等式2：一棵n个结点的树有n-1条边

一般的，度为0的结点不会产生边，度为1的结点(n1个)产生n1 * 1条边，度为2的结点(n2个)产生

n2 * 2 条边

那么 n-1 = n1+2*n2

把等式1和2联立，n0+n1+n2-1 = n1 + 2 * n2  -- >   n0 = n2 + 1

4.具有n个结点的完全二叉树的深度k为上取整

5. 对于具有 n 个结点的完全二叉树 ，如果按照 从上至下从左至右的顺序对所有节点从 0 开始编号 ，则对于 序号为 i 的结点有 ：

若 i>0 ， 双亲序号： (i-1)/2 ； i=0 ， i 为根结点编号 ，无双亲结点

若 2i+1<n ，左孩子序号： 2i+1 ，否则无左孩子

若 2i+2<n ，右孩子序号： 2i+2 ，否则无右孩子

假设父结点下标是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<Integer> list = new ArrayList<>();public List<Integer> preorderTraversal(TreeNode root) {if(root == null){return list;}list.add(root.val);preorderTraversal(root.left);preorderTraversal(root.right);return list;}
}

套娃存列表思想

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

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

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

---

图片遍历答案

前序：ABDEHCFG

中序：DBEHAFCG

后序：DHEBFGCA