目录
前言
一、二叉树的前中后序遍历
前序遍历
中序遍历
后序遍历
二、节点的删除、修改、查询
节点的删除
节点的修改
节点的获取
总结
前言
树属于数据结构中的非线性结构 , 最常见的树就属二叉树了 。那么在二叉树中 , 如何使用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
后序遍历
【用Java谈谈二叉树的增删改查】后序遍历则是先输出左节点,再输出右节点,最后输出父节点 。
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 + '\'' +'}';}}
二叉树是一种非常常见的数据结构,利用二叉树可以解决很多问题,如堆排序等问题,可以更有效地解决更多问题 。
- 频繁使用手机导致男性生育力降30%
- 羊粪怎么发酵成有机肥,羊粪有机肥的作用
- 《侠客风云传》战斗小技巧分享攻略 侠客风云传实战作用
- 《侠客风云传》武学秘籍获得方法 侠客风云传武学有什么用
- 灵芝袍子粉的功效与作用 灵芝的功效与作用的功能与主治与用量
- 小猪拉黄白痢用什么药物治疗,是什么原因导致的
- Android-socket的基本使用,发送文字和图片以及心跳
- 鱼肝油的功效与作用及食用方法 鱼肝油的功效与作用及食用方法及禁忌
- 鱼油卵磷脂的功效与作用 鱼油卵磷脂的功效与作用有哪些?
- 伊利酸奶的功效与作用英文 伊利酸奶的功效与作用