二叉树（数据结构）
1.两种特殊的二叉树
1.
满二叉树
:
一棵二叉树，如果
每层的结点数都达到最大值，则这棵二叉树就是满二叉树
。也就是说，
如果一棵
二叉树的层数为
K
，且结点总数是2^k-1
，则它就是满二叉树
。
2.
完全二叉树
:
完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为
K
的，有
n个结点的二叉树，当且仅当其每一个结点都与深度为K
的满二叉树中编号从
0
至
n-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
4.
具有
n
个结点的完全二叉树的深度
k
为log（n+1）
上取整
5.
对于具有
n
个结点的完全二叉树
，如果按照
从上至下从左至右的顺序对所有节点从
0
开始编号
，则对于
序号为
i
的结点有
：
若
i>0
，
双亲序号：
(i-1)/2
；
i=0
，
i
为根结点编号
，无双亲结点
若
2i+1<n
，左孩子序号：
2i+1
，否则无左孩子
若
2i+2<n
，右孩子序号：
2i+2
，否则无右孩子
3.二叉树的存储
二叉树的存储结构
分为：
顺序存储
和
类似于链表的链式存储
。
常见是
类似于链表的链式存储。
二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式
，具体如下：
// 孩子表示法class Node {int val ; // 数据域Node left ; // 左孩子的引用，常常代表左孩子为根的整棵左子树Node right ; // 右孩子的引用，常常代表右孩子为根的整棵右子树}// 孩子双亲表示法class Node {int val ; // 数据域Node left ; // 左孩子的引用，常常代表左孩子为根的整棵左子树Node right ; // 右孩子的引用，常常代表右孩子为根的整棵右子树Node parent ; // 当前节点的根节点}
4.创建二叉树
输入一串合法的前序遍历字符串，先创建根节点，不为'#'再递归创建左孩子，如果是就回退到上一个节点，再递归创建左孩子右孩子，连续遇到两个‘#’则一个子树创建完成。
代码如下：
class Main {
public static class TreeNode {
Character val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(Character val) {
this.val = val;
}
TreeNode(Character val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}//内部类（树节点）
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
// while (in.hasNextInt()) { // 注意 while 处理多个 case
String s = in.nextLine();
TreeNode root = createTree(s);//递归创建二叉树
order(root);
// }
}
public static int i = 0;
public static TreeNode createTree(String s) {
TreeNode root = null;
if (s.charAt(i) != '#') {
root = new TreeNode(s.charAt(i));
i++;
root.left = createTree(s);
root.right = createTree(s);
} else {
i++;
}
return root;
}
}
例：
root = [1,null,2,3]
5.二叉树的基本操作
// 获取树中节点的个数
int size(Node root){
if(root==null){
return 0;
}
return size2(root.right)+size2(root.left)+1;
}
// 获取叶子节点的个数
public static int leafSize = 0;
int getLeafNodeCount(Node root){
if(root==null){
return ;
}
if(root.left==null&&root.right==null){
leafSize++;
}
getLeafNodeCount1(root.right);
getLeafNodeCount1(root.left);
}
// 获取第K层节点的个数
int getKLevelNodeCount(Node root,int k){
if(root==null){
return 0;
}
if(k==1){
return 1;
}
return getKLevelNodeCount(root.left,k-1)+
getKLevelNodeCount(root.right,k-1);
}
// 获取二叉树的高度
int getHeight(Node root){
if(root==null){
return 0;
}
int leftL=getHeight(root.left);
int rightL=getHeight(root.right);
// return right>left?right+1:left+1;
return Math.max(rightL,leftL)+1;
}
// 检测值为value的元素是否存在
Node find(Node root, int val){
if(root==null){
return null;
}
if(root.val==val){
return root;
}
TreeNode leftT=find(root.left,val);
if(leftT!=null) {
return leftT;
}
TreeNode rightT=find(root.right,val);
if(rightT!=null){
return rightT;
}
return null;
}
//层序遍历
void levelOrder(Node root){
if(root==null){
return ;
}
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
TreeNode cur= queue.poll();
System.out.println(cur.val+" ");
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!=null){
queue.offer(cur.right);
}
}
System.out.println();
}
// 判断一棵树是不是完全二叉树
boolean isCompleteTree(Node root){
if(root==null){
return true;
}
int leftL=getHeight(root.left);
int rightL=getHeight(root.right);
if(leftL-rightL>1||rightL-leftL>1){
return false;
}
return isBalanced(root.left)&&isBalanced(root.right);//时间复杂度O(n^2)
//return getHeight2>0 时间复杂度O(n)
}