2. 考研
  3. 假设K1，…，Kn是n个关键词，试解答： (1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，…，Kn，时，用算法建立一棵以LLINK—RLJNK链接表示的二叉查找树。 (2)设计一个算法，打印出该二叉查找树

假设K1，…，Kn是n个关键词，试解答： (1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，…，Kn，时，用算法建立一棵以LLINK—RLJNK链接表示的二叉查找树。 (2)设计一个算法，打印出该二叉查找树

admin2019-08-01  17
问题 假设K1，…，Kn是n个关键词，试解答：
    (1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，…，Kn，时，用算法建立一棵以LLINK—RLJNK链接表示的二叉查找树。
    (2)设计一个算法，打印出该二叉查找树的嵌套括号表示结构。假定该二叉查找树的嵌套括号表示结构为B(A，D(C，E))。
选项
答案(1)非递归建立二叉排序树，在二叉排序树上插入的结点都是叶子结点。 typedef struct node{ Elemtype data； struct node*LLINK，*RLINK； }node*B／Tree； void Create_BST(BiTree bst，datatype K[]，int n){ ／／以存储在数组K中的n个关键字，建立一棵初始为空的二叉排序树 int i； BiTree p，f； for(i=1；i<=n i i++){ p=bst；f=null： ／／在调用Create_BST时，bst=null while(p!=null) if(p一>dataRLINK；} ／／f是p的双亲 else if(p一>data>K[i]){f=p；p=p一>LLINK；} s=(BiTree)malloc(sizeof(B／Node))；／／申请结点空间 s一>data=K[i]；s->LLINK=null；s->RLINK=null； if(f==null)bst=s： ／／根结点 else if(s一>datadata)f一>LLINK=s； ／／左子女 else f一>RLINK=s； ／／右子树根结点的值大于等于根结点的值 } } (2)本题要求输出遍历二叉排序树的嵌套括号表示。其算法思想是，若二叉排序树非空，则输出根结点，再输出其左右子树。在输出其左右子树前，要输出左括号，在输出其右子树前要输出逗号，在输出其右子树后要输出右括号，在左右子树均空情况下，则不输出括号。 void Print(BiTree t){ ／／以嵌套括号表示结构打印二叉排序树 if(t!=null){ printf(t一>data)； ／／打印根结点值 if(t一>LLINK||t一>LLINK)； ／／左子女和右子女中至少有一个不空 printf(“(”)； ／／输出左括号 Print(t一>LLINK)； ／／输出左子树的嵌套括号表示 if(t一>RLINK)printf(“，”)； ／／若右子树不空，输出逗号 Print(t一>RLINK)； ／／输出右子树的嵌套括号表示 printf(“)”)； ／／输出右括号 } }
解析
转载请注明原文地址:https://www.kaotiyun.com/show/qkCi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)