1.引言
这一段时间都没看java数据结构，松懈了。今天记录下二叉树的遍历，建树，删除节点。下一章 会用非递归的方式实现一下。
2.正题
新建一个TreeNode类：
public class TreeNode {
private String tag;
private int number;
private TreeNode leftNode;
private TreeNode rightNode;
//自己实现get、set
}
2.1 建立二叉树
递归参数：等待插入的节点A，父节点B（假如插入成功）
核心思想：假如A.number<B.number。表示在B的左边。然后在判断B.leftNode 是否为null；为null，就将A插进入，不为null，就进行递归。同理A.number>B.number一样。
实现代码：
public TreeNode rootNode;
public void buildTree(TreeNode treeNode,TreeNode binaryTree){
if (rootNode==null){
rootNode=treeNode;
rootNode.setLeftNode(null);
rootNode.setRightNode(null);
return;
}
if (treeNode.getNumber()<binaryTree.getNumber()){
if (binaryTree.getLeftNode()!=null){
buildTree(treeNode,binaryTree.getLeftNode());
}else {
binaryTree.setLeftNode(treeNode);
}
}else {
if (binaryTree.getRightNode()!=null){
buildTree(treeNode,binaryTree.getRightNode());
}else {
binaryTree.setRightNode(treeNode);
}
}
}
main函数：
BinaryTree binaryTree=new BinaryTree();
List<TreeNode>treeNodes=new ArrayList<>();
treeNodes.add(new TreeNode("A",6));
treeNodes.add(new TreeNode("B",3));
treeNodes.add(new TreeNode("C",7));
treeNodes.add(new TreeNode("D",1));
treeNodes.add(new TreeNode("E",4));
treeNodes.add(new TreeNode("F",9));
treeNodes.forEach(treeNode -> {binaryTree.buildTree(treeNode,binaryTree.rootNode);});
2.2前序遍历
递归参数：TreeNode
核心思想：先输出当前节点的tag，然后判断是否存在左节点。存在的话递归。然后在判断右节点是否存在，存在递归。
/**
* A
* B C
* D E F
*
* 前序遍历 ABDECF
*/
public void preorderTraversal(TreeNode treeNode){
if (treeNode==null)
return;
System.out.print(treeNode.getTag());
if (treeNode.getLeftNode()!=null)
preorderTraversal(treeNode.getLeftNode());
if (treeNode.getRightNode()!=null)
preorderTraversal(treeNode.getRightNode());
}
2.3中序遍历
递归参数：TreeNode
核心思想：先判断是否存在左节点。存在的话递归。然后输出节点的tag，然后在判断是否存在右节点。存在递归，
/**
* A
* B C
* D E F
*
* 中序遍历 DBEACF
*/
public void inorderTraversal(TreeNode treeNode){
if (treeNode==null)
return;
if (treeNode.getLeftNode()!=null)
inorderTraversal(treeNode.getLeftNode());
System.out.print(treeNode.getTag());
if (treeNode.getRightNode()!=null)
inorderTraversal(treeNode.getRightNode());
}
2.4后序遍历
递归参数：TreeNode
核心思想：先判断是否存在左节点。存在的话递归。然后在判断是否存在右节点。存在递归。然后输出节点的tag。
/**
* A
* B C
* D E F
*
* 后序遍历 DEBFCA
*/
public void afterOrderTraversal(TreeNode treeNode){
if (treeNode==null)
return;
if (treeNode.getLeftNode()!=null)
afterOrderTraversal(treeNode.getLeftNode());
if (treeNode.getRightNode()!=null)
afterOrderTraversal(treeNode.getRightNode());
System.out.print(treeNode.getTag());
}
2.5删除节点：
节点的删除和节点的插入思想一样。实现代码
/**
* 删除节点
* @param delete
*/
public void deleteNode(TreeNode delete,TreeNode rootNode){
if (delete==null)
return;
if (rootNode.getNumber()==delete.getNumber()){
rootNode=null;
return;
}
if (rootNode.getLeftNode()!=null){
if (rootNode.getLeftNode().getNumber()==delete.getNumber()){
rootNode.setLeftNode(null);
}else {
deleteNode(delete, rootNode.getLeftNode());
}
}
if (rootNode.getRightNode()!=null){
if (rootNode.getRightNode().getNumber()==delete.getNumber()){
rootNode.setRightNode(null);
}else {
deleteNode(delete, rootNode.getRightNode());
}
}
}
总体来说：二叉树的递归实现还是比较简单的,下一篇将二叉树的非递归算法。
完整代码：
import java.util.ArrayList;
import java.util.List;
/**
* Created by wxy on 2017/6/4.
*/
public class BinaryTree {
public TreeNode rootNode;
public void buildTree(TreeNode treeNode,TreeNode binaryTree){
if (rootNode==null){
rootNode=treeNode;
rootNode.setLeftNode(null);
rootNode.setRightNode(null);
return;
}
if (treeNode.getNumber()<binaryTree.getNumber()){
if (binaryTree.getLeftNode()!=null){
buildTree(treeNode,binaryTree.getLeftNode());
}else {
binaryTree.setLeftNode(treeNode);
}
}else {
if (binaryTree.getRightNode()!=null){
buildTree(treeNode,binaryTree.getRightNode());
}else {
binaryTree.setRightNode(treeNode);
}
}
}
/**
* A
* B C
* D E F
*
* 前序遍历 ABDECF
*/
public void preorderTraversal(TreeNode treeNode){
if (treeNode==null)
return;
System.out.print(treeNode.getTag());
if (treeNode.getLeftNode()!=null)
preorderTraversal(treeNode.getLeftNode());
if (treeNode.getRightNode()!=null)
preorderTraversal(treeNode.getRightNode());
}
/**
* A
* B C
* D E F
*
* 中序遍历 DBEACF
*/
public void inorderTraversal(TreeNode treeNode){
if (treeNode==null)
return;
if (treeNode.getLeftNode()!=null)
inorderTraversal(treeNode.getLeftNode());
System.out.print(treeNode.getTag());
if (treeNode.getRightNode()!=null)
inorderTraversal(treeNode.getRightNode());
}
/**
* A
* B C
* D E F
*
* 后序遍历 DEBFCA
*/
public void afterOrderTraversal(TreeNode treeNode){
if (treeNode==null)
return;
if (treeNode.getLeftNode()!=null)
afterOrderTraversal(treeNode.getLeftNode());
if (treeNode.getRightNode()!=null)
afterOrderTraversal(treeNode.getRightNode());
System.out.print(treeNode.getTag());
}
/**
* 删除节点
* @param delete
*/
public void deleteNode(TreeNode delete,TreeNode rootNode){
if (delete==null)
return;
if (rootNode.getNumber()==delete.getNumber()){
rootNode=null;
return;
}
if (rootNode.getLeftNode()!=null){
if (rootNode.getLeftNode().getNumber()==delete.getNumber()){
rootNode.setLeftNode(null);
}else {
deleteNode(delete, rootNode.getLeftNode());
}
}
if (rootNode.getRightNode()!=null){
if (rootNode.getRightNode().getNumber()==delete.getNumber()){
rootNode.setRightNode(null);
}else {
deleteNode(delete, rootNode.getRightNode());
}
}
}
public static void main(String args[]){
BinaryTree binaryTree=new BinaryTree();
List<TreeNode>treeNodes=new ArrayList<>();
treeNodes.add(new TreeNode("A",6));
treeNodes.add(new TreeNode("B",3));
treeNodes.add(new TreeNode("C",7));
treeNodes.add(new TreeNode("D",1));
treeNodes.add(new TreeNode("E",4));
treeNodes.add(new TreeNode("F",9));
treeNodes.forEach(treeNode -> {binaryTree.buildTree(treeNode,binaryTree.rootNode);});
System.out.print("前序遍历 ");
binaryTree.preorderTraversal(binaryTree.rootNode);
System.out.print("\n"+"中序遍历 ");
binaryTree.inorderTraversal(binaryTree.rootNode);
System.out.print("\n"+"后序遍历 ");
binaryTree.afterOrderTraversal(binaryTree.rootNode);
System.out.print("\n"+"删除节点B ");
binaryTree.deleteNode(treeNodes.get(4),binaryTree.rootNode);
binaryTree.preorderTraversal(binaryTree.rootNode);
binaryTree.inorderTraversal(binaryTree.rootNode);
binaryTree.afterOrderTraversal(binaryTree.rootNode);
}
}
