Question

二叉树问题，请C语言高手帮忙

1、给定一棵用二叉链表表示的二叉树，其根指针为root。试用C语言写一个程序求二叉树结点的数目（用非递归算法或递归算法）

2、给定一棵用二叉链表表示的二叉树，其根指针为root。试用C语言写一个程序求二叉树的深度

希望C语言高手浪费点你们宝贵的时间帮帮忙，本人感激涕零....谢谢大家

Answer 1

对于第一个问题，求结点个数还是比较简单的，最方便的就是使用递归算法了，函数如下：
void node_count (node *head)
{
if (head != NULL)
{
count++;
node_count (head->left);
node_count (head->right);
}
}
再附上一个完整的程序吧，可以用它来建数和验证这个计算结点个数的函数^_^
#include <stdio.h>
#include <stdlib.h>

int count = 0;
typedef struct node
{
int data;
struct node *left;
struct node *right;
} node;

//建树，为了方便，我建的是二叉排序树
void
create_tree (node ** root, int x)
{
node *current, *bak;

node *p = (node *) malloc (sizeof (node));
if (p == NULL)
{
perror ("malloc");
exit (1);
}

p->data = x;
p->left = NULL;
p->right = NULL;

if (*root == NULL)
*root = p;
else
{
current = *root;
while (current != NULL)
{
bak = current;
if (x < current->data)
current = current->left;
else
current = current->right;
}
if (x < bak->data)
bak->left = p;
else
bak->right = p;
}
}
//中序遍历该树，目的是验证一下程序是否正确
void
Inorder (node * root)
{
if (root)
{
Inorder (root->left);
printf ("%d ", root->data);
Inorder (root->right);
}
}
//销毁
void
destroy (node *root)
{
if (root)
{
destroy (root->left);
destroy (root->right);
free (root);
root = NULL;
}
}
//这部分是最关键的了，也是你最想看到的吧，就是节点统计计数的函数
void
node_count (node *root)
{
if (root != NULL)
{
count++;
node_count (root->left);
node_count (root->right);
}
}

int
main ()
{
node *root = NULL;
int i;
int n;
int a[] = { 3, 5, 1, 2, 7, 4, 9 };
n = sizeof a / sizeof a[0];

for (i = 0; i < n; i++)
create_tree (&root, a[i]);

Inorder (root);
printf ("\n");

node_count (root);
printf ("count = %d\n", count);
destroy (root);

return 0;
}

Answer 2

int leavenum(tree p)//求叶子数
{

if(p==null)
{
return 0;
}
else{
return depth(p->lchild)+depth(p->rchild);

}

}

int treedepth(tree p)//求树深度
{
int leftdep,rightdep;
if(p==null)
{
return 0;
}
else
{
leftdep=treedepth(p->lchild);
rightdep=treedepth(p->rchild);
return leftdep>rightdep?leftdep+1:rightdep+1;
}
}

随便写了一下，不保证对

Answer 3

hello!!