关于层次遍历二叉树的一些算法总结

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了关于层次遍历二叉树的一些算法总结，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1856字，纯文字阅读大概需要3分钟。

内容图文

//递归遍历二叉树
void levelOrder(BTNode *T){
    if(T==null) return;
    int height=getHeight(T);
    for(int i=1;i<height;i++){
        _levelOrder(T,i);
    }
}
void _levelOrder(BTNode *T,int num){
    if(T==null||i==0) return;
    if(i==1){
        visit(T->data);
        return;
    }    
    _levelOrder(T->lchild,i-1);
    _levelOrder(T->rchild,i-1);
}

//使用栈
void levelOrder(BiTree T){
    Init(Queue Q);
    BTNode* p;
    EnQueue(Q,T);
    while(!isEmpty(Q)){
        DeQueue(Q,p);
        visit(p);
        if(T->lchild){
            EnQueue(Q,T->lchild);
        }
        if(T->rchild){
            EnQueue(Q,T->rchild);
        }
    }
}

关于层次遍历二叉树的相关应用

---

//层次遍历求二叉树高度  
int Height(BTNode *T){
    if(T==null) return 0;
    else{
        InitQueue(Q);
        int front=-1,rear=-1;
        int last=0,level=0;
        Q[++rear]=T;
        BTNode *p;
        while(front<rear){
            p=Q[++front];
            if(p->lchild!=null) Q[++rear]=p->lchild;
            if(p->rchild!=null) Q[++rear]=p->rchild;
            if(front==last){
                level++;
                last=rear;
            }
        }
        return level;
    }
}

//求指定层次叶子节点的个数 
int Count_leaf(BTNode *t,int k){
    if(t==null) return 0;
    BTNode *p;
    int front=-1,rear=-1;
    int last=0,level=0,num=0;
    InitQueue(Q);
    Q[++rear]=T;
    while(front<rear){
        p=Q[++front];
        if(p->lchild==null && p->rchild==null && level=k-1) num++;
        if(p->lchild!=null) Q[++rear]=p->lchild;
        if(p->rchild!=null) Q[++rear]=p->rchild;
        if(front==last){
            last=rear;
            level++;
        }
        if(level>k) return num;
    }
    return 0;
}

//求二叉树的宽度 
int count_bread(BTNode *t){
    if(t==null) return 0;
    BTNode *p;
    int front=-1,rear=-1;
    int last=0;
    InitQueue(Q);
    int tempnum=0,max=0;
    Q[++rear]=T;
    while(front<rear){
        p=Q[++front];
        tempnum++;
        if(p->lchild!=null) Q[++rear]=p->lchild;
        if(p->rchild!=null) Q[++rear]=p->rchild;
        if(front==last){
            last=rear;
            if(tempnum>max){
                max=tempnum;
            }
            tempnum=0;
        }
    }
    return max;
}

//判断一棵树是否为完全二叉树 4
bool IsComplete(BTNode *T){
    if(T==null) return true;
    BTNode *p=T;
    InitQueue(Q,p);
    while(!isEmpty(Q)){
        p=DeQueue(Q);
        if(p==null) break;
        EnQueue(Q,p->lchild);
        EnQueue(Q,p->rchild);
    }
    while(!isEmpty(Q)){
        p=DeQueue(&Q);
        if(p!=null)
            return false;
    }
    return true;
}

欢迎留言讨论

内容总结

以上是互联网集市为您收集整理的关于层次遍历二叉树的一些算法总结全部内容，希望文章能够帮你解决关于层次遍历二叉树的一些算法总结所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---