假定一棵二叉树用二叉链表存储试编写求出二叉树中1度结点个数的算法

Question

如题所述

Answer 1

/*
设0度结点
1度结点
2度结点个数分别为x0
x1
x2
*/
x0+x1+x2
=
node_count;
//三种结点数之和为总结点数
0*x0
+
1*x1
+
2*x2
=
node_count
-
1;
//树枝数等于结点数减1（去掉根结点）
一式乘2减二式得
2*x0
+
x1
=
node_count
+
1;
因此只要知道叶子数和总结点数就可得1度结点个数

Answer 2

typedef
struct
bitnode
//二叉树结点定义
{
int
data;
struct
bitnode
*lchild;
struct
bitnode
*rchild;
}bitnode;
bitnode*
binary_create()
//创建二叉树
{
bitnode
*t
=
null;
int
n;
scanf("%d",
&n);
if
(n
!=
0)
{
t
=
(bitnode
*)malloc(sizeof(bitnode));
if
(t
==
null)
printf("内存分配错误!");
else
{
t->data
=
n;
t->lchild
=
binary_create();
t->rchild
=
binary_create();
}
}
return
t;
}
void
binary_output(bitnode
*t)
//前序遍历二叉树
{
if
(t
!=
null)
{
printf("%d
",
t->data);
binary_output(t->lchild);
binary_output(t->rchild);
}
}
void
binary_delete(bitnode
*t)
//释放空间
{
if
(t
!=
null)
{
binary_delete(t->lchild);
binary_delete(t->rchild);
free(t);
}
}
void
inorder(bitnode
*t)
//中序遍历
{
if
(
t
!=
null)
{
inorder(t->lchild);
printf("%d
",
t->data);
inorder(t->rchild);
}
}