mixkitcom素材网站,河南网站备案代理,平衡木网站建设,大二网页设计作业文章目录 1. 基本节点2. 二叉排序树2.1 增加节点2.2 查找#xff08;就是遍历#xff09;就一起写了吧2.3 广度优先遍历2.4 删除#xff08;这个有点意思#xff09;2.5 测试样例 最后的删除#xff0c;目前我测试的是正确的
1. 基本节点
TreeNode:
class TreeNode{pri… 文章目录 1. 基本节点2. 二叉排序树2.1 增加节点2.2 查找就是遍历就一起写了吧2.3 广度优先遍历2.4 删除这个有点意思2.5 测试样例 最后的删除目前我测试的是正确的
1. 基本节点
TreeNode:
class TreeNode{private int val;TreeNode left;TreeNode right;public void setLeft(TreeNode left){this.left left;}public void setRight(TreeNode right){this.right right;}TreeNode(){}TreeNode(int val){this.val val;}public int getVal(){return this.val;}public String toStringNode(){String ans [ val this.val;if(this.left ! null){ans -left this.left.toStringNode();}if(this.right ! null){ans -right this.right.toStringNode() ];}return ans;}public void setVal(int val){this.val val;}
}2. 二叉排序树
class BinaryTree{public TreeNode root;
}里面写一些方法吧
2.1 增加节点
其实就是插入
public void insert(int val){TreeNode newNode new TreeNode(val);if(root null){root newNode;return;}TreeNode curNode root;TreeNode preNode;while(true){preNode curNode;if(newNode.getVal() curNode.getVal()){curNode curNode.right;if(curNode null){preNode.setRight(newNode);return;}}else{curNode curNode.left;if(curNode null){preNode.setLeft(newNode);return;}}}}2.2 查找就是遍历就一起写了吧
跟修改一样
public void inOrder(TreeNode root){if(root null)return;inOrder(root.left);System.out.print(root.getVal() );inOrder(root.right);}public void preOrder(TreeNode root){if(root null)return;System.out.print(root.getVal() );preOrder(root.left);preOrder(root.right);}public void HOrder(TreeNode root){if(root null)return;HOrder(root.left);HOrder(root.right);System.out.print(root.getVal() );}2.3 广度优先遍历
利用队列
// 广度优先搜索void BFS(){if(this.root null){System.out.println(BFS: null);return;}System.out.print(BFS: );QueueTreeNode queue new LinkedList();queue.add(this.root);while(!queue.isEmpty()){TreeNode cur queue.poll();System.out.print(cur.getVal() );if(cur.left ! null)queue.add(cur.left);if(cur.right ! null)queue.add(cur.right);}}2.4 删除这个有点意思
分了六类情况
目标节点是叶子节点直接删了目标节点只有一个孩子直接连接上目标节点有俩孩子 左孩子没有右孩子把目标右子树连在左孩子的右孩子上然后目标父亲那条指向左孩子右孩子没有左孩子把目标左子树连在右孩子的左孩子上然后目标父亲那条指向右孩子最坏情况了找目标节点的左孩子最右或者左孩子最左交换值删了那个被交换的孩子
// 删除节点// 获取最左最右节点public TreeNode getLR(TreeNode root){if(root null || (root.left null root.right null))return null;TreeNode ans;if(root.left ! null){if(root.left.right null)return root.left;ans root.left.right;while(ans.right ! null){ans ans.right;}// System.out.println(获取最右);return ans;}if(root.right ! null){if(root.right.left null)return root.right;ans root.right.left;while(ans.left ! null){ans ans.left;}// System.out.println(获取最左);return ans;}return null;}// 获取父节点public TreeNode getParent(TreeNode root, int val){if(root null || (root.left null root.right null) || root.getVal() val)return null;// 左孩子不等if(root.getVal() val){if(root.left ! null){if(root.left.getVal() val)return root;elsereturn getParent(root.left, val);}elsereturn null;}else{if(root.right ! null){if(root.right.getVal() val)return root;elsereturn getParent(root.right, val);}elsereturn null;}}public void delNode(int val){TreeNode parent new TreeNode(Integer.MAX_VALUE);parent.left root;delNode(val, parent, null);this.root parent.left;}public void delNode(int val, TreeNode root, TreeNode parent){if(root null)return;if(root.getVal() val){delNode(val, root.right, root);}else if(root.getVal() val){delNode(val, root.left, root);}else{ // 相等if(root.left ! null root.right null){ // 没有左孩子if(parent.left root){parent.left root.left;}else{parent.right root.left;}}else if(root.left null root.right ! null){ // 没有右孩子if(parent.left root){parent.left root.right;}else{parent.right root.right;}}else if(root.left null root.right null){ // 都是nullif(parent.left root){parent.left null;}else{parent.right null;} }else{ // 进行交换if(root.left.right null){root.left.right root.right;if(parent.left root){parent.left root.left;}else{parent.right root.left;}}else if(root.right.left null){root.right.left root.left;if(parent.left root){parent.left root.left;}else{parent.right root.left;}}else{TreeNode cur getLR(root); // 获取最左最右节点// 删除那个节点TreeNode curParent getParent(root, cur.getVal()); // 获取父节点if(curParent.getVal() cur.getVal())curParent.left null;else{curParent.right null;}root.setVal(cur.getVal()); // 设置值}}}}2.5 测试样例
public class Test2{public static void main(String[] args) {TreeNode node1 new TreeNode(1);TreeNode node2 new TreeNode(2);TreeNode node3 new TreeNode(3);TreeNode node4 new TreeNode(4);TreeNode node5 new TreeNode(5);TreeNode node6 new TreeNode(6);// 进行构建node1.setRight(node2);node1.setLeft(node3);node3.setLeft(node4);node4.setLeft(node5);node4.setRight(node6);// System.out.println(node1.toStringNode());BinaryTree b new BinaryTree();b.insert(5);b.insert(7);b.insert(4);b.insert(2);b.insert(0);b.insert(3);b.insert(8);b.insert(6);b.insert(1);// System.out.println(b.root.toStringNode());// System.out.println(b.getParent(b.root, 3).getVal());for(int i 8; i 0; i--){System.out.println(删除了 i);b.delNode(i);b.BFS();System.out.println();}// // 中序// System.out.println(中序);// // 先序// System.out.println();// System.out.println(先序);// b.preOrder(b.root);// // 后序// System.out.println();// System.out.println(后序);// b.HOrder(b.root);// // 深度System.out.println();b.BFS();}
}
