非递归求树高

simpleset / 2023-08-16 / 原文

利用层次遍历求树高，最重要的就是计算每一层的遍历什么时候结束。

curNode:　入队+1，出队-1。时刻记录队列中结点个数，preNode==0时，curNode==下一层结点个数

preNode：出队-1，当==0时，该层遍历结束。preNode=curNode；high++；

//非递归求二叉树的高度或深度
int TreeHighByQueue(Tree T)
{
    if(T==NULL)
        return 0； 
    Queue Q;　　　　　　
    InitQueue(Q);
    TreeNode* p=T;
    int high=0;
    EnQueue(Q,p);    //根节点入队，第一层只有一个 
    int preNode=1;     
    int curNode=1;
    while(!isEmpty(Q))
    {
        DeQueue(Q,p);
        preNode--;
        curNode--;
        if(p->lchild!=NULL)
        {
            EnQueue(Q,p->lchild);
            curNode++;
        }
        if(p->rchild!=NULL)
        {
            EnQueue(Q,p->rchild);
            curNode++;
        }
        if(preNode==0)
        {
            preNode=curNode;
            high++;
        }
    }
    return high;
}

完整代码：

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 100

typedef struct Node{
    int data;
    struct Node *lchild,*rchild;
}TreeNode,*Tree;

typedef struct {
    TreeNode* data[MaxSize];
    int front,rear;
}Queue;

void InitQueue(Queue &Q)
{
    Q.front=Q.rear=0;
}

bool isEmpty(Queue Q)
{
    if(Q.front==Q.rear)
        return true;
    return false;
}

bool isFull(Queue Q)
{
    if((Q.rear+1)%MaxSize==Q.front)
        return true;
    return false; 
}

bool EnQueue(Queue &Q,TreeNode* p)
{
    if(isFull(Q))
        return false;
    Q.data[Q.rear]=p;
    Q.rear=(Q.rear+1)%MaxSize;
    return true;
}

bool DeQueue(Queue &Q,TreeNode* &p)
{
    if(isEmpty(Q))
        return false;
    p=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

void CreateTree(Tree &T)
{
    int x;
    scanf("%d",&x);
    if(x==-1)
    {
        T=NULL;
        return;
    }
    else
    {
        T=(Tree)malloc(sizeof(TreeNode));
        T->data=x;
        printf("输入%d的左结点：",x);
        CreateTree(T->lchild);
        printf("输入%d的右结点：",x);
        CreateTree(T->rchild);
    }
}

//递归求二叉树的高度或深度 
int TreeHigh(Tree T)
{
    int High=0;
    if(T!=NULL)
    {
        int lefthigh=TreeHigh(T->lchild);
        int righthigh=TreeHigh(T->rchild);
        High=lefthigh>righthigh?lefthigh+1:righthigh+1;
    }
    return High;
}

//非递归求二叉树的高度或深度
int TreeHighByQueue(Tree T)
{
    if(T==NULL)
        return 0;
        
    Queue Q;
    InitQueue(Q);
    TreeNode* p=T;
    int high=0;
    EnQueue(Q,p);    //根节点入队，第一层只有一个 
    int preNode=1;     
    int curNode=1;
    while(!isEmpty(Q))
    {
        DeQueue(Q,p);
        preNode--;
        curNode--;
        if(p->lchild!=NULL)
        {
            EnQueue(Q,p->lchild);
            curNode++;
        }
        if(p->rchild!=NULL)
        {
            EnQueue(Q,p->rchild);
            curNode++;
        }
        if(preNode==0)
        {
            preNode=curNode;
            high++;
        }
    }
    return high;
}

int main()
{
    Tree T;
    CreateTree(T);
    int High=TreeHigh(T);
    printf("树高%d",High);
    return 0;
}