二叉树是一种非线性数据结构，二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用。在二叉树中，除叶节点外，其他所有节点都包含子节点和非空子树。
二叉树的常见术语包括一下几个：
根节点：位于二叉树顶层的节点，没有父节点。
叶节点：没有子节点的节点，其两个指针均指向 None 。
边：连接两个节点的线段，即节点引用（指针）。
节点所在的层：从顶至底递增，根节点所在层为 1 。
节点的度：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。
二叉树的高度：从根节点到最远叶节点所经过的边的数量。
节点的深度：从根节点到该节点所经过的边的数量。
节点的高度：从距离该节点最远的叶节点到该节点所经过的边的数量。
二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历等。
1，层次遍历从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。层序遍历本质上属于广度优先搜索（BFS），它体现了一种“一圈一圈向外扩展”的逐层遍历方式。广度优先搜索通常借助“队列”来实现
/* 层序遍历 */List<Integer>levelOrder(TreeNoderoot){// 初始化队列，加入根节点Queue<TreeNode>queue=newLinkedList<>();queue.add(root);// 初始化一个列表，用于保存遍历序列List<Integer>list=newArrayList<>();while(!queue.isEmpty()){TreeNodenode=queue.poll();// 队列出队list.add(node.val);// 保存节点值if(node.left!=null)queue.offer(node.left);// 左子节点入队if(node.right!=null)queue.offer(node.right);// 右子节点入队}returnlist;}前序、中序和后序遍历都属于深度优先搜索（DFS），它体现了一种“先走到尽头，再回溯继续”的遍历方式。深度优先搜索通常基于递归实现：
/* 前序遍历 */voidpreOrder(TreeNoderoot){if(root==null)return;// 访问优先级：根节点 -> 左子树 -> 右子树list.add(root.val);preOrder(root.left);preOrder(root.right);}/* 中序遍历 */voidinOrder(TreeNoderoot){if(root==null)return;// 访问优先级：左子树 -> 根节点 -> 右子树inOrder(root.left);list.add(root.val);inOrder(root.right);}/* 后序遍历 */voidpostOrder(TreeNoderoot){if(root==null)return;// 访问优先级：左子树 -> 右子树 -> 根节点postOrder(root.left);postOrder(root.right);list.add(root.val);}二叉树不仅可以用链表实现，数组同样可以实现。若某节点的索引为 i ，则该节点的左子节点索引为 2I+1，右子节点索引为 2I+2。
二叉搜索树基于二叉树，同时要满足对于根节点，左子树中所有节点的值
小于根节点的值 小于右子树中所有节点的值，并且任意节点的左右子树也满足这个条件。
1，二叉搜索树的查找和二分查找算法原理一致，都是每轮排除一半情况，循环次数最多为二叉树的高度，二叉树的中序遍历遵循“左 根 右”的遍历顺序，而二叉搜索树满足“左子节点 小于 根节点 小于右子节点”的大小关系，因此，二叉搜索树的中序遍历序列是升序的。利用中序遍历升序的性质，我们在二叉搜索树中获取有序数据仅需 On时间，无须进行额外的排序操作，非常高效。
/* 查找节点 */TreeNodesearch(intnum){TreeNodecur=root;// 循环查找，越过叶节点后跳出while(cur!=null){// 目标节点在 cur 的右子树中if(cur.val<num)cur=cur.right;// 目标节点在 cur 的左子树中elseif(cur.val>num)cur=cur.left;// 找到目标节点，跳出循环elsebreak;}// 返回目标节点returncur;}2，插入节点，给定一个待插入元素 num ，为了保持二叉搜索树“左子树 < 根节点 < 右子树”的性质，与查找操作相似，从根节点出发，根据当前节点值和 num 的大小关系循环向下搜索，直到越过叶节点（遍历至 None ）时跳出循环。在该位置插入节点：初始化节点 num ，将该节点置于 None 的位置。二叉搜索树不允许存在重复节点，否则将违反其定义。因此，若待插入节点在树中已存在，则不执行插入，直接返回。为了实现插入节点，我们需要借助节点 pre 保存上一轮循环的节点。这样在遍历至 None 时，我们可以获取到其父节点，从而完成节点插入操作。
/* 插入节点 */voidinsert(intnum){// 若树为空，则初始化根节点if(root==null){root=newTreeNode(num);return;}TreeNodecur=root,pre=null;// 循环查找，越过叶节点后跳出while(cur!=null){// 找到重复节点，直接返回if(cur.val==num)return;pre=cur;// 插入位置在 cur 的右子树中if(cur.val<num)cur=cur.right;// 插入位置在 cur 的左子树中elsecur=cur.left;}// 插入节点TreeNodenode=newTreeNode(num);if(pre.val<num)pre.right=node;elsepre.left=node;}删除节点，先在二叉树中查找到目标节点，再将其删除。与插入节点类似，我们需要保证在删除操作完成后，二叉搜索树的“左子树 < 根节点 < 右子树”的性质仍然满足。因此，我们根据目标节点的子节点数量，分 0、1 和 2 三种情况，执行对应的删除节点操作。当待删除节点的度为 0时，表示该节点是叶节点，可以直接删除。当待删除节点的度为 1时，将待删除节点替换为其子节点即可。当待删除节点的度为 2 时，我们无法直接删除它，而需要使用一个节点替换该节点。由于要保持二叉搜索树“左子树 小于根节点 小于右子树”的性质，因此这个节点可以是右子树的最小节点或左子树的最大节点。
/* 删除节点 */voidremove(intnum){// 若树为空，直接提前返回if(root==null)return;TreeNodecur=root,pre=null;// 循环查找，越过叶节点后跳出while(cur!=null){// 找到待删除节点，跳出循环if(cur.val==num)break;pre=cur;// 待删除节点在 cur 的右子树中if(cur.val<num)cur=cur.right;// 待删除节点在 cur 的左子树中elsecur=cur.left;}// 若无待删除节点，则直接返回if(cur==null)return;// 子节点数量 = 0 or 1if(cur.left==null||cur.right==null){// 当子节点数量 = 0 / 1 时， child = null / 该子节点TreeNodechild=cur.left!=null?cur.left:cur.right;// 删除节点 curif(cur!=root){if(pre.left==cur)pre.left=child;elsepre.right=child;}else{// 若删除节点为根节点，则重新指定根节点root=child;}}// 子节点数量 = 2else{// 获取中序遍历中 cur 的下一个节点TreeNodetmp=cur.right;while(tmp.left!=null){tmp=tmp.left;}// 递归删除节点 tmpremove(tmp.val);// 用 tmp 覆盖 curcur.val=tmp.val;}}