二叉树层次遍历非递归求树的高度C语言

    思路：设置level变量记录层数，last变量记录该层最右结点，在层次遍历出队时，让队列的front指针与last对比，相等证明该层遍历完了，last=rear，同时level+1，直至遍历完成，即队列为空，此时level即为二叉树的高度。完整代码如下：

#include 
#include 
#include #define MaxSize 100struct tree {int data;struct tree* left;struct tree* right;
};typedef struct queue{struct tree* numQ[MaxSize];int front;int rear;
}Queue;Queue Q;void initilize() { //初始化队列Q.front = -1;Q.rear = -1;
}struct tree* creatTree (struct tree* root) {int value;scanf("%d", &value);if (value == -1)return NULL;root = (struct tree*)malloc(sizeof(struct tree));root->data = value;printf("请输入%d的左子树：", root->data);root->left = creatTree(root->left);printf("请输入%d的右子树：", root->data);root->right = creatTree(root->right);return root;
}
int main() {printf("请输入头节点：");struct tree* root = creatTree(root);initilize();  //初始化队列int level = 0,last = 0;Q.numQ[++Q.rear]=root;//根节点入队struct tree *p;while(Q.frontleft)Q.numQ[++Q.rear]=p->left;if(p->right)Q.numQ[++Q.rear]=p->right;if(Q.front==last){//该层遍历完毕level++;last = Q.rear;//层数+1}}printf("该树的高度为%d\n",level);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！