假設(shè)二叉樹采用二叉鏈表的存儲結(jié)構(gòu)，設(shè)計一個非遞歸算法求二叉樹高度；

創(chuàng)新互聯(lián)成立于2013年，先為遷安等服務(wù)建站，遷安等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為遷安企業(yè)網(wǎng)站制作PC+手機+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。

我這邊用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);//測試數(shù)據(jù)：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);//測試數(shù)據(jù)：abd@@e@@c@@
    //abcde
    //edcba
    cout<< Btdepth(t);

}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

新聞名稱：非遞歸算法求二叉樹高度-創(chuàng)新互聯(lián)
鏈接URL：http://chinadenli.net/article24/hjeje.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站內(nèi)鏈、App開發(fā)、云服務(wù)器、網(wǎng)站排名、微信小程序、品牌網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)