Question

请设计求二叉树中分支结点个数的算法。（二叉树采用二叉链表存储，分别实现递归算法和非递归算法）

详细的算法 程序步骤！能实现的采纳再加100在线等 急求！！！

Answer 1

1. 递归算法
void getBranchNum(TreeNode *root)
{
if (root == NULL)
return 0;
if (root->left != NULL || root->right != NULL)
return 1 + getBranchNum(root->left) + getBranchNum(root->right);
return 0;
}
2. 非递归算法：
typedef struct Link
{
TreeNode * root;
struct Link * next;
}Queue;

int getBranchNum(TreeNode *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 > 0)
nNum ++;

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

追问

你好 还有些问题想问你，能加你求求吗

追答

Soucula@126.com
你发我邮箱吧