无锡建设局施工许可证网站,简单的h5制作开发,公共资源交易中心上班怎么样,企业邮箱有序二叉树的相关实体类
TreeNode类
二叉树结点类#xff0c;包含三个属性#xff1a;value#xff0c;leftChild#xff0c;rightChild
有序二叉树类就包括这样一个根节点
剩下的getter和setter方法#xff0c;有参无参构造#xff0c;toString方法都是老生长谈包含三个属性valueleftChildrightChild
有序二叉树类就包括这样一个根节点
剩下的getter和setter方法有参无参构造toString方法都是老生长谈在这里略过不表
public class TreeNode {private int value;private TreeNode LeftChild;private TreeNode rightChild;public TreeNode(int value, TreeNode leftChild, TreeNode rightChild) {this.value value;LeftChild leftChild;this.rightChild rightChild;}public TreeNode() {}public int getValue() {return value;}public void setValue(int value) {this.value value;}Overridepublic String toString() {return TreeNode{ value value , LeftChild LeftChild , rightChild rightChild };}public TreeNode getLeftChild() {return LeftChild;}public void setLeftChild(TreeNode leftChild) {LeftChild leftChild;}public TreeNode getRightChild() {return rightChild;}public void setRightChild(TreeNode rightChild) {this.rightChild rightChild;}
}有序二叉树类
有序二叉树只有一个属性TreeNode root
public class BinarySearchTree {private TreeNode root;public TreeNode getRoot() {return root;}public void setRoot(TreeNode root) {this.root root;}}现在我们开始有序二叉树的CURD讲解
insert有序二叉树的结点插入
比结点value值大放右边反之放左边
注意结点的遍历循环的终止条件
这个方法要放到BinarySearchTree实体类当中作为成员方法 // 插入public void insert(int value) {// 创建新结点TreeNode newNode new TreeNode();newNode.setValue(value);// 若根节点为null则新插入的结点就是根节点if (root null) {root newNode;return;}// 根节点不为null// index拷贝root作为查询指针TreeNode index root;// pre作为index的parent存在TreeNode pre null;while (index ! null) {if (value index.getValue()) {pre index;index index.getRightChild();} else {pre index;index index.getLeftChild();}}// 此时pre指针指向的位置就是应该插入的位置比较大小if (value pre.getValue()) {pre.setRightChild(newNode);} else {pre.setLeftChild(newNode);}}demo
public class TreeTest {public static void main(String[] args) {BinarySearchTree tree new BinarySearchTree();tree.setRoot(new TreeNode(14, null, null));tree.insert(5);tree.insert(20);tree.insert(4);tree.insert(8);tree.insert(7);tree.insert(9);tree.insert(17);tree.insert(22);tree.insert(15);tree.insert(19);System.out.println(tree.getRoot());}
}输出结果
query有序二叉树的查询
遍历查询
时间复杂度O(n)其实就是全部结点都访问一遍来查询
二叉树的遍历
根据遍历方式优先级的不同可以分为深度优先遍历DFS和广度优先遍历BFS
深度优先遍历
先序遍历根左右DLR中序遍历左根右LDR和后序遍历左右根LRD
以上三种遍历是深度优先遍历的三种形式他们都是深度优先的
这里的D是data的意思理解成父节点即可
这三种遍历基本都是使用递归完成代码清晰而且很好理解使用非递归的方式循环栈也可以在这里不做展示
先序遍历 public void beforeSearch(TreeNode treeNode) { // DLR// 根左右// 先访问根节点打印if (treeNode null) {return;}// 打印根节点System.out.println(treeNode.getValue());// 再访问到最深的左结点不打印beforeSearch(treeNode.getLeftChild());// 最后访问到最深的右结点不打印beforeSearch(treeNode.getRightChild());}demo
public class TreeTest {public static void main(String[] args) {BinarySearchTree tree new BinarySearchTree();tree.setRoot(new TreeNode(14, null, null));tree.insert(5);tree.insert(20);tree.insert(4);tree.insert(8);tree.insert(7);tree.insert(9);tree.insert(17);tree.insert(22);tree.insert(15);tree.insert(19);System.out.println();tree.beforeSearch(tree.getRoot());}
}运行结果
中序遍历 public void middleSearch(TreeNode treeNode) {// LDR// 左根右if (treeNode null) {return;}// 只有碰到左结点才会打印middleSearch(treeNode.getLeftChild());System.out.println(treeNode.getValue());middleSearch(treeNode.getRightChild());}demo
public class TreeTest {public static void main(String[] args) {BinarySearchTree tree new BinarySearchTree();tree.setRoot(new TreeNode(14, null, null));tree.insert(5);tree.insert(20);tree.insert(4);tree.insert(8);tree.insert(7);tree.insert(9);tree.insert(17);tree.insert(22);tree.insert(15);tree.insert(19);System.out.println();tree.middleSearch(tree.getRoot());}
}运行结果 我们可以发现有序二叉树中序遍历的结果实际上就是有序二叉树从小到大排列的结果
后序遍历 public void afterSearch(TreeNode treeNode) {// LRD//左右根if (treeNode null) {return;}afterSearch(treeNode.getLeftChild());afterSearch(treeNode.getRightChild());System.out.println(treeNode.getValue());}demo
public class TreeTest {public static void main(String[] args) {BinarySearchTree tree new BinarySearchTree();tree.setRoot(new TreeNode(14, null, null));tree.insert(5);tree.insert(20);tree.insert(4);tree.insert(8);tree.insert(7);tree.insert(9);tree.insert(17);tree.insert(22);tree.insert(15);tree.insert(19);System.out.println();tree.afterSearch(tree.getRoot());}
} 广度优秀遍历BFS
BFSBreadthFirstSearch,广度优先遍历, 需要队列来辅助实现
队列的存取特点与栈相反先进先出FIFO
public void bfs(TreeNode treeNode) {// 定义队列LinkedListTreeNode queue new LinkedList();// 树为空直接返回if (treeNode null) {return;}// 首先将根节点放入队列queue.add(treeNode);while (!queue.isEmpty()) {// 队列末尾节点出列treeNode queue.pop();System.out.println(treeNode.getValue());// 左右结点放入队列if (treeNode.getLeftChild() ! null) {queue.add(treeNode.getLeftChild());}if (treeNode.getRightChild() ! null) {queue.add(treeNode.getRightChild());}}}运行结果
二分查询
时间复杂度最好O(logn)前提是二叉树有序而且相对平衡否则会退化成单链表
没什么可说的比当前结点值大就向右遍历反之则向左遍历 // 二分查找public TreeNode binarySearch(TreeNode treeNode, int val) {// 复制根节点指针 TreeNode index treeNode;while (index ! null) {if (val index.getValue()) {System.out.println(val 找到了);return index; } else if (val index.getValue()) {index index.getRightChild();} else if (val index.getValue()) {index index.getLeftChild();}}return null;}demo
public class TreeTest {public static void main(String[] args) {BinarySearchTree tree new BinarySearchTree();tree.setRoot(new TreeNode(14, null, null));tree.insert(5);tree.insert(20);tree.insert(4);tree.insert(8);tree.insert(7);tree.insert(9);tree.insert(17);tree.insert(22);tree.insert(15);tree.insert(19);
// 二分查找System.out.println(tree.binarySearch(tree.getRoot(), 15));}
}运行结果
update有序二叉树的编辑
有序二叉树无法直接编辑因为编辑前后要保证有序二叉树的性质不变
所以编辑变成了删除插入
delete有序二叉树的删除
有序二叉树的删除操做很复杂我们不是直接删除找到的结点而是将其与叶子结点交换然后删除交换后的叶子结点
如果是根节点不允许删除 如果是叶子结点直接删除 如果是中间的结点就需要交换删除
这里的交换也是大有讲究
如图所示
假设要删除结点8我们需要找一个结点与结点8交换然后将交换后的结点删除要找哪个结点呢
我们需要明白结点8的性质比5大比14小我们需要重新找到一个这样的结点来替换结点8
比14小好说只要从根节点的左子树部分找即可
比5大要怎么满足
显然要从结点8的右子树去寻找右子树的每一个结点都比8大所以肯定也比5大
但是具体是哪一个呢
我们发现这样的结点交换之后依然需要满足有序二叉树的性质如果交换的不是叶子结点那么后续还需要新的交换
如果交换叶子节点那么交换就会变得非常简单
结论
要删除的结点是父节点的左孩子时就要去左孩子所在的左子树中寻找最右叶子结点去替换要删除结点如果左子树不存在右孩子比如只有左孩子则直接将祖孙连接 要删除的结点是父节点的右孩子时就要去右孩子所在的右子树中寻找最左叶子结点去替换要删除结点如果右子树不存在左孩子比如只有右孩子则直接将祖孙连接
代码
// 删除: 根节点不是叶子结点的情况下不允许删除/删除叶子结点/其他结点的删除// 1. 先遍历找到结点位置// 2. 然后判断是否存在父节点// 3. 确定要删除的结点是左子树还是右子树// 4. 根据第三步的情况删除左子树则parent.setLeftChild(null);右子树则parent.setRightChild(null)public void delete(TreeNode treeNode, int val) {// 为空直接返回if (treeNode null) {return;}// 指针拷贝TreeNode index treeNode;TreeNode parent null;// 查询要删除的结点while (index ! null) {if (val index.getValue()) {System.out.println(val 找到了);break;} else if (val index.getValue()) {parent index;index index.getRightChild();} else if (val index.getValue()) {parent index;index index.getLeftChild();}}// 找不到要删除的结点直接返回if (index null) {System.out.println(有序二叉树中无值为 val 的结点);return;}// 要删除的结点是根节点直接返回if (parent null) {System.out.println(根节点不允许删除);return;}// 如果index是parent的左子树那么就去index子树当中搜索最右结点最大结点若index是parent的右子树就去找index子树中最左结点最小结点// 跳出循环后index指向要删除的结点parent指向删除结点的父节点// 分情况讨论// 情况1index是叶子结点直接删除if (index.getRightChild() null index.getLeftChild() null) {parent.setLeftChild(null);return;}// 判断要删除结点的类型左孩子还是右孩子 if (index.getValue() parent.getValue()) {// 情况2index不是叶子节点但是右子树为空祖孙连接if (index.getRightChild() null) {parent.setLeftChild(index.getLeftChild());return;}// 情况3index不是叶子节点,右子树不为空遍历查询最右结点// 指针拷贝标记叶子节点和叶子结点的父节点TreeNode query index;TreeNode queryParent parent;while (query.getRightChild() ! null) {// 查询最右结点queryParent query;query query.getRightChild();}// 数值交换,删除叶子节点index.setValue(query.getValue());queryParent.setRightChild(null);} else {// 情况2index不是叶子节点但是左子树为空祖孙连接if (index.getLeftChild() null) {parent.setRightChild(index.getRightChild());}// 情况3index不是叶子节点,且左子树不为空遍历查询最左结点// 指针拷贝标记叶子节点和叶子结点的父节点TreeNode query index;TreeNode queryParent parent;while (query.getLeftChild() ! null) {// 查询最左结点queryParent query;query query.getLeftChild();}// 数值交换,删除叶子节点index.setValue(query.getValue());queryParent.setLeftChild(null);}}demo
public class TreeTest {public static void main(String[] args) {BinarySearchTree tree new BinarySearchTree();tree.setRoot(new TreeNode(14, null, null));tree.insert(5);tree.insert(20);tree.insert(4);tree.insert(8);tree.insert(7);tree.insert(9);tree.insert(17);tree.insert(22);tree.insert(15);tree.insert(19);tree.delete(tree.getRoot(), 14);tree.delete(tree.getRoot(), 100);tree.delete(tree.getRoot(), 5);System.out.println(tree.getRoot());}
}运行结果
