7、二叉挑序树的生成 二叉排序树的中序序列是一个递增的有序序列 ● 二叉排序树的生成步骤：已知一序列k,k2,,k} 一K作为二叉树的根； 若k2<k1,则k2插入到k的左子树上；否则，插入到k的右子树上； 读入k,若k<k1,则进入左子树，否则进入右子树；继续与子树 的根做上述比较，直到某结点k; 若k<k,且k,左子树空，则k插入到k左子树；若k>=k?且k右 子树空，则将k插入到k的右子树。 ·[例]已知序列 [190,381,12,40,410,394,540,760,85,476,800,146,9,445,600},试 构造一棵二叉排序树。 电子科技大学刘民岷 树和二叉树 7电子科技大学 刘民岷 树和二叉树 7 • 二叉排序树的中序序列是一个递增的有序序列 • 二叉排序树的生成步骤：已知一序列{k1,k2,…,kn} – K1作为二叉树的根； – 若k2<k1，则k2插入到k1的左子树上；否则，插入到k1的右子树上； – 读入ki，若ki<k1，则进入左子树，否则进入右子树；继续与子树 的根做上述比较，直到某结点ki； – 若ki<kj，且kj左子树空，则ki插入到kj左子树；若ki>=kj，且kj右 子树空，则将ki插入到kj的右子树。 • [例]已知序列 {190,381,12,40,410,394,540,760,85,476,800,146,9,445,600},试 构造一棵二叉排序树