Question

求二叉树中结点的度为1的个数的算法，并以n返回（要求非递归）一定要是非递归呀。。。求大神详细指导

Answer 1

typedef struct Link
{
Tree * root;
struct Link * next;
}Queue;

int getOneDegreeNum(Tree *root)
{
Queue *head = (Queue *)malloc(sizeof(Queue));
Queue *tail = head;
head->root = root;
head->next = NULL;
int nNum = 0;

while(head != NULL)
{
Queue *temp;
int degree = 0;
if (head->root->left != NULL)
{
temp = (Queue *)malloc(sizeof(Queue));
temp->root = head->root->left;
temp->next = NULL;
tail->next = temp;
tail = temp;
degree++;
}

if (head->root->right != NULL)
{
temp = (Queue *)malloc(sizeof(Queue));
temp->root = head->root->right;
temp->next = NULL;
tail->next = temp;
tail = temp;
degree++;
}

if (degree == 1)
nNum ++;

temp = head;
head = head->next;
free(temp);
}
return nNum;
}