杭州IT培训学校江干区学IT去哪里

"1　什么是二叉树

二叉树也是一种树状结构。

二叉树中每个节点多有两个子节点。

二叉树中每个节点都比自己左边节点的值大，比右边节点的值小。

2　添加元素

l 添加进来的个元素就是根节点；

l 然后再添加第二个元素时，与根节点进行比较，如果比根节点大，那么放到根节点的右侧子节点位置；如果比根节点小，那么放到根节点左侧子节点位置；如果与根节点相等，那么添加失败。

l 添加第三个元素时，先与根比较：

如果比根小，那么再与根的左侧子节点进行比较：

n 大于左侧节点，新元素放到左节点的右节点位置；

n 小于左节点，放到左节点的左节点位置；

n 等于左节点，那么添加失败。

如果比根大，那么再与根的右侧子节点进行比较：

n 大于右侧节点，新元素放到右节点的右节点位置；

n 小于左节点，放到左节点的左节点位置；

n 等于左节点，那么添加失败。

如果等于根节点，那么添加失败。

例如：向TreeSet中添加Integer，分别是：2,5,8,3,6,9,3

步：添加2到树中，因为没有元素，那么2为根节点：




第二步：添加5到树中，因为5大于根节点2，所以把5放到2的右边：




第三步：添加8到树中，因为8大于根节点2，所以再让8与5比较，因为8大于5，所以把8放到5的右边：





第四步：添加3到树中，因为3大于根节点2，所以再让3与5比较，因为3小于5，所以把3放到5的左边：





第五步：添加6到树中，因为6大于根节点2，所以再让6与5比较，因为6大于6，所以让6与8比较，因为6小于8，所以把6放到8的左边：





第六步：添加9到树中，因为9大于根节点2，所以再让9与5比较，因为9大于5，所以让9与8比较，因为9小于8，所以把9放到8的右边：





第七步：添加3到树中，因为3大于根节点2，所以再让3与5比较，因为3小于5，所以让3与3比较，因为3与3相等，所以添加失败！




3　遍历二叉树

遍历二叉树是原则是先左，然后当前节点，后是右。

例如还是以上面二叉树结构举例说明：

l 2是根节点，那么需要再遍历2的左节点，但因为2没有左节点，所以打印；

l 然后是2的右节点了，即5；

l 因为5有左节点，所以遍历到3节点；

l 因为3没有左结节，所打印3，然后轮到3的右节点，但因为3没有右节点，所以打印3结节结束；

l 5的左节点打印结束，开始打印5本身，然后是打印5右侧节点8；

l 因为8有左节点，所先打印左节点6；

l 因为6没有左节点，所打印6本身，因为6没有右节点，所以打印6节点结束；

l 8节点的左侧打印完毕，开始打印8本身，然后开始打印8的右侧节点9；

l 因为9没有左节点，所以打印9本身，因为9没有右节点，所以打印9结束；

l 打印8结束；

l 打印5结束；

l 打印2结束。"