题目内容
（请给出正确答案）
[主观题]
在一棵以二叉链表表示的二叉树上，试写出用按层次顺序遍历二叉树的方法，统计树中具有度为1的结点
数目的算法。【同济大学2000三、2(12分)】【山东大学1993二(12分)】【上海交大1999三(12分)】【天津大学2005七(10分)】【北京理工200l九(8分)2006七、1(15／2分)】【南京航空航天大学2004二、3(12分)】
提问人：网友miyaonanhai
发布时间：2022-01-07
如搜索结果不匹配，请 
题目内容
（请给出正确答案）
您可能会需要：
安装简答题APP，拍照搜题省时又省心！
更多“在一棵以二叉链表表示的二叉树上，试写出用按层次顺序遍历二叉树…”相关的问题
第1题
设一棵二叉树的存储表示是二叉链表，编写一个用逆转链方法实现二叉树前序遍历的算法。这个方法的思想是在遍历过程中沿着结点的左子女或右子女方向“下降”时，临时改变其leftChild或rightChild的值，使之指向该结点的父结点，从商为以后的“上升”提供路径;在上升的过程中将结点的leftChild或rightChild的值恢复原来的值。为了在上升的过程中区分是从该结点的左子树上升的还是从右子树上升的，在结点中设置一个tag标志。进人算法时，所有结点的tag设为0，当遍历过程中进入结点的左子树时，将该结点的tag置为l、从左子树退出进人右子树时再将该结点的tag置为0.
点击查看答案
第2题
设一棵二义树的存储表示是二叉链表、编写一个用Robson方法实现二叉树后序遍历的算法。Robson方法遍历二叉树的特点如下：
点击查看答案
(1)沿袭5-60题使用逆转链遍历二叉树的思想。
(2)不使用tag标志，而是用内嵌的栈代替tag的作用。该内嵌的栈使用了叶结点作为栈的结构，没有另外定义栈的存储空间。
(3)利用栈解决在回溯时分辨究竟是从左子树还是右子树上升的问题，步骤是：
①当进入有非空左子树的结点的右子树时，将该结点的地址进栈。
②在回溯过程中如遇到结点的左、布子树都非空时，如果该结点就是存于栈顶的结点，则可判定当前是从该结点的右子树退回，该结点的右子女指针指向它的父结点;否则当前是从该结点的左子树退回，该结点的左子女指向它的父结点。
第5题
程序填空。 若已知一棵二叉树的先序和中序，可唯一确定这棵树。以下按照该法创建一棵二叉树，接着按中序遍历。 #include <stdio.h> #include <stdlib.h> typedef char ElemType; //定义结点数据为int型 typedef int Status; //定义函数类型为int型 #define ERROR 0 #define OK 1 struct BiTNode{ //定义结构体 ElemType data; //结点数值 struct BiTNode *lchild; //左孩子指针 struct BiTNode *rchild; //右孩子指针 }; BiTNode *BiTree,*s; // 两个全局指针变量 ElemType x[4]={'A','B','C','D'}; //该树的先序序列 ElemType z[4]={'C','B','A','D'}; //该树的中序序列 void CreateBiTree(BiTNode *root,ElemType y) //功能：将y插入到root所指向的树 { int k=0; if(root==NULL) //若root为空，即root指向空树，（*s）成为该树的根节点 {root=s;s->data=y;s->lchild=NULL;s->rchild=NULL;} //填充（*s） else //若非空 { while(_________________) //5分 k++; //在中序列找到等于当前插入元素y或者等于当 // 前根元素（root->data）的结点为止 if(z[k]==y) //若找到的结点等于当前插入元素y，说明y在根元 { //素(root->data)左边，代表y在根元素的左子树 CreateBiTree(root->lchild,y); //将y插入当前root的左子树 __________=BiTree; //配合BiTree=root; 使全局变量BiTree逐渐回归 } //到最大树的根节点，以便插入下一个结点时始终从最大树根节点出发 //同时使结点（*s）获得父亲 3分 else // 若找到的结点等于当前根元素（root->data），说明 { //y在当前根元素的右边，代表y在当前根元素的右子树 CreateBiTree(root->rchild,y); //将y插入当前root的右子树 ___________=BiTree; //配合BiTree=root; 使全局..........(同上） } } BiTree=root; //和上面配合，使全局变量BiTree逐渐回归到最大树的根节点。 //目前，BiTree、root、s三者相同，但结点(*s)还没有父亲 } void MidOrder(BiTNode *root) //中序遍历方法 { if(!(root->lchild==NULL)) MidOrder(root->lchild); printf("%c",root->data); if(!(root->rchild==NULL)) MidOrder(root->rchild); } main() { int i; BiTree=NULL; for(i=0;i<4;i++) if(s="(BiTNode*)malloc(sizeof(BiTNode)))" { createbitree(bitree,x[i]); 按照先序序列逐个插入，所有结点插入完毕后 树就建成了 } midorder(bitree);>
