2014-941

2014-941

1.将整数数组[1…n]中所有的偶数放到所有奇数之前，并求时间复杂度

int swap(int a,int b){
    int temp = b;
    b = a;
    a = temp;
}
int shuzu(int A[]){
    int i,j = 0;
    while(A[i] != NULL){
        if(A[i] % 2 != 0){//奇数
        	i++;
        }
        if(A[i] % 2 = 0){//偶数
            swap(A[i],A[j]);
            i++；
            j++;
        }
    }
    return A;
}

2.按递减次序打印所有左子树非空，右子树为空的结点的关键字

• 重要

• 二叉查找树采用链式存储

• 各个结点的关键词均不相同

• 非递归算法

---

• 利用栈，先一路走到最右边，然后判断该结点是否符合题意
• 若不符合转向左子树，继续在左子树的右子树里依次寻找

---

int guanjianzi(BiTree T){
    BiTree *p = T;
    int Stack[];
    int top = -1;
    while(p || top > -1){
        while(p){
            Stack[++top] = p;
            p = p -> rchild;//右分支向下
        }
        if(top > -1){
            p = Stack[top--];
            if(p -> lchild != NULL && p -> rchild == NULL){
                printf(p -> data);
            }
            p = p -> lchild;//左分支
        }//if
    }//while
}