非递归算法求二叉树高度-创新互联

假设二叉树采用二叉链表的存储结构，设计一个非递归算法求二叉树高度；

我这边用C++的队列容器解决。

#include#includeusing namespace std;
typedef struct BiNode {
    char data;
    struct BiNode* lchild, * rchild;
}BiNode, * BiTree;
void create(BiTree& t) {//二叉树先序
    char ch;
    cin >>ch;
    if (ch == '@')t = NULL;
    else {
        t = new BiNode;
        t->data = ch;
        create(t->lchild);
        create(t->rchild);
    }
}
int Btdepth(BiTree t) {//使用C++容器
    queueq;
    BiTree last = NULL;
    int num = 0;
    BiTree p = t;
    q.push(p);
    last = q.back();
    while (!q.empty()) {
        p = q.front();
       
        
        if (p->lchild)q.push(p->lchild);
        if (p->rchild)q.push(p->rchild);
        if (p == last) {
            num++;
            last = q.back();
        }
        q.pop();//这个出队要放在这边，不能放在p = q.front();的下一行，因为如果在p = q.front();下一行
        //出队后容器可能为空，p == last的判断的前提是容器不为空。
        //使用容器的 top()、back（）的使用,必须保证容器不为空


    }
    return num;
}
int main() {
    BiTree t;
    create(t);//测试数据：abd@@e@@c@@
    //abcde
    //edcba
    cout<< Btdepth(t);
}

我重新又写了c语言的版本

#includeusing namespace std;
typedef struct BiNode {
    char data;
    struct BiNode* lchild, * rchild;
}BiNode, * BiTree;
typedef struct stack {
    BiTree data[1024];
    int top;
}stack;
typedef struct queue {
    BiTree data[1024];
    int front;
    int rear;
}queue;
void create(BiTree& t) {//二叉树先序
    char ch;
    cin >>ch;
    if (ch == '@')t = NULL;
    else {
        t = new BiNode;
        t->data = ch;
        create(t->lchild);
        create(t->rchild);
    }
}
int Btdepth(BiTree T) {
      BiTree q[1024];
    int front = 0, rear = 0;
    BiTree p = T;
    q[rear++] = p;
    int level = 0;
    int last = rear;
    while (front< rear) {
        p = q[front++];
        if (p->lchild)q[rear++] = p->lchild;
        if (p->rchild)q[rear++] = p->rchild;
        if (front == last) {
            level++;
            last = rear;
        }
    }
    return level;
}
int main() {
    BiTree t;
    create(t);//测试数据：abd@@e@@c@@
    //abcde
    //edcba
    cout<< Btdepth(t);

}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧