什么是二叉树？
树结构是一种非线性存储结构，存储的是具有一对多关系的数据的集合
而树形结构的一种抽象出来的数据结构往往是二叉树的形式
满足以下两个条件的树就是二叉树：
本身是有序树
树中包含的各个节点的度不能超过 2即只能是 0或者1 或者 2
接下来要分享的二叉树的基本构成如图
static class TreeNode{
public String val;//值
public TreeNode left;//左
public TreeNode right;//右
public TreeNode (String 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");
A.left=B; A.right=C;
B.left=D; B.right=E;
C.left=F; C.right=G;
return A;
//root=A;
}//new一个树
public void preOrder (TreeNode root){
if (root == null) return;
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}//前序打印
public void inOrder (TreeNode root){
if (root == null) return;
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}//中序打印
public void postOrder (TreeNode root){
if (root == null) return;
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}//后序打印
public void levelOrder(TreeNode root){
if (root==null)return;
Queue<TreeNode>queue=new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
TreeNode tmp=queue.poll();
System.out.print(tmp.val+" ");
if (tmp.left!=null){
queue.offer(tmp.left);
}
if (tmp.right!=null){
queue.offer(tmp.right);
}
}
}//层序打印
public int nodeSize;//存放长度
public void size(TreeNode root){
if (root == null) return ;
nodeSize++;
size(root.left);
size(root.right);
}//计算长度//遍历思路
public int size2(TreeNode root){
if(root==null)return 0;
return size2(root.left)+size2(root.right)+1;
}//计算长度//子问题思路
public int Count;//存放叶子
public void getNodeCount(TreeNode root) {
if (root==null)return ;
if (root.left==null&&root.right==null){
Count++;
}
getNodeCount(root.left);
getNodeCount(root.right);
}//获取叶子节点个数//遍历思路
public int getNodeCount1(TreeNode root){
if(root==null)return 0;
if (root.left==null&&root.right==null) {
return 1;
}
return getNodeCount1(root.left)+getNodeCount1(root.right);
}//获取叶子节点个数//子问题思路
public int getLevelNodeCount(TreeNode root,int k) {
if (root == null) {
return 0;
}
if (k == 1) return 1;
return getLevelNodeCount(root.left,k-1)
+getLevelNodeCount(root.right,k-1);
}//某一层数节点的个数
public int getHeight(TreeNode root){
if (root==null)return 0;
int Hei1=getHeight(root.left);
int Hei2=getHeight(root.right);
return Hei1>Hei2?Hei1+1:Hei2+1;
}//获取二叉树高度
public TreeNode find(TreeNode root,String val){
if (root==null)return null;
if(root.val.equals(val))return root;
TreeNode tmp= find(root.left,val);
if (tmp!=null)return tmp;
return find(root.right,val);
}//查找二叉树中的val值
