【每日编程】Day 6 树的层次遍历

二叉树采用二叉链表进行存储（如下所示），每个结点包含数据域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 ;