首页 > 代码库 > 排序二叉树
排序二叉树
属性：
①若它的左子树不为空，则左子树上所有节点的值均小于它的根节点的值。
②若它的右子树不为空，则右子树上所有节点的值均大于它的根节点的值。
③它的左、右子树也都是排序二叉树。
添加操作：
当根节点为空时，添加进的节点作为根节点。然后每次添加节点时，都从根节点过滤，以根节点作为当前节点，如果新节点大于当前节点，则走当前节点的右子节点分支，如果新节点小于当前节点，则走当前节点的左子节点分支。然后再用右子节点或左子节点作为当前节点与新加节点比较，如果新加节点大，则当前节点的右子节点，如果新加节点小，则当前节点的左子节点。依次类推知道左子树或右子树为null时，将该新节点添加在这里。
1 package tree; 2 import java.util.ArrayDeque; 3 import java.util.ArrayList; 4 import java.util.List; 5 import java.util.Queue; 6 public class SortedBinaryTree<T extends Comparable> { 7 8 public static class Node<E>{ 9 E data; 10 Node<E> parent; 11 Node<E> left; 12 Node<E> right; 13 14 public Node() {} 15 public Node(E data){ 16 this.data=http://www.mamicode.com/data; 17 } 18 public Node(E data,Node<E> left,Node<E> right){ 19 this.data=http://www.mamicode.com/data; 20 this.left=left; 21 this.right=right; 22 } 23 public Node(E data,Node<E> parent,Node<E> left,Node<E> right){ 24 this.data=http://www.mamicode.com/data; 25 this.parent=parent; 26 this.left=left; 27 this.right=right; 28 } 29 public boolean equals(Object obj){ 30 if(this==obj){ 31 return true; 32 }else if(this.getClass()==obj.getClass()){ 33 Node<E> nodeObj=(Node<E>) obj; 34 return nodeObj.data.equals(data) && nodeObj.left==left && nodeObj.right==right; 35 } 36 return false; 37 } 38 public String toString(){ 39 return "[data="http://www.mamicode.com/+data+"]"; 40 } 41 } 42 private Node<T> root; 43 public SortedBinaryTree() { 44 root=null; 45 } 46 public SortedBinaryTree(T data){ 47 root=new Node<T>(data); 48 } 49 50 //往排序二叉树中添加节点 51 public void add(T element){ 52 Node<T> node=new Node<T>(element); 53 if(root==null){ 54 root=node; 55 }else { 56 Node<T> current=root; 57 Node<T> parent=null; 58 int cmp=0; 59 //循环找到可以被添加到的位置。 60 while(current!=null){ 61 parent=current; 62 cmp=element.compareTo(current.data); 63 //如果新节点大于当前节点 64 if(cmp>0){ 65 //以右子节点作为当前节点 66 current=current.right; 67 }else { 68 current=current.left; 69 } 70 } 71 //如果新节点大于父节点的值 72 if(cmp>0){ 73 //新节点作为父节点的右子节点。 74 parent.right=node; 75 }else { 76 parent.left=node; 77 } 78 node.parent=parent; 79 } 80 } 81 //删除节点 82 public void remove(T data){ 83 //获取要删除的节点 84 Node<T> node=getNode(data); 85 if(node==null){ 86 return; 87 } 88 boolean isLeftOfParent=isLeft(node); 89 //如果删除的是叶子节点 90 if(node.left==null && node.right==null){ 91 //如果该叶子节点就是根节点,即该树中只有一个根节点 92 if(node==root){ 93 root=null; 94 }else if(isLeftOfParent){//被删除的节点是父节点的左子节点。 95 node.parent.left=null;//将被删除的节点的父节点的左子节点指针设为null 96 }else { 97 node.parent.right=null; 98 } 99 //将被删除节点的父节点指针设为null100 node.parent=null;101 }else if(node.left!=null && node.right==null){//左子树不为空，右子节点为空102 //被删除节点是根节点103 if(root==node){104 root=node.left;105 }else if(isLeftOfParent){106 node.parent.left=node.left; 107 }else {108 node.parent.right=node.left; 109 }110 node.parent=null;111 }else if(node.left==null && node.right!=null){112 if(node==root){113 root=node.right;114 }else if(isLeftOfParent){115 node.parent.left=node.right;116 }else {117 node.parent.right=node.right;118 }119 node.parent=null;120 }else {121 Node<T> leftMaxNode=node.left;122 while(leftMaxNode.right!=null){123 leftMaxNode=leftMaxNode.right;124 }125 if(node!=root){ 126 leftMaxNode.parent=node.parent;127 if(isLeftOfParent){//如果被删的节点是其父节点的左子节点，则重构其父节点的左子节点为leftMaxNode节点128 node.parent.left=leftMaxNode;129 }else {//如果被删的节点是其父节点的右子节点，则重构其父节点的右子节点为leftMaxNode节点130 node.parent.right=leftMaxNode;131 }132 }else {//如果删除的节点就是根节点，则重构根节点为leftMaxNode，因为一颗树必须有根节点，以如中根节点分析133 root=leftMaxNode;134 }135 if(leftMaxNode!=node.left){//>必须判断<以图中节点10分析。136 //如果leftMaxNode节点就是其根结点的左子节点，就不能有下面的语句，否则会出现死循环137 leftMaxNode.left=node.left;138 //如果leftMaxNode节点就是其根结点的左子节点，就不能有下面的语句，否则删除其他的数据-->leftMaxNode.parent.right。139 leftMaxNode.parent.right=null;140 } 141 142 leftMaxNode.right=node.right; 143 node.parent=node.left=node.right=null;144 }145 }146 private boolean isLeft(Node<T> node) {147 if(node==root){148 return false;149 }else {150 return node==node.parent.left;151 } 152 }153 public Node<T> getNode(T data) {154 Node<T> node=root;155 while(node!=null){156 int comp=data.compareTo(node.data);157 if(comp>0){158 node=node.right;159 }else if(comp<0){160 node=node.left;161 }else {162 return node;163 }164 }165 return null;166 }167 //广度优先遍历168 public List<Node<T>> breadthFirst(){169 Queue<Node<T>> queue=new ArrayDeque<Node<T>>();170 List<Node<T>> list=new ArrayList<Node<T>>();171 Node<T> tmp;172 if(root!=null){173 queue.offer(root);174 }175 while(!queue.isEmpty()){176 list.add(queue.peek());177 tmp=queue.poll();178 if(tmp.left!=null){179 queue.offer(tmp.left);180 }181 if(tmp.right!=null){182 queue.offer(tmp.right);183 }184 }185 return list;186 }187 //中序遍历188 public List<Node> midIterator(){189 return midIterator(root);190 }191 private List<Node> midIterator(Node root) {192 List<Node> list=new ArrayList<Node>();193 if(root==null){194 return null;195 }else{196 if(root.left!=null){197 list.addAll(midIterator(root.left));198 }199 list.add(root);200 if(root.right!=null){201 list.addAll(midIterator(root.right));202 }203 return list;204 }205 }206 }
测试：
1 public static void main(String[] args) { 2 SortedBinaryTree<Integer> sortedBinaryTree=new SortedBinaryTree<Integer>(); 3 sortedBinaryTree.add(5); 4 sortedBinaryTree.add(20); 5 sortedBinaryTree.add(10); 6 sortedBinaryTree.add(3); 7 sortedBinaryTree.add(8); 8 sortedBinaryTree.add(15); 9 sortedBinaryTree.add(30);10 System.out.println(sortedBinaryTree.breadthFirst());11 System.out.println(sortedBinaryTree.midIterator());12 sortedBinaryTree.remove(20);13 System.out.println(sortedBinaryTree.breadthFirst());14 System.out.println(sortedBinaryTree.midIterator());15 }
排序二叉树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。