1 二叉树的基本概念

（1）树有很多种，每个节点最多只能有两个子节点的树就是二叉树。
（2）二叉树的子节点分为左节点和右节点
（3）示意图

（4）如果所有二叉树的叶节点都在最后一层，并且节点总数为2*n-1，n为层数，则该二叉树为满二叉树。

（5）如果该二叉树的所有叶节点都在最后一层或者倒数第二层，而且最后一层的叶节点在左边连续，倒数第二层的叶节点在右边连续，则该二叉树为完全二叉树。

2 二叉树的遍历

二叉树的遍历方式有四种，前序遍历、中序遍历、后序遍历和层次遍历。这里介绍以下三种常用的遍历算法。
（1）前序遍历：先输出父节点，再遍历左子树和右子树
（2）中序遍历：先遍历左子树，再输出父节点，再遍历右子树
（3）后序遍历：先遍历左子树，在遍历右子树，再输出父节点
（4）小结：看父节点的输出顺序，确定是前序、中序还是后序。

3 代码实现二叉树的遍历

public class BinaryTreeDemo {public static void main(String[] args) {//创建一颗空二叉树BinaryTree binaryTree = new BinaryTree();//创建需要的节点TreeNode root = new TreeNode(1);TreeNode node2 = new TreeNode(2);TreeNode node3 = new TreeNode(3);TreeNode node4 = new TreeNode(4);TreeNode node5 = new TreeNode(5);//手动创建二叉树root.setLeft(node2);root.setRight(node3);node3.setRight(node4);node3.setLeft(node5);binaryTree.setRoot(root);}
}
//创建二叉树
class BinaryTree{private TreeNode root;public void setRoot(TreeNode root){this.root = root;}//前序遍历public void preOrder(){if (this.root != null){this.root.preOrder();}else {System.out.println("二叉树为空，无法遍历");}}//中序遍历public void infixOrder(){if (this.root != null){this.root.infixOrder();}else {System.out.println("二叉树为空，无法遍历");}}//后序遍历public void postOrder(){if (this.root != null){this.root.postOrder();}else {System.out.println("二叉树为空，无法遍历");}}//先序遍历查找public boolean preOrderSearch(int no){if (this.root != null){TreeNode resNode = this.root.preOrderSearch(no);if (resNode != null)  return true;}else {System.out.println("二叉树为空，无法查找!\n");}return false;}//中序遍历查找public boolean infixOrderSearch(int no){if (this.root != null){TreeNode resNode = this.root.infixOrderSearch(no);if (resNode != null) {return true;}}else {System.out.println("二叉树为空，无法查找!\n");}return false;}//后序遍历查找public boolean postOrderSearch(int no){if (this.root != null){TreeNode resNode = this.root.postOrderSearch(no);if (resNode != null) return true;}else {System.out.println("二叉树为空，无法查找!\n");}return false;}//递归删除节点public void delNode(int no){if (root != null){//如果只有一个root节点，判断root是否是需要删除的节点if (root.getVal() == no){root = null;}else {//递归删除root.deleteNode(no);}}else {System.out.println("空树，不能删除!");}}}//创建二叉树的节点
class TreeNode{int val;TreeNode left;TreeNode right;TreeNode(){}TreeNode(int val){this.val =val;}TreeNode(int val,TreeNode left,TreeNode right){this.val = val;this.left = left;this.right = right;}public int getVal() {return val;}public void setVal(int val) {this.val = val;}public TreeNode getLeft() {return left;}public void setLeft(TreeNode left) {this.left = left;}public TreeNode getRight() {return right;}public void setRight(TreeNode right) {this.right = right;}//编写前序遍历方法public void preOrder(){System.out.print(this.val+" "); //先输出父节点//递归向左子树前序遍历if (this.left != null){this.left.preOrder();}//递归向右子树前序遍历if (this.right != null){this.right.preOrder();}}//中序遍历public void infixOrder(){//递归向左子树中序遍历if (this.left != null){this.left.infixOrder();}//输出父节点System.out.print(this.val+" ");;//递归向右子树中序遍历if (this.right != null){this.right.preOrder();}}//后序遍历public void postOrder(){//递归向左子树后序遍历if (this.left != null){this.left.postOrder();}//递归向右子树后序遍历if (this.right != null){this.right.postOrder();}//输出根节点System.out.print(this.val+" ");}
}

4 代码实现前序、中序、后序查找

//前序遍历查找public TreeNode preOrderSearch(int no){if (this.val == no){return this;}TreeNode resNode = null;if (this.left != null){resNode = this.left.preOrderSearch(no);}if (this.right != null){resNode = this.right.preOrderSearch(no);}return resNode;}//中序遍历查找public TreeNode infixOrderSearch(int no){//判断当前节点的左子节点是否为空，如果不为空，则递归中序查找TreeNode resNode = null;if (this.left != null){resNode = this.left.infixOrderSearch(no);}if (resNode != null){return resNode;}System.out.println("进入中序查找\n");if (this.val == no){return this;}if (this.right != null){resNode = this.right.infixOrderSearch(no);}return resNode;}//后序遍历查找public TreeNode postOrderSearch(int no){TreeNode resNode = null;if (this.left != null){resNode = this.left.postOrderSearch(no);}if (resNode != null){  //说明左子树找到return resNode;}if (this.right != null){resNode = this.right.postOrderSearch(no);}if (resNode != null){  //说明右子树找到return resNode;}System.out.println("进入后序遍历\n");//如果左右子树都没有找到if (this.val == no){return this;}return resNode;}

5 代码实现二叉树指定节点的删除

    //递归删除节点//1.如果删除的节点是叶子节点，则删除该节点//2.如果删除的节点是非叶子节点，则删除该子树public void deleteNode(int no){//如果当前节点的左子节点不为空，并且左子节点就是要删除的节点，就将this.left = null;并且就返回(结束递归删除)if (this.left != null && this.left.val == no){this.left = null;return;}//如果当前节点的右子节点不为空，并且右子节点就是要删除的节点，就将this.right = null;并且就返回(结束递归删除)if (this.right != null && this.right.val == no){this.right = null;return;}//向左子树递归删除if (this.left != null){this.left.deleteNode(no);}//向右子树递归删除if (this.right != null){this.right.deleteNode(no);}}