将数列 {1, 3, 6, 8, 10, 14 } 构建成一颗二叉树.
问题分析:
1.当我们对上面的二叉树进行中序遍历时,数列为 {8, 3, 10, 1, 6, 14 }
2.但是 6, 8, 10, 14 这几个节点的 左右指针,并没有完全的利用上.
3.如果我们希望充分的利用 各个节点的左右指针, 让各个节点可以指向自己的前后节点,怎么办?
4.解决方案-线索二叉树
概念:当用二叉链表作为二叉树的存储结构时,可以很方便的找到某个结点的左右孩子;但一般情况下,无法直接找到该结点在某种遍历序列中的前驱和后继结点。所以使用线索化,利用二叉树结构链表的空指针域进行线索化。
n 个结点的二叉链表中含有 n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域,存放指向该结点在某种遍历次序下的前驱和后继结点的指针(这种附加的指针称为"线索")
这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同,线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
中序线索化二叉树并遍历
应用案例说明:将下面的二叉树,进行中序线索二叉树。中序遍历的数列为 {8, 3, 10, 1, 14, 6}
思路分析
中序遍历的结果:{8, 3, 10, 1, 14, 6}
那么线索化之后的二叉树的左右指针如上图↑
说明: 当线索化二叉树后,Node 节点的 属性 left 和 right ,有如下情况:
left 指向的是左子树,也可能是指向的前驱节点. 比如 ① 节点 left 指向的左子树, 而 ⑩ 节点的 left 指向的 就是前驱节点.
right 指向的是右子树,也可能是指向后继节点,比如 ① 节点 right 指向的是右子树,而⑩ 节点的 right 指向的是后继节点.
因此要改变原来的二叉树的结点结构
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 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 |
|
可以看到我们多出来了这么两个属性:
1 2 3 4 |
|
中序线索化二叉树
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 |
|
中序线索化二叉树思路
因为中序遍历的二叉树顺序是左根右,因此,首先对左子树进行线索化,递归线索化即可;
当递归到左子树的最左结点的时候,他的左结点肯定为空,那么就对他的左结点赋值为pre(pre结点是在线索化的最后一步赋值为当前结点,这样递归才能进行下去),注意左结点的类型一定要改为1,代表他是前趋结点。前趋结点就线索掉了。
后继结点的处理则是判断前趋结点,当前趋结点不为空,并且前趋结点的右节点为空,那么设置前趋结点的右节点为当前结点,也就是上一个结点未设置的右节点,类型同样要设置为后继
最后就是对pre这个结点赋值,为当前结点,因为下一次递归,当前结点就成了上一个结点,也就是这里的pre
最后就是对二叉树的右子结点进行线索化。
中序线索化二叉树的遍历
遍历中序线索化二叉树首先应该明确的是他的遍历顺序要和遍历原来的中序二叉树遍历的结果是一样的,才是遍历成功
那么第一步应该就是判断根结点不为空,也就是循环结束条件
接着就循环查找当前结点的左子结点类型为0的也就是没有被线索化的结点,只要他为0,那么结点就一直往左子结点赋值。直到找到第一个被线索化的结点,输出他,他就是我们第一个线索化并且也是中序遍历的第一个左子结点。
输出之后,判断他的右子结点是否被线索化,如果被线索化,那么当前结点node就被赋值为它自己的右子结点,并且输出,如果他之后的结点的右子结点的类型又为1,那么继续往后走并赋值,说明他有后继
直到右子结点的类型为0,退出循环之后,也应该向右再赋值,继续向后遍历
代码演示
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 |
|
线索化二叉树
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 |
|
遍历线索化二叉树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
图解
后续线索化二叉树
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 |
|
以上是如何实现Java数据结构中的线索化二叉树?的详细内容。更多信息请关注PHP中文网其他相关文章!