[数据结构与算法]算法笔记--二叉树相应的算法题

算法笔记–二叉树相应的算法题

1.二叉树自下而上、从右到左的层次遍历算法

void InvertLevel(BiTree T){
    Stack s;
    Queue q;
    if(bt){
        InitStack(s);
        InitQueue(q);
        EnQueue(q,T);
        while(!IsEmpty(q)){
            DeQueue(q,p);
            push(s,p); //出队时将元素入栈
            if(p->lchild)
                EnQueue(q,p->lchild);
            if(p->rchild)
                EnQueue(q,p->rchild);
        }
        while(!IsEmpty(s)){ //最后将栈遍历，则得到反向层次遍历的结果
            pop(s,p);
            visit(p->data);
        }
    }
}

2.设计非递归算法求链表存储的二叉树高度

int GetHeight(BiTree T){ //非递归算法
    if(!T) return 0;
    int front=-1,rear=-1;
    int last=0,level=0; //last指向当前层的最右节点，level记录当前层数
    BiTree q[MaxSize];
    q[++rear]=T;
    BiTree p; //操作指针
    while(front<rear){
        p=q[++front];
        //层次遍历
        if(p->lchild)
            q[++rear]=p->lchild;
        if(p->rchild)
            q[++rear]=p->rchild;
        if(front==last){ //若当前指针与当前层最右节点相等。则层数+1，last指向下一层最右节点
            level++;
            last=rear;
        }
    }
    return level;
}

//递归算法如下
int GetHeight2(BiTree T){
    if(!T) return 0;
    lheight=GetHeight2(T->lchild);
    rheight=GetHeight2(T->rchild);
    if(lheight<rheight) return riheight+1;
    else lheight+1;
}

3.一颗节点各不相同的二叉树，先序和中序遍历的序列分别存在两个一维数组A[1…n]和B[1…n]中，建立该二叉树链表

BiTree createBiTree(ElemType A[],ElemType B[],int l1,int h1,int l2,int h2){
    //l1,h1为先序的第一个和最后一个节点下标
    //l2,h2为中序的第一个和最后一个节点下标
    root=(BiTNode*)malloc(sizeof(BiTNode));
    root->data=A[l1];
    for(i=l2;B[i]!=root;i++);
    llen=i-l2; //左子树长度
    rlen=h2-i;//右子树长度
    if(llen) //递归建立左子树
        root->lchild=createBiTree(A,B,l1+1,l1+llen,l2,l2+llen-1);
    else root->lchild=null;
    if(rlen) //递归建立右子树
        root->rchild=createBiTree(A,B,l1+llen,h1,l2+llen,h2);
    else root->rchild=null;
    return root;
}

4.二叉树按链表存储，判断给定二叉树是否一个完全二叉树

bool CheckCompleteBT(BiTree T){
    queue<BitNode> q; //建立队列
    if(!T) return true;
    q.push(T);
    while(!q.empty()){ //层次遍历
        auto p=q.front();
        q.pop();
        if(p){ //若某节点不为空，则将其左右儿子一次入队
            q.push(p->lchild);
            q.push(p->rchild)
        }else{ //若某节点为空
            while(!q.empty()){ //则判断队列中剩下节点是否有不为空的节点
                p=q.front();
                q.pop();
                if(p) return false; //若有，则不是完全二叉树
            }
        }
    }
    return true; //否则是完全二叉树
}

5.二叉树采用二叉链表存储，计算给定一颗二叉树的所有双分支节点个数

$$\begin{gathered} 计算一颗二叉树b中所有双分支节点个数的递归模型如下： \\ f(b)=0,b=null \\ f(b)=f(b?>lchild)+f(b?>rchild)+1,b为双分支节点 \\ f(b)=f(b?>lchild)+f(b?>rchild),b为单分之节点or叶子节点 \end{gathered}$$

int computeDNode1(BiTree T){ //采用递归方法
   	if(!T) return 0;
    else if(T->lchild&&T->rchild) 
        return computeDNode(T->lchild)+computeDNode(T->rchild)+1;
    else
        return computeDNode(T->lchild)+computeDNode(T->rchild);
}

int computeDNode2(BiTree T){ //非递归方法
    queue<BitNode> q;
    int num=0; //用来计数
    q.push(T);
    while(!q.empty()){ //层次遍历二叉树
       	auto p=q.front();
        q.pop();
        if(p->lcihld&&p->rchild) //若当前节点有左右儿子，则计数器+1
            num++;
        q.push(p->lchild);
        q.push(p->rchild);
    }
    return num;
}

6.若树B是链式存储的二叉树，设计一个把树B中所有节点的左、右子树进行交换的函数

void swap(BiTree T){ //递归
    if(T){
        swap(b->lchild); //递归交换左子树
        swap(b->rchild); //递归交换右子树
        auto temp=T->lchild; //交换左右孩子节点
        T->lchlid=T->rchild;
        T->rchild=temp;
    }
}

7.二叉树采用链表存储，求先序遍历序列中第k个节点的值（1<=k<=n）

int i=1;//全局变量，记录当前所访问的是第几个节点
ElemType getIndex(BiTree T,int k){
    if(!T) return null; //节点为空返回null
    if(i==k) return T->data; //如果当前节点是第k个节点，则返回data
    i++;
    auto val=getIndex(T->lchild,k); //遍历左子树
    if(val!=null) { //如果左子树中已经遍历到第k个节点了则直接返回
        i=1; //重置全局变量，方便下次使用
        return val;
    }
    val=getiIndex(T->rchild,k);//否则遍历右子树，直到找到第k个节点
    i=1; //重置全局变量，方便下次使用
    return val;
}