Java：数据结构-二叉树
1.二叉树的概念：
二叉树是一种数据结构，其中每个节点最多有两个子节点，称为左子节点和右子节点。二叉树可以用于各种算法和数据操作
注：子树之间不能有交集，否则就不是树形结构，只能有一个父树。
2.二叉树的基本属性：
-
节点 (Node): 二叉树中的每个元素称为节点。每个节点包含数据，以及指向其左子节点和右子节点的指针。
-
根节点 (Root): 二叉树的顶点节点，通常称为根节点。一个二叉树只有一个根节点。
-
子节点 (Child Node): 根节点下面的节点称为子节点，一个节点可以有左子节点和右子节点。
-
叶节点 (Leaf Node): 没有子节点的节点称为叶节点。
-
父节点 (Parent Node): 具有子节点的节点称为其子节点的父节点。
-
深度 (Depth): 指从根节点到某个节点所经过的边的数量。根节点的深度为 0。
-
高度 (Height): 从某个节点到叶节点的最长路径的边数。叶节点的高度为 0。
-
层 (Level): 树的层数由根节点开始计算，根节点是第 1 层，它的子节点是第 2 层，依此类推。
3.两种特殊的二叉树
1.满二叉树
如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树
2.完全二叉树
完全二叉树是效率很高的数据结构，有n 个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完 比特就业课 全二叉树。
4.二叉树的性质：
5.简单的创建一个二叉树
public class BinaryTree {
static class TreeNode{
public TreeNode left;
public TreeNode right;
public int val;
public TreeNode(int val){
this.val=val;
}
}
public TreeNode creatTree(){
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;
}
}6.二叉树的遍历
1.前序遍历
先遍历根，再遍历左子树，最后遍历右子树
public void preOrder(TreeNode root){
if(root==null){
return;
}
System.out.println(root.val+" ");
preOrder(root.left);
preOrder(root.right);
}public List<Character> preOrder1(TreeNode root){
List<Character> list=new ArrayList<>();
if(root==null){
return list;
}
list.add(root.val);
List<Character> treeLeft=preOrder1(root.left);
list.addAll(treeLeft);
List<Character> treeRight=preOrder1(root.right);
list.addAll(treeRight);
return list;
}2.中序遍历
先遍历左子树，再遍历根，最后遍历右子树
public void inOrder(TreeNode root){
if(root==null){
return;
}
preOrder(root.left);
System.out.println(root.val+" ");
preOrder(root.right);
}3.后序遍历
先遍历左子树，再遍历右子树，最后遍历根
public void postOrder(TreeNode root){
if(root==null) {
return;
}
preOrder(root.left);
preOrder(root.right);
System.out.println(root.val+" ");
}4.层次遍历
7.二叉树的基本操作：
1.获取树中节点的个数
public static int size(TreeNode root){
if(root==null){
return -1;
}
usedSize++;
size(root.left);
size(root.right);
return usedSize;
}public int size1(TreeNode root){
if(root==null){
return -1;
}
return size(root.left)+size(root.right)+1;
}2.获取叶子节点的个数
整棵树的叶子等于左树的叶子加上右树的叶子
public void getLeafNodeCount(TreeNode root){
if (root==null){
return;
}
if(root.left==null && root.right==null){
leftCount++;
}
getLeafNodeCount(root.left);
getLeafNodeCount(root.right);
}public int getLeafNodeCount1(TreeNode root){
if (root==null){
return -1;
}
if(root.left==null && root.right==null){
return 1;
}
return getLeafNodeCount1(root.left)+getLeafNodeCount1(root.right);
}3.获取第K层节点的个数
public int getLLeaveNodeCount(TreeNode root,int k){
if(root==null){
return -1;
}
if(k==1){
return 1;
}
return getLLeaveNodeCount(root.left,k-1)+getLLeaveNodeCount(root.right,k-1);
}4.获取二叉树的高度
public int getHeight(TreeNode root){
if(root==null){
return -1;
}
return Math.max(getHeight(root.left),getHeight(root.right))+1;
}5.检测值为value的元素是否存在
public TreeNode find(TreeNode root, char val){
if(root==null){
return null;
}
if(root.val==val){
return root;
}
TreeNode left=find(root.left,val);
if(left!=null){
return left;
}
TreeNode right=find(root.right,val);
if(right!=null){
return right;
}
return null;
}6.层序遍历
public void levelOrder(TreeNode root){
if(root==null){
return;
}
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while (queue.isEmpty()){
TreeNode cur=queue.poll();
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!=null){
queue.offer(cur.right);
}
}
System.out.println();
}7. 判断一个二叉树是不是完全二叉树
public boolean isCompleteTree(TreeNode root){
if(root==null){
return true;
}
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while (queue.isEmpty()){
TreeNode cur=queue.poll();
if(cur.left!=null){
queue.offer(cur.left);
queue.offer(cur.right);
}else {
break;
}
}
while (!queue.isEmpty()){
TreeNode pek= queue.peek();
if(pek!=null){
return false;
}
queue.poll();
}
return true;
}希望能对大家有所帮助！！！！！！！！
