2. 考研
  3. 假设二叉树采用二叉链表存储结构存储，设计一个算法，求先序遍历序列中第k(1≤k≤二叉树中结点个数)个结点的值，要求： 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

假设二叉树采用二叉链表存储结构存储，设计一个算法，求先序遍历序列中第k(1≤k≤二叉树中结点个数)个结点的值，要求： 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

admin2018-07-17  59
问题 假设二叉树采用二叉链表存储结构存储，设计一个算法，求先序遍历序列中第k(1≤k≤二叉树中结点个数)个结点的值，要求：
根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
选项
答案算法的设计如下： int n=1； ElemType PreNode(BTNode *b，int k)( ElemType ch； if(b==NULL) return ’ ’； if(n==k) return b—>data； ++n； ch=PreNode(b—>ichild，k)； if(ch!=’ ’) return ch； ch=PreNOde(b—>rchiid，k)； return ch； } 若对递归不熟悉的同学也可以在二叉树的非递归先序遍历算法模型上进行修改，考虑到非递归算法的复杂性，考场上并不推荐使用非递归算法，既耗时又容易出错。相比之下，递归算法不仅简单，代码数量也较短，适宜在考场上使用。学有余力的同学可以自己再用非递归算法把这题再做一遍。 下面给出非递归算法的代码： #define MaxSize 100 int n=1； ElemType PreNode(BTNode *b，int k){ BTNode *st[MaxSize]，*p； if(b!=NULL){ st[++top]=b； while(top>—1){ p=st[top一一]； ++n； if(n==k)return P—>data； if(p—>rchild)st[++top]=p—>rchild； ／／右子树进栈 if (p—>lchild)st[r++top]=p—>lchild； ／／左子树进栈 } } return’ ’； } 在统考中，二叉树的算法大多会围绕遍历这个知识点进行出题，考生务必掌握好三种遍历算法，并在基本算法的基础上学会简单的修改进而解决问题。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/3yRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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