class Test{
public static void main(String[] args){
Scanner sc=new Scanner(System.in)
int n=sc.nextInt()
sc.close()
int a=1,b=1
int sum=1
for(int i=3i<=ni++){
sum=a+b
a=b
b=sum
}
System.out.format("第%d项是：%d", n, sum)
}
}
先序非递归算法【思路】
假设：T是要遍历树的根指针，若T != NULL
对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。
问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取T的右子树的根指针？
方法1：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
方法2：访问T->data后，将T->rchild入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T->rchild，出栈，遍历以该指针为根的子树。
【算法1】
voidPreOrder(BiTree T, Status ( *Visit ) (ElemType e))
{// 基于方法一
InitStack(S)
while ( T!=NULL || !StackEmpty(S)){
while ( T != NULL ){
Visit(T->data)
Push(S,T)
T = T->lchild
}
if( !StackEmpty(S) ){
Pop(S,T)
T = T->rchild
}
}
}
【算法2】
voidPreOrder(BiTree T, Status ( *Visit ) (ElemType e))
{// 基于方法二
InitStack(S)
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Visit(T->data)
Push(S, T->rchild)
T = T->lchild
}
if ( !StackEmpty(S) ){
Pop(S,T)
}
}
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。
中序非递归算法
【思路】
T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取T指针？
方法：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。
【算法】
voidInOrder(BiTree T, Status ( *Visit ) (ElemType e))
{
InitStack(S)
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T)
T = T->lchild
}
if( !StackEmpty(S) ){
Pop(S, T)
Visit(T->data)
T = T->rchild
}
}
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。
后序非递归算法
【思路】
T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。
可采用标记法，结点入栈时，配一个标志tag一同入栈(0：遍历左子树前的现场保护，1：遍历右子树前的现场保护)。
首先将T和tag(为0)入栈，遍历左子树；返回后，修改栈顶tag为1，遍历右子树；最后访问根结点。 [Page]
typedef struct stackElement{
Bitreedata
chartag
}stackElemType
【算法】
voidPostOrder(BiTree T, Status ( *Visit ) (ElemType e))
{
InitStack(S)
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T,0)
T = T->lchild
}
while ( !StackEmpty(S) &&GetTopTag(S)==1){
Pop(S, T)
Visit(T->data)
}
if ( !StackEmpty(S) ){
SetTopTag(S, 1) // 设置栈顶标记
T = GetTopPointer(S) // 取栈顶保存的指针
T = T->rchild
}else break
}
}
