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;}希望能对大家有所帮助！！！！！！！！
