🎈一.二叉树相关概念

1.树

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合，树结构通常用来存储逻辑关系为 "一对多" 的数据。例如：

关于树的几个重要概念：

1）树的度：一棵树中，所有结点度的最大值称为树的度，如上图，这棵树的度为3；

2）节点的度：一个结点含有子树的个数称为该结点的度，如上图，A节点的度为3；

3）根节点：一棵树中，没有双亲结点的结点，如上图，A就是根节点；

4）叶子节点：简单来说，度为0的就是叶子节点，如上图，K，L，F，M等都是叶子节点；

5）树的高度或深度：树中结点的最大层次，如上图，树的高度为4；

那么什么是二叉树呢？

简单地理解，满足以下两个条件的树就是二叉树：

1. 本身是有序树；
2. 树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；

如图：

🎈二.二叉树的性质

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

2.若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是2^k-1 (k>=0)；

3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1；

✅关于此结论的推导：

对于任意一棵二叉树,一棵有N个节点的树就有N-1条边

假设度为0的节点为n0,度为1的节点为n1，度为2的节点为n2，度为0的节点没有边，度为1的节点有1条边，度为2的节点有2条边，由此可得：

N-1=n1*1+n2*2   ----------------产生的边的关系

N=n0+n1+n2       ----------------产生节点的关系

联立就可以得出这个结论：n0=n2+1

4.具有n个结点的完全二叉树的深度k为 log2(n+1)上取整；

✅习题：

1)  在具有 2n 个结点的完全二叉树中，叶子结点个数为（A）；

A .n            B. n+1            C. n-1           D. n/2

解析：

完全二叉树分奇偶数俩种情况，如上图，本题有2n个节点，是偶数，那么度为1的节点数只有1个，所以可知:

2n=n0+n1+n2;

n0=n2+1;

代入可求：n0=n;

2）一个具有767个节点的完全二叉树，其叶子节点个数为（B）；

A. 383         B. 384             C. 385           D. 386

解析：因为它是一棵完全二叉树，节点数为奇数，说明它是一棵满二叉树，所以没有度为1的节点，由此可知：

767=n0+n2;

n0=n2+1;

联立上式可以求出答案

🎈三.构造二叉树

二叉树的存储结构分为：顺序存储和类似于链表的链式存储。

构造一个类，里面存放左子树，右子树，数据域；

publicstaticclassTreeNode {
publiccharval;//数据域publicTreeNodeleft;//左节点publicTreeNoderight;//右节点publicTreeNode(charval) {
this.val=val;
        }
    }
//构造树publicTreeNodecreateTree() {
TreeNodenode1=newTreeNode('A');
TreeNodenode2=newTreeNode('B');
TreeNodenode3=newTreeNode('C');
TreeNodenode4=newTreeNode('D');
TreeNodenode5=newTreeNode('E');
TreeNodenode6=newTreeNode('F');
TreeNodenode7=newTreeNode('G');
node1.left=node2;
node1.right=node3;
node2.left=node4;
node2.right=node5;
node3.left=node6;
node3.right=node7;
returnnode1;
    }
}