对于遍历不过多的赘述,关于查找有关的思想,关键是如何实现查找的顺序以及结果的回传;附代码
1 package dataSrtuct; 2 3 public class BinaryTreeDemo { 4 public static void main(String[] args) { 5 BinaryTree binaryTree=new BinaryTree(); 6 TreeNode root=new TreeNode(1,"MLQ"); 7 TreeNode node1=new TreeNode(2,"ZBB"); 8 TreeNode node2=new TreeNode(3,"MXP"); 9 TreeNode node3=new TreeNode(4,"MYP"); 10 root.setLeftNext(node1); 11 root.setRightNext(node2); 12 node2.setRightNext(node3); 13 binaryTree.setRoot(root); 14 System.out.println("遍历结果1为"); 15 binaryTree.preOrder(); 16 System.out.println("遍历结果2为"); 17 binaryTree.infixOrder(); 18 System.out.println("遍历结果3为"); 19 binaryTree.postOrder(); 20 System.out.println("查找结果1为"); 21 System.out.println(binaryTree.preOrderSearch(3)+"查找的次数为:"+TreeNode.countPre); 22 System.out.println("查找结果2为"); 23 System.out.println(binaryTree.infixOrderSearch(3)+"查找的次数为:"+TreeNode.countInfix); 24 System.out.println("查找结果3为"); 25 System.out.println(binaryTree.postOrderSearch(3)+"查找的次数为:"+TreeNode.countPost); 26 } 27 28 } 29 //二叉树 30 class BinaryTree{ 31 private TreeNode root; 32 33 public TreeNode getRoot() { 34 return root; 35 } 36 37 public void setRoot(TreeNode root) { 38 this.root = root; 39 } 40 //先序遍历 41 public void preOrder(){ 42 if (this.root!=null) 43 this.root.preOrder(); 44 else 45 System.out.println("二叉树为空,不能遍历"); 46 } 47 ///中序遍历 48 public void infixOrder(){ 49 if (this.root!=null) 50 this.root.infixOrder(); 51 else 52 System.out.println("二叉树为空,不能遍历"); 53 } 54 //后序遍历 55 public void postOrder(){ 56 if (this.root!=null) 57 this.root.postOrder(); 58 else 59 System.out.println("二叉树为空,不能遍历"); 60 } 61 //前、后、中序查找 62 //先序查找 63 public TreeNode preOrderSearch(int val){ 64 if (this.root!=null) 65 return this.root.preOrderSearch(val); 66 else { 67 System.out.println("二叉树为空,不能遍历"); 68 return null; 69 } 70 } 71 //中序查找 72 public TreeNode infixOrderSearch(int val){ 73 if (this.root!=null) 74 return this.root.infixOrderSearch(val); 75 else { 76 System.out.println("二叉树为空,不能遍历"); 77 return null; 78 } 79 } 80 //后序查找 81 public TreeNode postOrderSearch(int val){ 82 if (this.root!=null) 83 return this.root.postOrderSearch(val); 84 else { 85 System.out.println("二叉树为空,不能遍历"); 86 return null; 87 } 88 89 } 90 } 91 //树节点 92 class TreeNode{ 93 private int val; 94 private String name; 95 private TreeNode leftNext; 96 private TreeNode rightNext; 97 public static int countPre; 98 public static int countInfix; 99 public static int countPost; 100 static { 101 countPre=0; 102 countInfix=0; 103 countPost=0; 104 } 105 106 public TreeNode(int val, String name) { 107 this.val = val; 108 this.name = name; 109 } 110 111 public int getVal() { 112 return val; 113 } 114 115 public void setVal(int val) { 116 this.val = val; 117 } 118 119 public String getName() { 120 return name; 121 } 122 123 public void setName(String name) { 124 this.name = name; 125 } 126 127 public TreeNode getLeftNext() { 128 return leftNext; 129 } 130 131 public void setLeftNext(TreeNode leftNext) { 132 this.leftNext = leftNext; 133 } 134 135 public TreeNode getRightNext() { 136 return rightNext; 137 } 138 139 public void setRightNext(TreeNode rightNext) { 140 this.rightNext = rightNext; 141 } 142 143 @Override 144 public String toString() { 145 return "TreeNode{" + 146 "val=" + val + 147 ", name='" + name + '\'' + 148 '}'; 149 } 150 //先序查找 151 public TreeNode preOrderSearch(int val){ 152 TreeNode.countPre++; 153 if (this.val==val) 154 return this; 155 TreeNode tempNode=null; 156 if (this.leftNext!=null) 157 tempNode=this.leftNext.preOrderSearch(val); 158 if (tempNode!=null) 159 return tempNode; 160 if (this.rightNext!=null) 161 tempNode= this.rightNext.preOrderSearch(val); 162 return tempNode; 163 } 164 //中序查找 165 public TreeNode infixOrderSearch(int val){ 166 TreeNode.countInfix++; 167 TreeNode tempNode=null; 168 if (this.leftNext!=null) 169 tempNode=this.leftNext.infixOrderSearch(val); 170 if (tempNode!=null) 171 return tempNode; 172 if (this.val==val) 173 return this; 174 if (this.rightNext!=null) 175 tempNode=this.rightNext.infixOrderSearch(val); 176 return tempNode; 177 } 178 //后序查找 179 public TreeNode postOrderSearch(int val){ 180 TreeNode.countPost++; 181 TreeNode tempNode=null; 182 if (this.leftNext!=null) 183 tempNode=this.leftNext.postOrderSearch(val); 184 if (tempNode!=null) 185 return tempNode; 186 if (this.rightNext!=null) 187 tempNode=this.rightNext.postOrderSearch(val); 188 if (tempNode!=null) 189 return tempNode; 190 if (this.val==val) 191 return this; 192 return tempNode; 193 194 } 195 //先序遍历 196 public void preOrder(){ 197 System.out.println(this); 198 if (this.leftNext!=null) 199 this.leftNext.preOrder(); 200 if (this.rightNext!=null) 201 this.rightNext.preOrder(); 202 } 203 ///中序遍历 204 public void infixOrder(){ 205 if (this.leftNext!=null) 206 this.leftNext.infixOrder(); 207 System.out.println(this); 208 if (this.rightNext!=null) 209 this.rightNext.infixOrder(); 210 } 211 //后序遍历 212 public void postOrder(){ 213 if (this.leftNext!=null) 214 this.leftNext.postOrder(); 215 if (this.rightNext!=null) 216 this.rightNext.postOrder(); 217 System.out.println(this); 218 } 219 }
标签:遍历,TreeNode,val,return,二叉树,Java,null,root,public From: https://www.cnblogs.com/Mexcellent/p/17311137.html