🎈一.二叉树相关概念
1.树
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合，树结构通常用来存储逻辑关系为 "一对多" 的数据。例如：
关于树的几个重要概念：
1）树的度：一棵树中，所有结点度的最大值称为树的度，如上图，这棵树的度为3；
2）节点的度：一个结点含有子树的个数称为该结点的度，如上图，A节点的度为3；
3）根节点：一棵树中，没有双亲结点的结点，如上图，A就是根节点；
4）叶子节点：简单来说，度为0的就是叶子节点，如上图，K，L，F，M等都是叶子节点；
5）树的高度或深度：树中结点的最大层次，如上图，树的高度为4；
那么什么是二叉树呢？
简单地理解，满足以下两个条件的树就是二叉树：
- 本身是有序树；
- 树中包含的各个节点的度不能超过 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; } }
