“岁月极美，在于它必然的流逝”
“春花 秋月 夏日 冬雪”
— 三毛
一、树 & 二叉树
树是由节点和边构成，储存元素的集合。节点分根节点、父节点和子节点的概念。
如图：树深=4; 5是根节点；同样8与3的关系是父子节点关系。
二叉树binary tree，则加了“二叉”（binary），意思是在树中作区分。每个节点至多有两个子（child）,left child & right child。二叉树在很多例子中使用，比如二叉树表示算术表达式。
如图：1/8是左节点；2/3是右节点；
二、二叉搜索树 BST
顾名思义，二叉树上又加了个搜索的限制。其要求：每个节点比其左子树元素大，比其右子树元素小。
如图：每个节点比它左子树的任意节点大，而且比它右子树的任意节点小
三、BST Java实现
直接上代码，对应代码分享在 Github 主页
BinarySearchTree.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 |
package org.algorithm.tree; /* * Copyright [2015] [Jeff Lee] * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ /** * 二叉搜索树(BST)实现 * * Created by bysocket on 16/7/7. */ public class BinarySearchTree { /** * 根节点 */ public static TreeNode root; public BinarySearchTree() { this.root = null; } /** * 查找 * 树深(N) O(lgN) * 1. 从root节点开始 * 2. 比当前节点值小,则找其左节点 * 3. 比当前节点值大,则找其右节点 * 4. 与当前节点值相等,查找到返回TRUE * 5. 查找完毕未找到, * @param key * @return */ public TreeNode search (int key) { TreeNode current = root; while (current != null && key != current.value) { if (key key) { isLeftChild = true; -58129a29bec5b098321631-49"> isLeftChild = true; 树是由节点和边构成，储存元素的集合。节点分根节点、父节点和子节点的概念。
二叉树binary tree，则加了“二叉”（binary），意思是在树中作区分。每个节点至多有两个子（child）,left child & right child。二叉树在很多例子中使用，比如二叉树表示算术表达式。
二、二叉搜索树 BST顾名思义，二叉树上又加了个搜索的限制。其要求：每个节点比其左子树元素大，比其右子树元素小。
三、BST Java实现直接上代码，对应代码分享在 Github 主页
|
