如果节点为空，则个数肯定为0；如果不为空，则算上这个节点之后，继续递归计算所有子树的节点数，全部相加即可
/** * 获取某个节点及子树的节点个数 * @param node * @return */ public int size(BinaryTreeNode node){ if (node==null){ return 0; } //递归获取左子树节点数 int l=size(node.getLeftChild()); //递归获取右子树节点数 int r=size(node.getRightChild()); return l+r+1; } /** * 获取二叉树节点个数 * @return */ public int size(){ return size(root); }2.2.6、获取末端叶子节点
通过递归左右子树，获得左右子树末端的叶子节点。
/** * 获取节点左子树的末端节叶子点 * @param node * @return */ public BinaryTreeNode getLeftLeaf(BinaryTreeNode node){ if (node==null){ return null; } if (node.getLeftChild()==null){ return node; }else{ node=getLeftLeaf(node.getLeftChild()); } return node; } /** * 获取整个二叉树左子树最末端的叶子节点 * @return */ public BinaryTreeNode getLeftLeaf(){ return getLeftLeaf(root); } /** * 获取某个节点右子树最末端的叶子节点 * @param node * @return */ public BinaryTreeNode getRightLeaf(BinaryTreeNode node){ if (node==null){ return null; } if (node.getRightChild()==null){ return node; }else{ node=getRightLeaf(node.getRightChild()); } return node; } /** * 获取整个二叉树右子树最末端叶子节点 * @return */ public BinaryTreeNode getRightLeaf(){ return getRightLeaf(root); }2.2.7、插入
这里只是实现了给节点插入左孩子、右孩子,只考虑了插入的节点的左右孩子不存在的情况。
/** * 给某个节点插入左孩子 * @param parent * @param newNode */ public void insertLeft(BinaryTreeNode parent,BinaryTreeNode newNode){ parent.setLeftChild(newNode); newNode.setParent(parent); } /** * 给某个节点插入右孩子 * @param parent * @param newNode */ public void insertRitht(BinaryTreeNode parent,BinaryTreeNode newNode){ parent.setRightChild(newNode); newNode.setParent(parent); }2.2.8、删除
从二叉树中删除节点，稍微复杂一些，需要考虑三种情形。
被删除的节点左右子树均为空
这是最简单的一种情形，只需要把被被删除节点的父亲节点的孩子节点指向null即可。
被删除的节点左右子树有一个为空
这种情形，只需要将被删除元素的左子树的父节点移动到被删除元素的父节点，然后将被删除元素移除即可。
图9：二叉树节点删除——左子树为空
被删除的节点左右子树均不为空
这是最复杂的一种情形。这里博主偷了一个懒，选择了填坑的方式，将需要删除的节点删除，挖了一个坑，找到二叉树左子树叶子节点，把这个节点给填进去。
具体代码实现：
/** * 删除节点 * @param subNode 遍历的节点 * @param node 待删除节点 * @return */ public BinaryTreeNode deleteNode(BinaryTreeNode subNode,BinaryTreeNode node){ if (subNode==null){ return null; } //父节点 BinaryTreeNode parent=null; if (subNode.equals(node)){ parent=node.getParent(); //情形1、当前节点没有孩子节点 if (subNode.getLeftChild()==null&&subNode.getRightChild()==null){ //删除父节点和当前节点的关联 this.changeChild(parent,subNode,null); //情形2、当前节点只有左节点或右节点 } else if (subNode.getLeftChild()==null){ //情形2.1只有右孩子节点 //将父节点孩子节点设置为当前节点的右孩子 this.changeChild(parent,subNode,subNode.getRightChild()); }else if (subNode.getRightChild()==null){ //情形2，2只有左孩子节点 //将父节点孩子节点设置为当前节点的左孩子 this.changeChild(parent,subNode,subNode.getLeftChild()); }else{ //情形3、左右孩子节点都有 //左子树末端叶子节点 BinaryTreeNode leftLeaf=getLeftLeaf(subNode); //将父节点孩子节点设置为末端叶子节点 this.changeChild(parent,subNode,leftLeaf); //将叶子节点父节点子节点置为null this.changeChild(leftLeaf.getParent(),leftLeaf,null); //叶子节点父节点 leftLeaf.setParent(parent); //被删除的节点置为null，帮助gc subNode=null; } } //递归左子树 if (deleteNode(subNode.getLeftChild(),node)!=null){ deleteNode(subNode.getLeftChild(),node); }else { //递归右子树 deleteNode(subNode.getRightChild(),node); } return subNode; } /** * 替换父亲节点的孩子节点 * @param parent 父亲节点 * @param replacedNode 被替换的节点 * @param aimNode 替换的节点 */ void changeChild(BinaryTreeNode parent,BinaryTreeNode replacedNode,BinaryTreeNode aimNode){ //被替换节点是左孩子 if (replacedNode==parent.getLeftChild()){ parent.setLeftChild(aimNode); }else{ //被替换节点是右孩子 parent.setRightChild(aimNode); } }2.3、遍历二叉树
常见的二叉树遍历方法有前序、中序、后序、层次等。
2.3.1、前序遍历
前序遍历(Preorder Traversal)是先遍历根结点， 再遍历左子树， 最后才遍历右子树。 及时二叉树非空， 则依次进行如下操作：
访问根节点
前序遍历左子树
前序遍历右子树