首页 > 代码库 > 二叉树

二叉树

2024-09-23 20:39:50   203人阅读

背景：
  • 有序数组使用二分查找法，需要的时间为 O(log n)，同时可以迅速遍历，但是插入和删除操作太慢（找到后，把大的全部后移，对应删除则是左移）
  • 链表的插入和删除操作都很快，时间复杂度是最小的 O(1)，但是查找需要从头开始，费时 O(N)，即使使用有序链表，在访问任意项时也不能加快速度

“树”是一种有着“链表那样快速的插入和删除”和“有序数组那样快速的查找”的能力的数据结构。

下面是个人写的“二叉查找树（Binary Search Tree）”的实现（不允许重复关键值的元素）：
  1. /**
  2.  * 节点类
  3.  * 
  4.  * @author Frank
  5.  *
  6.  */
  7. public class TreeNode {
  8. 	int keyData;// 关键值（可能还有别的非关键数据，这里省略）
  9. 	TreeNode leftChild;// 左子节点
  10. 	TreeNode rightChild;// 右子节点
  12. 	public TreeNode(int keyData) {
  13. 		super();
  14. 		this.keyData = keyData;
  15. 	}
  17. 	/**
  18. 	 * 显示该节点信息
  19. 	 */
  20. 	public void display() {
  21. 		System.out.println(
  22. 				"TreeNode [keyData="http://www.mamicode.com/ + keyData + ", leftChild=" + leftChild + ", rightChild=" + rightChild + "]");
  23. 	}
  25. 	@Override
  26. 	public String toString() {
  27. 		return "TreeNode [keyData="http://www.mamicode.com/ + keyData + "]";
  28. 	}
  30. }

  1. import java.util.HashMap;
  2. import java.util.Iterator;
  3. import java.util.Set;
  5. /**
  6.  * 二叉查找树
  7.  * 
  8.  * @author Frank
  9.  *
  10.  */
  11. public class Tree {
  12. 	TreeNode root;// 根节点
  13. 	private TreeNode parent;// 父节点
  15. 	public Tree(TreeNode root) {
  16. 		super();
  17. 		this.root = root;
  18. 	}
  20. 	/**
  21. 	 * 以关键值查找节点是否存在
  22. 	 * 
  23. 	 * @param keyData
  24. 	 *            节点关键值
  25. 	 * @return 若该树包含关键值对应的 Node，返回 true
  26. 	 */
  27. 	public boolean findNode(int keyData) {
  28. 		TreeNode current = root;// 当前节点
  29. 		while (current != null) {
  30. 			if (current.keyData == keyData)
  31. 				return true;// 找到了
  32. 			if (current.keyData > keyData) // 往左遍历
  33. 				current = current.leftChild;
  34. 			if (current.keyData < keyData) // 往右遍历
  35. 				current = current.rightChild;
  36. 		}
  37. 		return false;// 未找到
  38. 	}
  40. 	/**
  41. 	 * 将节点插入当前树
  42. 	 * 
  43. 	 * @param node
  44. 	 *            新插入的节点
  45. 	 */
  46. 	public void insert(TreeNode node) {
  47. 		if (!this.isEmpty()) {
  48. 			boolean isLeftChild = true;
  49. 			int keyData = node.keyData;
  50. 			TreeNode current = root;// 当前节点
  51. 			parent = null;
  52. 			while (current != null) {
  53. 				parent = current;
  54. 				if (keyData == current.keyData)
  55. 					return;// 关键值一样则不插入
  56. 				current = (keyData < current.keyData) ? (current.leftChild) : (current.rightChild);
  57. 				isLeftChild = (keyData < parent.keyData) ? true : false;
  58. 			}
  59. 			if (isLeftChild) {
  60. 				parent.leftChild = node;
  61. 			} else {
  62. 				parent.rightChild = node;
  63. 			}
  64. 		}
  65. 	}
  67. 	/**
  68. 	 * 将集合中的所有节点插入当前树
  69. 	 * 
  70. 	 * @param node
  71. 	 *            新插入的节点
  72. 	 */
  73. 	public void insert(Set<TreeNode> nodeSet) {
  74. 		Iterator<TreeNode> iterator = nodeSet.iterator();
  75. 		while (iterator.hasNext()) {
  76. 			insert(iterator.next());
  77. 		}
  78. 	}
  80. 	/**
  81. 	 * 判断当前树是否为空
  82. 	 * 
  83. 	 * @return 若为空，返回 true
  84. 	 */
  85. 	public boolean isEmpty() {
  86. 		return root == null;
  87. 	}
  89. 	// 通过递归实现中序遍历输出
  90. 	private void getOrder(TreeNode localRoot) {
  91. 		if (localRoot != null) {
  92. 			getOrder(localRoot.leftChild);
  93. 			System.out.print(localRoot.keyData + " ");
  94. 			getOrder(localRoot.rightChild);
  95. 		}
  96. 	}
  98. 	/**
  99. 	 * 中序遍历指定的子树，若指定的节点并不是本树的节点（以关键值为标准，可能出现非关键值不一样的正常遍历），则不输出任何值
  100. 	 * 
  101. 	 * @param localRoot
  102. 	 *            指定节点对象，若为 root 节点则遍历当前树
  103. 	 */
  104. 	public void inOrder(TreeNode localRoot) {
  105. 		if (localRoot != null && findNode(localRoot.keyData)) {
  106. 			TreeNode current = getNode(localRoot.keyData);
  107. 			getOrder(current);
  108. 			System.out.println();
  109. 		}
  110. 	}
  112. 	/**
  113. 	 * 获取指定关键值对应的节点，该节点需存在于本树中
  114. 	 * 
  115. 	 * @param keyData
  116. 	 *            节点关键值
  117. 	 * @return 若存在这样的节点则返回此节点，否则返回 null
  118. 	 */
  119. 	public TreeNode getNode(int keyData) {
  120. 		TreeNode current = root;// 当前节点
  121. 		while (current != null) {
  122. 			if (current.keyData == keyData)
  123. 				return current;// 找到了
  124. 			if (current.keyData > keyData) // 往左遍历
  125. 				current = current.leftChild;
  126. 			if (current.keyData < keyData) // 往右遍历
  127. 				current = current.rightChild;
  128. 		}
  129. 		return null;// 未找到
  130. 	}
  132. 	/**
  133. 	 * 获取当前树的最小关键值节点
  134. 	 * 
  135. 	 * @return 最小关键值对应的节点，若树为空则返回 null
  136. 	 */
  137. 	public TreeNode minimum() {
  138. 		if (!this.isEmpty()) {
  139. 			parent = null;
  140. 			TreeNode minmum = root;
  141. 			while ((minmum = minmum.leftChild) != null) {
  142. 				parent = minmum;
  143. 			}
  144. 			return parent;
  145. 		}
  146. 		return null;
  147. 	}
  149. 	/**
  150. 	 * 获取当前树的最大关键值节点
  151. 	 * 
  152. 	 * @return 最大关键值对应的节点，若树为空则返回 null
  153. 	 */
  154. 	public TreeNode maximum() {
  155. 		if (!this.isEmpty()) {
  156. 			parent = null;
  157. 			TreeNode maximum = root;
  158. 			while ((maximum = maximum.rightChild) != null) {
  159. 				parent = maximum;
  160. 			}
  161. 			return parent;
  162. 		}
  163. 		return null;
  164. 	}
  166. 	/**
  167. 	 * 获取指定节点的子节点个数
  168. 	 * 
  169. 	 * @param keyData
  170. 	 *            节点关键值
  171. 	 * @return 返回拥有 keyData 关键值的节点的子节点个数，若节点不存在与本树，返回-1
  172. 	 */
  173. 	public HashMap<Integer, Boolean> numOfChildren(int keyData) {
  174. 		HashMap<Integer, Boolean> returnMap = new HashMap<Integer, Boolean>();
  175. 		if (this.isEmpty() || !findNode(keyData)) {
  176. 			returnMap.put(-1, false);
  177. 			return returnMap;
  178. 		}
  179. 		TreeNode current = root;
  180. 		parent = null;
  181. 		boolean isLeftChild = true;
  182. 		while (current != null) {
  183. 			if (keyData == current.keyData) {
  184. 				break;
  185. 			}
  186. 			parent = current;
  187. 			current = (keyData < current.keyData) ? (current.leftChild) : (current.rightChild);
  188. 			isLeftChild = (keyData < parent.keyData) ? true : false;
  189. 		}
  190. 		if (current.leftChild == null && current.rightChild == null) {
  191. 			returnMap.put(0, isLeftChild);
  192. 		} else if (current.leftChild != null && current.rightChild != null) {
  193. 			returnMap.put(2, isLeftChild);
  194. 		} else {
  195. 			returnMap.put(1, isLeftChild);
  196. 		}
  197. 		return returnMap;
  198. 	}
  200. 	/**
  201. 	 * 删除指定关键值对应的节点，若为非叶子节点，当直接子节点仅有一个时，由该子节点继承，若直接子节点为两个，则由后继节点继承，各子节点保持规律不变，
  202. 	 * 即左子节点小于父节点，父节点小于右子节点
  203. 	 * 
  204. 	 * @param keyData
  205. 	 *            叶子节点的关键值
  206. 	 * @return 删除成功返回 true，否则返回 false
  207. 	 */
  208. 	public boolean delete(int keyData) {
  209. 		HashMap<Integer, Boolean> map = numOfChildren(keyData);
  210. 		boolean isLeftChild = map.values().iterator().next();
  211. 		switch (map.keySet().iterator().next()) {
  212. 		case -1:
  213. 			return false;
  214. 		case 0:
  215. 			if (isLeftChild) {
  216. 				parent.leftChild = null;
  217. 			} else {
  218. 				parent.rightChild = null;
  219. 			}
  220. 			return true;
  221. 		case 1:
  222. 			if (isLeftChild) {
  223. 				TreeNode current = parent.leftChild;
  224. 				parent.leftChild = (current.leftChild == null) ? current.rightChild : parent.leftChild.leftChild;
  225. 			} else {
  226. 				TreeNode current = parent.rightChild;
  227. 				parent.rightChild = (current.leftChild == null) ? current.rightChild : parent.leftChild.leftChild;
  228. 			}
  229. 			return true;
  230. 		case 2:
  231. 			TreeNode successorNode = getSuccessor(new TreeNode(keyData));// 该节点的后继节点，即将替换被删除节点
  232. 			TreeNode delNode = null;// 将要删除的节点
  234. 			if (isLeftChild) {// 将要删除的节点是其父节点的左子节点
  235. 				if (parent == null) {// 删除整个树
  236. 					root = null;
  237. 					return true;
  238. 				}
  239. 				delNode = parent.leftChild;
  240. 				if (delNode.rightChild == null) {
  241. 					break;
  242. 				} else if (successorNode.keyData == delNode.rightChild.keyData) {// 后继节点是delNode的右子节点
  243. 					parent.leftChild = successorNode;// 1.将要删除的节点替换为后继节点
  244. 					successorNode.leftChild = delNode.leftChild;// 2.将后继节点的左子节点替换为将要删除的节点的左子节点
  245. 				} else {// 后继节点是delNode的右子节点的左后代
  246. 					TreeNode successorParent = getParent(successorNode);// 获取后继节点的父节点，后继节点一定是这个父节点的左子节点
  247. 					parent = getParent(delNode);
  248. 					successorParent.leftChild = successorNode.rightChild;// 1.将后继节点的父节点的左子节点替换为后继节点的右子节点
  249. 					successorNode.rightChild = delNode.rightChild;// 2.将后继节点的右子节点换为将要删除的节点的右子节点
  250. 					parent.leftChild = successorNode;// 3.将要删除的节点替换为后继节点
  251. 					successorNode.leftChild = delNode.leftChild;// 4.将后继节点的左子节点替换为将要删除的节点的左子节点
  252. 				}
  253. 			} else {// 将要删除的节点是其父节点的右子节点
  254. 				delNode = parent.rightChild;
  255. 				if (successorNode.keyData == delNode.rightChild.keyData) {// 后继节点是delNode的右子节点
  256. 					parent.rightChild = successorNode;// 1.将要删除的节点替换为后继节点
  257. 					successorNode.leftChild = delNode.leftChild;// 2.将后继节点的左子节点替换为将要删除的节点的左子节点
  258. 				} else {// 后继节点是delNode的右子节点的左后代
  259. 					TreeNode successorParent = getParent(successorNode);// 获取后继节点的父节点，后继节点一定是这个父节点的左子节点
  260. 					parent = getParent(delNode);
  261. 					successorParent.leftChild = successorNode.rightChild;// 1.将后继节点的父节点的左子节点替换为后继节点的右子节点
  262. 					successorNode.rightChild = delNode.rightChild;// 2.将后继节点的右子节点换为将要删除的节点的右子节点
  263. 					parent.rightChild = successorNode;// 3.将要删除的节点替换为后继节点
  264. 					successorNode.leftChild = delNode.leftChild;// 4.将后继节点的左子节点替换为将要删除的节点的左子节点
  265. 				}
  266. 			}
  267. 			return true;
  268. 		}
  269. 		return false;
  270. 	}
  272. 	// 获取指定节点的父节点
  273. 	private TreeNode getParent(TreeNode node) {
  274. 		int keyData = node.keyData;
  275. 		if (this.isEmpty() || !findNode(keyData)) {
  276. 			return null;
  277. 		}
  278. 		TreeNode current = root;
  279. 		parent = null;
  280. 		while (current != null) {
  281. 			if (keyData == current.keyData) {
  282. 				break;
  283. 			}
  284. 			parent = current;
  285. 			current = (keyData < current.keyData) ? (current.leftChild) : (current.rightChild);
  286. 		}
  287. 		return parent;
  288. 	}
  290. 	/**
  291. 	 * 获取指定节点的后继节点，后继节点应为：在该节点的子节点中，关键值大于该节点关键值且最接近的那个，该方法为删除方法提供支持
  292. 	 * 
  293. 	 * @param del
  294. 	 *            将要删除的节点
  295. 	 * @return
  296. 	 */
  297. 	private TreeNode getSuccessor(TreeNode del) {
  298. 		if (this.isEmpty() || !findNode(del.keyData))
  299. 			return null;
  300. 		int keyData = del.keyData;
  301. 		TreeNode current = root;
  302. 		while (current != null) {
  303. 			if (keyData == current.keyData) {
  304. 				break;
  305. 			}
  306. 			current = (keyData < current.keyData) ? (current.leftChild) : (current.rightChild);
  307. 		}
  308. 		if (current.rightChild == null) {
  309. 			return null;// 无后继节点
  310. 		}
  311. 		TreeNode successorNode = current.rightChild;
  312. 		while (successorNode.leftChild != null) {
  313. 			successorNode = successorNode.leftChild;
  314. 		}
  315. 		return successorNode;
  316. 	}
  317. }

二叉树


联系
我们