Question

设计一个非递归算法 从一棵二叉树中查找出所有节点的最大值并返回

Answer 1

用广度搜索
创建队列
创建初始MAX值 0
将树跟放入队列
将树根取出队列和MAX对比 比MAX大则替换MAX
然后将取出节点的左右子节点放入队列
如上遍历队列
依次类推
最后得出MAX值

Answer 2

请参考：
// Test6.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"

#define MAX 100
#define EMPTY 0xFFFF

struct stack
{
int data[MAX];
int top;
}Stack;

struct Tree
{
char data;
struct Tree *left;
struct Tree *right;
};

struct queue
{
//char data[MAX];
struct Tree *data[MAX];
int front;
int rear;
}Queue;

//栈中top所指向的保留为空
void Initial();
void PushStack(int iData);
int PopStack();

//队列中rear所指向的保留为空
void InsertQueue(struct Tree *iData);
struct Tree * DeleteQueue();

void CreateTree(struct Tree **root);
void PrintTree(struct Tree *r, int order);
void TransLevel(struct Tree *r);

struct Tree * TransLevel_MaxNum(struct Tree *r);

int main(int argc, char* argv[])
{

Initial();
struct Tree *root=NULL;
CreateTree(&root);
printf("\n层次遍历:");
//TransLevel(root);
struct Tree *p =TransLevel_MaxNum(root);
printf("\nMax char is :%c\n",p->data);
return 0;
}

void Initial()
{
int i=0;
struct Tree t={0,NULL,NULL};
for (i=0; i<MAX; i++)
{
Stack.data[i] = 0;
Queue.data[i] = &t;
}
Stack.top = 0;

Queue.front = 0;
Queue.rear = 0;

}

void PushStack(int iData)
{
if (Stack.top>=MAX-1)
{
printf("Stack is full!\n");
return ;
}
Stack.data[Stack.top] = iData;
Stack.top = Stack.top+1;
}
int PopStack()
{
if (Stack.top == 0)
{
printf("Stack is empty!\n");
return EMPTY;
}
int temp=0;
Stack.top = Stack.top-1;
temp = Stack.data[Stack.top];
return temp;

}
void InsertQueue(struct Tree *t)
{
if (Queue.front == (Queue.rear+1)%MAX )
{
printf("\nQueue is full\n");
return ;
}
Queue.data[Queue.rear] = t;
Queue.rear = (Queue.rear+1)%MAX;
}
struct Tree * DeleteQueue()
{
// struct Tree t={0,NULL,NULL};
if (Queue.front == Queue.rear)
{
printf("\nQueue is empty\n");
return NULL;
}
struct Tree *temp=NULL;

temp = Queue.data[Queue.front];
Queue.front = (Queue.front+1)%MAX;
return temp;
}

void CreateTree(struct Tree **root)
{
char ch;
ch = getchar();
if (ch == '#')
{
return ;
}
*root = (struct Tree *)malloc(sizeof(struct Tree));
(*root)->data = ch;
(*root)->left = NULL;
(*root)->right = NULL;
CreateTree(&(*root)->left);
CreateTree(&(*root)->right);
}

void PrintTree(struct Tree *r,int order)
{
if (r == NULL)
{
return ;
}
switch(order)
{
case 0:printf("%c",r->data);
PrintTree(r->left, order);
PrintTree(r->right,order);
break;
case 1:PrintTree(r->left,order);
printf("%c",r->data);
PrintTree(r->right,order);
break;
case 2:PrintTree(r->left,order);
PrintTree(r->right,order);
printf("%c",r->data);
break;
}
}

void TransLevel(struct Tree *r)
{
if (r == NULL)
{
return ;
}
InsertQueue(r);
struct Tree *pTree=NULL;
while ( (pTree=DeleteQueue()) != NULL )
{
printf("%c",pTree->data);
if (pTree->left != NULL)
{
InsertQueue(pTree->left);
}
if (pTree->right != NULL)
{
InsertQueue(pTree->right);
}
}
}

struct Tree * TransLevel_MaxNum(struct Tree *r)
{
if (r == NULL)
{
return NULL;
}
struct Tree *temp=r;
int maxNum = r->data;
InsertQueue(r);
struct Tree *pTree=NULL;
while ( (pTree=DeleteQueue()) != NULL )
{
printf("%c",pTree->data);
if (pTree->data > maxNum)
{
maxNum = pTree->data;
temp = pTree;
}
if (pTree->left != NULL)
{
InsertQueue(pTree->left);
}
if (pTree->right != NULL)
{
InsertQueue(pTree->right);
}
}
return temp;
}

//其中栈的代码为练习所用，非必要代码