1.输出二叉树某一层结点（从左到右）
把输出二叉树第K层结点转换成：分别输出"以该二叉树根结点的左右子树为根的两棵子树"中第K-1层结点。
void PrintNodeAtLevel(Node *root , int level)
{
if(!root || level < 0)
return ;
if(level == 0)
{
printf("%c", root->chValue);
}
PrintNodeAtLevel(root->lChild , level - 1);
PrintNodeAtLevel(root->rChild , level - 1);
}
个人觉得，原书中：return a() + b()似乎不能保证从左往右输出，因为a() + b()的调用顺序是由编译器决定的，并不一定是从左往右。
2.按层从上到下遍历二叉树，每一层单独一行且从左往右输出
front为队首指针，指向队首元素，rear为队尾指针，指向队尾元素的下一个位置
void InitQueue()
{
front = rear = 0;
}
void EnQueue(Node *p)
{
Q[rear++] = p;
}
Node *DeQueue()
{
return Q[front++];
}
void PrintNodeByLevel(Node *root)
{
int last;
Node *p;
if(!root) return ;
InitQueue();
EnQueue(root);
while(front < rear)
{
last = rear;
while(front < last)
{
p = DeQueue();
printf("%c", p->chValue);
if(p->lChild) EnQueue(p->lChild);
if(p->rChild) EnQueue(p->rChild);
}
printf("\n");
}
}
3.扩展问题
依然是按层遍历二叉树，只是要求从下往上访问，并且每一层中结点的访问顺序为从右向左
分析：只要层与层之间加入哑元素（NULL），然后逆序输出队列Q即可
{dy}步：给每一层之间添加哑元素NULL
void PrintNodeByLevel(Node *root)
{
int last;
Node *p;
if(!root) return ;
InitQueue();
EnQueue(root);
EnQueue(NULL);
while(front < rear - 1)
{
last = rear - 1;
while(front < last)
{
p = DeQueue();
if(p->lChild) EnQueue(p->lChild);
if(p->rChild) EnQueue(p->rChild);
}
EnQueue(NULL);
front = last + 1;
}
}
第二步：逆序输出队列Q
4.百度一道面xx
输出二叉树第 m 层的第 k 个节点值(m, k 均从 0 开始计数)
递归方法：
利用||从左往右的计算顺序以及其真值关系
int Print(Node *root , int m , int *cnt)
{
if(!root || m < 0)
return 0;
if(m == 0)
{
if(*cnt == k)
{
printf("%c", root->chValue);
return 1;
}
*cnt += 1;
return 0;
}
return Print(root->lChild , m - 1 , cnt) || Print(root->rChild , m - 1 , cnt);
}
非递归方法：
按照先前层次遍历的方法找到第m层，第k个结点，然后输出，代码略
程序还未严格验证，如果bug,请告知谢谢~
posted on 2010-06-01 14:53 阅读(1) 所属分类:
