每日编程Day 6如何实现树的层次遍历？

本文共计778个文字，预计阅读时间需要4分钟。

二叉树采用二叉链表进行存储（如下所示），每个节点包含数据域Data，以及左右子指针域left和right。

请设计非递归算法计算二叉树的高度。

ctypedef struct BitNode { TElemType data; struct BitNode *left; struct BitNode *right;} BitNode;

int calculateHeight(BitNode *root) { if (root==NULL) return 0;

int height=0; int queue[1000]; // 使用数组模拟队列 int front=0, rear=0; queue[rear++]=root; // 初始化队列

while (front

for (int i=0; i left !=NULL) queue[rear++]=node->left; if (node->right !=NULL) queue[rear++]=node->right; }

levelHeight++; height=levelHeight > height ? levelHeight : height; }

return height;}

二叉树采用二叉链表进行存储（如下所示），每个结点包含数据域Data，左孩子指针域left和右孩子指针域right。请设计非递归算法统计二叉树的高度。

Typedef struct BitNode{ TElemType data; struct BitNode *left, *right; } *BiTree ;

int Height(BiTree T) { if(T==NULL) return 0; BiTree Q[MAXSIZE]; front =0; Q[0]=T; rear=1; count=1; temp=0; height=0; while(front!=last) { p=Q[front]; front=(front+1)%MAXSIZE; if(p->lchild!=NULL) { Q[rear]=p->lchild; rear=(rear+1)%MAXSIZE; } if(p->rchild!=NULL) { Q[rear]=p->rchild; rear=(rear+1)%MAXSIZE; } temp++; if(temp>=count) { count=(rear-front+MAXSIZE)%MAXSIZE; temp=0; height++; } } return height; }

层次遍历回顾

给出一棵二叉树{3,9,20,#,#,15,7},

3 / \ 9 20 / \ 15 7

层次遍历为：[3,9,20,15,7]

层次遍历题目变形：

1.二叉树采用二叉链表进行存储（如下所示），每个结点包含数据域Data，左孩子指针域left和右孩子指针域right。请设计算法判断树是否为完全二叉树。

Typedef struct BitNode{ TElemType data; struct BitNode *left, *right; } *BiTree ;

2.二叉树采用二叉链表进行存储（如下所示），每个结点包含数据域Data，左孩子指针域left和右孩子指针域right。请设计算法给定一颗树，返回其节点值从底向上的层次序遍历（按从叶节点所在层到根节点所在的层遍历，然后逐层从左往右遍历）。

Typedef struct BitNode{ TElemType data; struct BitNode *left, *right; } *BiTree ;

样例

给出一棵二叉树{3,9,20,#,#,15,7},

3 / \ 9 20 / \ 15 7

按照从下往上的层次遍历为：

[ [15,7], [9,20], [3] ]

3.哈夫曼树采用二叉链表进行存储（如下所示），每个结点包含权值域Data，左孩子指针域left和右孩子指针域right。请设计算法计算这颗哈夫曼树的带权路径长度。

Typedef struct BitNode{ int data; //哈夫曼树权值 struct BitNode *left, *right; } *BiTree ;