用Java谈谈二叉树的增删改查
目录
前言
一、二叉树的前中后序遍历
前序遍历
中序遍历
后序遍历
节点的删除
节点的修改
节点的获取
总结
前言
树属于数据结构中的非线性结构，最常见的树就属二叉树了。那么在二叉树中，如何使用Java实现二叉树中元素的增删改查呢？
首先我们先创建一个类代表用户节点，以及一个二叉树类：
class UserNode {String userName;int userId;UserNode left;UserNode right;public UserNode(String userName , int userId) {this.userName = userName;this.userId = userId;}@Overridepublic String toString() {return "UserNode{" +"userName='" + userName + '\'' +", userId='" + userId + '\'' +'}';}
}class BinaryTree {UserNode root;public BinaryTree(UserNode root) {this.root = root;}
}并且为该二叉树添加节点：
public static void main(String[] args) {UserNode userNode0 = new UserNode("张零", 0);UserNode userNode1 = new UserNode("李一", 1);UserNode userNode2 = new UserNode("王二", 2);UserNode userNode3 = new UserNode("杨三", 3);UserNode userNode4 = new UserNode("胡四", 4);UserNode userNode5 = new UserNode("邓五", 5);UserNode userNode6 = new UserNode("吕六", 6);userNode0.left = userNode1;userNode0.right = userNode2;userNode1.left = userNode3;userNode1.right = userNode4;userNode2.left = userNode5;userNode2.right = userNode6;BinaryTree binaryTree = new BinaryTree(userNode0);}一、二叉树的前中后序遍历
在二叉树中，根据二叉树的结构特点，我们可以对二叉树进行前中后序的遍历。
前序遍历
前序遍历的顺序主要是从父节点开始，输入父结点之后，继续向左节点遍历，左节点遍历完成之后再遍历右节点。
在前序遍历中，首先输出的就是root根节点，输出之后，继续向左递归，输出1，在1中，再次向左递归，输出3. 输出完之后，由于3是二叉树的叶子节点，此时返回到1处，向右递归，输出4，由于4也是二叉树的叶子节点，输出完成之后就返回，此时1的左节点和右节点已经遍历完成，重新返回到root处进行右节点的遍历。遍历到2的时候，输出2，此时向左节点5进行遍历。以此遍历，最后输出的结果是：
0 1 3 4 2 5 6
public void preOrder (UserNode node) {System.out.println(node);if (node.left != null) {this.preOrder(node.left);}if (node.right != null) {this.preOrder(node.right);}}中序遍历
同理，中序遍历则是先输出左节点，再输出父节点，再输出右节点。
public void midOrder (UserNode node) {if (node.left != null) {this.midOrder(node.left);}System.out.println(node);if (node.right != null) {this.midOrder(node.right);}}最后的输出结果是：3 1 4 0 5 2 6
后序遍历
后序遍历则是先输出左节点，再输出右节点，最后输出父节点。
public void postOrder (UserNode node) {if (node.left != null) {this.postOrder(node.left);}if (node.right != null) {this.postOrder(node.right);}System.out.println(node);}最后的输出结果是：3 4 1 5 6 2 0
二、节点的删除、修改、查询 节点的删除
在二叉树中，我们规定，如果要删除某一个节点，那么该节点以及该节点下方的所有节点也被一并删除，假如我们删除1号节点，那么3和4也被一同删除，于是我们可以这样来实现。
由于要获取节点，这个函数要写到类里面。
public int deleteUserNodeByPreOrder(int userId) {if (this.left != null) {if (this.left.userId == userId) {this.left = null;return 1;}//递归左节点int i = this.left.deleteUserNodeByPreOrder(userId);//若i已经为1，则证明删除成功了，继续返回if (i == 1) {return 1;}}if (this.right != null) {if (this.right.userId == userId) {this.right = null;return 1;}//递归右节点int i = this.right.deleteUserNodeByPreOrder(userId);if (i == 1) {return 1;}}return 0;}节点的修改
同理，我们可以根据节点的id来对节点进行修改，该函数要写入类。
public int updateUserNodeByPreOrder (UserNode userNode) {if (this.left != null) {if (this.left.userId == userNode.userId) {userNode.left = this.left.left;userNode.right = this.left.right;this.left = userNode;return 1;} else {//遍历左节点，如果修改成功则返回1。int i = this.left.updateUserNodeByPreOrder(userNode);if (i == 1) {return 1;}}}if (this.right != null) {if (this.right.userId == userNode.userId) {userNode.left = this.right.left;userNode.right = this.right.right;this.right = userNode;return 1;} else {//递归右节点int i = this.right.updateUserNodeByPreOrder(userNode);if (i == 1) {return 1;}}}return 0;}节点的获取
我们可以通过遍历来获取节点的信息，在这里我们使用前序遍历的方式来查找节点，如果找到了节点就直接返回结果，没有找到节点就继续向下递归。
public UserNode getUserNodeByPreOrder(int userId) {if (this.userId == userId) {return this;} else {if (this.left != null) {UserNode userNode = this.left.getUserNodeByPreOrder(userId);if (userNode != null) {return userNode;}}if (this.right != null) {UserNode userNode = this.right.getUserNodeByPreOrder(userId);if (userNode != null) {return userNode;}}}return null;}总结
总代码如下：
public class Day_二叉树 {public static void main(String[] args) {UserNode userNode0 = new UserNode("张零", 0);UserNode userNode1 = new UserNode("李一", 1);UserNode userNode2 = new UserNode("王二", 2);UserNode userNode3 = new UserNode("杨三", 3);UserNode userNode4 = new UserNode("胡四", 4);UserNode userNode5 = new UserNode("邓五", 5);UserNode userNode6 = new UserNode("吕六", 6);userNode0.left = userNode1;userNode0.right = userNode2;userNode1.left = userNode3;userNode1.right = userNode4;userNode2.left = userNode5;userNode2.right = userNode6;BinaryTree binaryTree = new BinaryTree(userNode0);binaryTree.postOrder(binaryTree.root);}
}
class BinaryTree {UserNode root;public BinaryTree(UserNode root) {this.root = root;}//从UserNode中调用方法public UserNode getUserNodeByPreOrder(int userId) {return root.getUserNodeByPreOrder(userId);}public int deleteUserNodeByPreOrder(int userId) {return root.deleteUserNodeByPreOrder(userId);}public int updateUserNodeByPreOrder (UserNode userNode) {if (root.userId == userNode.userId) {userNode.left = root.left;userNode.right = root.right;root = userNode;return 1;}return root.updateUserNodeByPreOrder(userNode);}public void preOrder (UserNode node) {System.out.println(node);if (node.left != null) {this.preOrder(node.left);}if (node.right != null) {this.preOrder(node.right);}}public void midOrder (UserNode node) {if (node.left != null) {this.midOrder(node.left);}System.out.println(node);if (node.right != null) {this.midOrder(node.right);}}public void postOrder (UserNode node) {if (node.left != null) {this.postOrder(node.left);}if (node.right != null) {this.postOrder(node.right);}System.out.println(node);}
}class UserNode {String userName;int userId;UserNode left;UserNode right;public UserNode(String userName , int userId) {this.userName = userName;this.userId = userId;}public int deleteUserNodeByPreOrder(int userId) {if (this.left != null) {if (this.left.userId == userId) {this.left = null;return 1;}int i = this.left.deleteUserNodeByPreOrder(userId);if (i == 1) {return 1;}}if (this.right != null) {if (this.right.userId == userId) {this.right = null;return 1;}int i = this.right.deleteUserNodeByPreOrder(userId);if (i == 1) {return 1;}}return 0;}public UserNode getUserNodeByPreOrder(int userId) {if (this.userId == userId) {return this;} else {if (this.left != null) {UserNode userNode = this.left.getUserNodeByPreOrder(userId);if (userNode != null) {return userNode;}}if (this.right != null) {UserNode userNode = this.right.getUserNodeByPreOrder(userId);if (userNode != null) {return userNode;}}}return null;}public int updateUserNodeByPreOrder (UserNode userNode) {if (this.left != null) {if (this.left.userId == userNode.userId) {userNode.left = this.left.left;userNode.right = this.left.right;this.left = userNode;return 1;} else {int i = this.left.updateUserNodeByPreOrder(userNode);if (i == 1) {return 1;}}}if (this.right != null) {if (this.right.userId == userNode.userId) {userNode.left = this.right.left;userNode.right = this.right.right;this.right = userNode;return 1;} else {int i = this.right.updateUserNodeByPreOrder(userNode);if (i == 1) {return 1;}}}return 0;}@Overridepublic String toString() {return "UserNode{" +"userName='" + userName + '\'' +", userId='" + userId + '\'' +'}';}
}二叉树是一种非常常见的数据结构，利用二叉树可以解决很多问题，如堆排序等问题，可以更有效地解决更多问题。
