给定序列 6 8 5 7 9 3构建二叉排序树并画出先序索二叉树

柠檬初夏目 · 2018-4-30 01:57:38

出现两个4，所以按照定义这两个四都不放进去，后面的先序线索二叉树就是将没有左孩子的添加前驱，没有右孩子的添加后继，若没有前驱或者后继写null。

ggg8422771 · 2018-4-30 01:57:37

二叉排序树就是中序遍历之后是有序的；
构造二叉排序树步骤如下；
插入法构造

聽第二个结点聽4聽比聽6聽来的小聽所以插入在聽6聽的左子树；

聽第三个结点聽8聽比聽6聽来的大聽所以插入在聽6聽的右子树；

第四个结点聽5聽比6聽来得小聽先进入左子树然后跟聽4比较，
5聽比4聽大聽所以插入在聽4聽的右子树；

聽
以此类推聽将要插入的结点先跟根结点比较，聽比根结点大进入右子树聽反之进入聽左子树；
在跟进入的聽左子树（右子树）的结点比较聽方法同上；
直到没有结点了聽在插入；聽你给的排序最后的二叉排序树如下；

聽
聽
聽中序遍历结果是聽：聽 3聽4聽5聽6聽7聽8聽9聽；
聽先序遍历结果是聽：聽6聽4聽3聽5聽8聽7聽9聽；

给定序列 6 8 5 7 9 3构建二叉排序树 并画出先序索二叉树

2 个回复

给定序列 6 8 5 7 9 3构建二叉排序树并画出先序索二叉树