數據結構考研分類復習真題 第六章 答案 (五)[15]

　　[題目分析] 先序遍歷二叉樹的非遞歸算法要求進棧元素少意味著空指針不進棧

　　void PreOrder(Bitree  bt)//對二叉數bt進行非遞歸遍歷
　　{int top=; Bitree s[]; //top是棧s的棧頂指針棧中元素是樹結點指針棧容量足夠大
　　while(bt!=null || top>)
　　{while(bt!=null)
　　{printf(bt>data);  //訪問根結點
　　if(bt>rchlid) s[++top]=bt>rchild;  //若有右子女則右子女進棧
　　bt=bt>lchild; }
　　if (top>) bt=s[top];
　　}

　　本題中的二叉樹中需進棧的元素有 CHKF

　　[題目分析]二叉樹的順序存儲是按完全二叉樹的順序存儲格式雙親與子女結點下標間有確定關系對順序存儲結構的二叉樹進行遍歷與二叉鏈表類似在順序存儲結構下判二叉樹為空時用結點下標大於n（完全二叉樹）或（對一般二叉樹的虛結點）本題是完全二叉樹

　　void PreOrder(ElemType btint n)//對以順序結構存儲的完全二叉樹bt進行前序遍歷
　　{int top=s[];  //top是棧s的棧頂指針棧容量足夠大
　　while(i<=n||top>)
　　{while(i<=n)
　　{ printf(bt[i]);                   //訪問根結點
　　if (*i+<=n) s[++top]=*i+;    //右子女的下標位置進棧
　　i=*i; }                         //沿左子女向下
　　if(top>) i=s[top]; }           //取出棧頂元素
　　}//結束PreOrder

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/23731.html