📄 急！急有一 数据结构 题请教！！！！ - 考研论坛.htm
字号:
alt=引用这个帖子回复 src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/quote.gif"
align=absMiddle border=0></A> <A
href="http://bbs.kaoyan.com/posting.asp?action=copypost&topic=609276"><IMG
alt=复制 src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/copy.gif" align=absMiddle
border=0></A> <A
href="http://bbs.kaoyan.com/download.asp?topic=609276"><IMG
alt=将本帖子内容通过email打包下载 src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/mailto.gif"
align=absMiddle border=0></A> <A
href="http://bbs.kaoyan.com/ubbmisc.asp?forum=%BC%C6%CB%E3%BB%FA&action=getip&topic=609276"><IMG
alt=管理员查看gofaster的IP src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/ip.gif"
align=absMiddle border=0></A>
<HR>
<DIV align=right></DIV>不用栈, 就用个队列吧</TD></TR>
<TR bgColor=#dcdcdc>
<TD vAlign=top noWrap width="18%">flyinsail<BR><IMG
src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/Imagef24.gif"
vspace=5><BR><B>开国大老</B><BR>积分：2303<BR>发贴：601<BR>来自：山西<BR>注册：2001-08-14<BR></TD>
<TD vAlign=top><IMG src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/icon1.gif"
align=absMiddle border=0> 发表于 2001-12-26 <FONT
color=#000000>12:03:19</FONT> <A target=_blank
href="http://bbs.kaoyan.com/viewuser.asp?username=flyinsail"><IMG
alt=按此观看flyinsail的个人资料 src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/profile.gif"
align=absMiddle border=0></A> <A href="mailto:flyinsail@263.net"><IMG
alt=按此发邮件给flyinsail src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/email.gif"
align=absMiddle border=0></A> <A
href="http://search.tencent.com/cgi-bin/friend/user_show_info?ln=4911126"><IMG
alt="flyinsail 的 oicq 是4911126,查看 4911126 的资料"
src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/oicq.gif" align=absMiddle
border=0></A> <A
href="http://bbs.kaoyan.com/pm.asp?action=newPM&recipient=flyinsail&subject=%BC%B1%A3%A1%BC%B1%D3%D0%D2%BB+%CA%FD%BE%DD%BD%E1%B9%B9+%CC%E2%C7%EB%BD%CC%A3%A1%A3%A1%A3%A1%A3%A1"><IMG
alt=发送悄悄话给flyinsail src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/pm.gif"
align=absMiddle border=0></A> <A target=_blank
href="http://bbs.kaoyan.com/search.asp?action=searchuser&username=flyinsail"><IMG
height=16 alt=搜索flyinsail的所有帖子
src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/find.gif" width=16 align=absMiddle
border=0></A> <A
href="http://bbs.kaoyan.com/posting.asp?Forum=%BC%C6%CB%E3%BB%FA&Topic=609301&TopicSubject=%BC%B1%A3%A1%BC%B1%D3%D0%D2%BB+%CA%FD%BE%DD%BD%E1%B9%B9+%CC%E2%C7%EB%BD%CC%A3%A1%A3%A1%A3%A1%A3%A1&action=editpost"><IMG
alt=编辑/删除帖子 src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/edit.gif" align=absMiddle
border=0 ?></A> <A
href="http://bbs.kaoyan.com/posting.asp?quotenum=609301&action=replywquote&forum=%BC%C6%CB%E3%BB%FA&topic=609118&TopicSubject=%BC%B1%A3%A1%BC%B1%D3%D0%D2%BB+%CA%FD%BE%DD%BD%E1%B9%B9+%CC%E2%C7%EB%BD%CC%A3%A1%A3%A1%A3%A1%A3%A1"><IMG
alt=引用这个帖子回复 src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/quote.gif"
align=absMiddle border=0></A> <A
href="http://bbs.kaoyan.com/posting.asp?action=copypost&topic=609301"><IMG
alt=复制 src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/copy.gif" align=absMiddle
border=0></A> <A
href="http://bbs.kaoyan.com/download.asp?topic=609301"><IMG
alt=将本帖子内容通过email打包下载 src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/mailto.gif"
align=absMiddle border=0></A> <A
href="http://bbs.kaoyan.com/ubbmisc.asp?forum=%BC%C6%CB%E3%BB%FA&action=getip&topic=609301"><IMG
alt=管理员查看flyinsail的IP src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/ip.gif"
align=absMiddle border=0></A>
<HR>
<DIV align=right></DIV>中序遍历三叉树是不用栈的。
<P>向左走到尽头；<BR>while(p){<BR>如果有右子树，后继是右子树的最左节点；<BR>如果没有右子树，而且是父母的左子树，后继就是父母；<BR>如果没有右子树，而且是父母的右子树，一直上溯到自身是父母的左子树，这时候父母就是后继<BR>}
<P>
<HR>
<FONT
color=blue>我像冬天里的田鼠一样，躲在暖暖的洞穴里，吃着储存着的粮食。想着明天怎样变得和松鼠一样讨人喜欢。可是到了可以出去的时候，又忙忙碌碌地寻找着食物，忘记了曾经的宏伟目标。</FONT></TD></TR>
<TR bgColor=#f7f7f7>
<TD vAlign=top noWrap width="18%">胖胖龙<BR><IMG
src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/Imaged60.gif"
vspace=5><BR><B>高级站友</B><BR>积分：785<BR>发贴：198<BR>来自：<BR>注册：2001-09-01<BR></TD>
<TD vAlign=top><IMG src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/icon1.gif"
align=absMiddle border=0> 发表于 2001-12-26 <FONT
color=#000000>15:17:53</FONT> <A target=_blank
href="http://bbs.kaoyan.com/viewuser.asp?username=%C5%D6%C5%D6%C1%FA"><IMG
alt=按此观看胖胖龙的个人资料 src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/profile.gif"
align=absMiddle border=0></A> <IMG alt=该用户不允许显示它的电子邮件
src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/email.gif" align=absMiddle
border=0> <A
href="http://bbs.kaoyan.com/pm.asp?action=newPM&recipient=%C5%D6%C5%D6%C1%FA&subject=%BC%B1%A3%A1%BC%B1%D3%D0%D2%BB+%CA%FD%BE%DD%BD%E1%B9%B9+%CC%E2%C7%EB%BD%CC%A3%A1%A3%A1%A3%A1%A3%A1"><IMG
alt=发送悄悄话给胖胖龙 src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/pm.gif" align=absMiddle
border=0></A> <A target=_blank
href="http://bbs.kaoyan.com/search.asp?action=searchuser&username=%C5%D6%C5%D6%C1%FA"><IMG
height=16 alt=搜索胖胖龙的所有帖子 src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/find.gif"
width=16 align=absMiddle border=0></A> <A
href="http://bbs.kaoyan.com/posting.asp?Forum=%BC%C6%CB%E3%BB%FA&Topic=609674&TopicSubject=%BC%B1%A3%A1%BC%B1%D3%D0%D2%BB+%CA%FD%BE%DD%BD%E1%B9%B9+%CC%E2%C7%EB%BD%CC%A3%A1%A3%A1%A3%A1%A3%A1&action=editpost"><IMG
alt=编辑/删除帖子 src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/edit.gif" align=absMiddle
border=0 ?></A> <A
href="http://bbs.kaoyan.com/posting.asp?quotenum=609674&action=replywquote&forum=%BC%C6%CB%E3%BB%FA&topic=609118&TopicSubject=%BC%B1%A3%A1%BC%B1%D3%D0%D2%BB+%CA%FD%BE%DD%BD%E1%B9%B9+%CC%E2%C7%EB%BD%CC%A3%A1%A3%A1%A3%A1%A3%A1"><IMG
alt=引用这个帖子回复 src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/quote.gif"
align=absMiddle border=0></A> <A
href="http://bbs.kaoyan.com/posting.asp?action=copypost&topic=609674"><IMG
alt=复制 src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/copy.gif" align=absMiddle
border=0></A> <A
href="http://bbs.kaoyan.com/download.asp?topic=609674"><IMG
alt=将本帖子内容通过email打包下载 src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/mailto.gif"
align=absMiddle border=0></A> <A
href="http://bbs.kaoyan.com/ubbmisc.asp?forum=%BC%C6%CB%E3%BB%FA&action=getip&topic=609674"><IMG
alt=管理员查看胖胖龙的IP src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/ip.gif"
align=absMiddle border=0></A>
<HR>
<DIV
align=right></DIV>这个题目俺有兴趣，下面就是俺写的算法（呜呜呜，没得午觉睡了），请大家品评。<BR>此题本质，就是要在此存储结构上不设栈地非递归遍历二叉树<BR>//二叉树的三叉链表存储结构<BR>typedef
struct BiTNode{<BR>TElemType data;<BR>struct BiTNode *parent, *lchild,
*rchild;<BR>}BiTNode, *BiTree;
<P>Void InOrderTraverse(BiTree &T){<BR>p=T; pre=NULL; i=0; j=0;
ISBST=TRUE;<BR>//pre指向刚访问的结点，i、j分别记录度为0、1的结点数，ISBST记录此树是否二叉排序树<BR>if(p){<BR>while(p->lchild)p=p->lchild;//向左走到尽头<BR>while(1){<BR>if(!p->lchid&&!p->rchild)i++;<BR>if((!p->lchid&&p->rchild)||(p->lchid&&!p->rchild))j++;<BR>if(pre&&pre->data>p->data)ISBST=FALSE;<BR>pre==p;//保持pre指向刚访问的结点<BR>if(p->rchild){<BR>p=p->rchild;<BR>while(p->lchild)p=p->lchild;<BR>}//刚访问的结点，若其右子树非空，则其中序后继为右子树上最左的结点<BR>else{//刚访问的结点的右子树为空<BR>if(p->parent->lchild==p)p=p->parent;<BR>//若此结点是其双亲的左孩子，则其中序后继就是它的双亲结点<BR>else{<BR>//若此结点是其双亲的右孩子，则要沿双亲链一直寻找直至找到以此结点为左后代的某结<BR>//点（即当前结点的中序后继），或找到根（说明此结点是根的右子树上最右的结点，此时<BR>//应结束整个遍历过程）<BR>while(p!=T&&p->parent->lchild!=p)p=p->parent;<BR>if(p==T)break;//已遍历完二叉树，结束循环<BR>p=p->parent;<BR>}//else<BR>}//else<BR>}//while<BR>}//if<BR>printf("The
number of the nodes which have 0 degree is %d",i);<BR>printf("The number
of the nodes which have 1 degree is %d",j);<BR>if(ISBST)printf("The tree
is a BiSortTree."<IMG
src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/wink.gif">;<BR>else printf("The tree
is not a BiSortTree."<IMG
src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/wink.gif">;<BR>}//InOrderTraverse<BR><IMG
src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/tongue.gif"> <IMG
src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/tongue.gif"> <IMG
src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/tongue.gif">
<P>
<HR>
龙岂池中物？乘雷欲上天！</TD></TR>
<TR bgColor=#dcdcdc>
<TD vAlign=top noWrap width="18%">liusheng7<BR><IMG
src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/Imageb25.gif"
vspace=5><BR><B>开国大老</B><BR>积分：1040<BR>发贴：269<BR>来自：<BR>注册：2001-06-07<BR></TD>
<TD vAlign=top><IMG src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/icon1.gif"
align=absMiddle border=0> 发表于 2001-12-26 <FONT
color=#000000>23:35:23</FONT> <A target=_blank
href="http://bbs.kaoyan.com/viewuser.asp?username=liusheng7"><IMG
alt=按此观看liusheng7的个人资料 src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/profile.gif"
align=absMiddle border=0></A> <A
href="mailto:liu_sheng7@sina.com"><IMG alt=按此发邮件给liusheng7
src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/email.gif" align=absMiddle
border=0></A> <A
href="http://bbs.kaoyan.com/pm.asp?action=newPM&recipient=liusheng7&subject=%BC%B1%A3%A1%BC%B1%D3%D0%D2%BB+%CA%FD%BE%DD%BD%E1%B9%B9+%CC%E2%C7%EB%BD%CC%A3%A1%A3%A1%A3%A1%A3%A1"><IMG
alt=发送悄悄话给liusheng7 src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/pm.gif"
align=absMiddle border=0></A> <A target=_blank
href="http://bbs.kaoyan.com/search.asp?action=searchuser&username=liusheng7"><IMG
height=16 alt=搜索liusheng7的所有帖子
src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/find.gif" width=16 align=absMiddle
border=0></A> <A
href="http://bbs.kaoyan.com/posting.asp?Forum=%BC%C6%CB%E3%BB%FA&Topic=610748&TopicSubject=%BC%B1%A3%A1%BC%B1%D3%D0%D2%BB+%CA%FD%BE%DD%BD%E1%B9%B9+%CC%E2%C7%EB%BD%CC%A3%A1%A3%A1%A3%A1%A3%A1&action=editpost"><IMG
alt=编辑/删除帖子 src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/edit.gif" align=absMiddle
border=0 ?></A> <A
href="http://bbs.kaoyan.com/posting.asp?quotenum=610748&action=replywquote&forum=%BC%C6%CB%E3%BB%FA&topic=609118&TopicSubject=%BC%B1%A3%A1%BC%B1%D3%D0%D2%BB+%CA%FD%BE%DD%BD%E1%B9%B9+%CC%E2%C7%EB%BD%CC%A3%A1%A3%A1%A3%A1%A3%A1"><IMG
alt=引用这个帖子回复 src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/quote.gif"
align=absMiddle border=0></A> <A
href="http://bbs.kaoyan.com/posting.asp?action=copypost&topic=610748"><IMG
alt=复制 src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/copy.gif" align=absMiddle
border=0></A> <A
href="http://bbs.kaoyan.com/download.asp?topic=610748"><IMG
alt=将本帖子内容通过email打包下载 src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/mailto.gif"
align=absMiddle border=0></A> <A
href="http://bbs.kaoyan.com/ubbmisc.asp?forum=%BC%C6%CB%E3%BB%FA&action=getip&topic=610748"><IMG
alt=管理员查看liusheng7的IP src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/ip.gif"
align=absMiddle border=0></A>
<HR>
<DIV
align=right></DIV>这道题其实不是很难，关键看你平时做过这类题没有。<BR>这道题可以这样看：根据题目要求，知道这道题是要遍历二叉树，又告诉了要检查是否为二叉排序树。是否为二叉排序树就是看它的中序遍历是否有序。<BR>而做一个中序遍历的不用栈的非递归程序（用三叉链表做）是习题集上6。40的一道题。所以要在平时多做这类题，考试时才不会无处下手。<BR>下面是6。40的答案（我做的，大家看对不对）<BR>TYPE
bitreptr=^bnodetp;<BR>bondetp=RECORD<BR>data<IMG
src="急！急有一 数据结构 题请教！！！！ - 考研论坛.files/biggrin.gif">atatype;<BR>lchild,rchild,parent:bitreptr<BR>END;<BR>PROC
inorder_nonrecursive(bt:bitreptr);<BR>p:=bt;<BR>while p<> nil do
<BR>[ while p^.lchild<>nil do
p:=p^.lchild;{找到以P为根的子树中中序遍历的第一个结点}<BR>visite(p);<BR>while p<>nil
CAND p^.rchild=nil do{当P的右孩不存在时}<BR>[ repeat<BR>pre:=p;p:=p^.parent{
pre保存P的值，返回到P结点的双亲结点}<BR>until p<>nil CAND
pre=p^.rchild;{当P结点为双亲结点的右孩时}<BR>if (p<>nil) visite(p)
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -