Question

C语言高手进!高分采纳写的最好的!还有追加哦!关于数据结构二叉排序树的编写。

编写程序，将若干整数从键盘输入，以构成一棵二叉排序树。计算二叉树中叶子节点的个数，并打印出所有的叶子节点的值。
思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印(printf)出来。

题目不难,但程序要越简洁越好!!!!!!!当然要在满足题目要求的前提之下!!!!!!!!!
我想要个写的好的高级一点的程序。

最好要用指针链表的方法来写，这样可以精炼一点。

匿名:高手拜托你就随便写几句嘛！！！！！
梦想窗外:只要打印叶子结点，不是所有结点都要打印，程序有点长，可以再精简一点吗？

最好要用指针链表的方法来写，这样可以精炼一点。

高手们，编译通过了（0 error 0 warning）再把正确程序贴上来好吗？

Answer 1

关于程序算法的优缺点没什么需要特别说明的，标准算法加了一个判断，仅此而已，便于初学者的理解。

//---------------------------------------------------------------------------

已经更改为你要的程序：

//---------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#define ENDIN (-1) /*括号里面的-1是结束标志，可以在此改为其它的整数*/

typedef struct Node{
int data;
struct Node *r;
struct Node *l;
} node;

typedef node *bt;

bt BST(bt a,int d)
{
if (a==NULL) {
a=(bt)malloc(sizeof(node));
a->data =d;
a->r=a->l=NULL;

}
else if (d<a->data ) {
a->l=BST(a->l ,d);
}
else if (d>=a->data ) {
a->r=BST(a->r,d);
}
return a;
}
bt init(void) /*创建一颗二叉排序树，输入结束标志时结束输入*/
{
int i=0;
bt tree=NULL;
while (scanf("%d",&i),i!=ENDIN){

tree=BST(tree,i);
}
return tree;
}
unsigned int inorder(bt a) /*中序遍历输出叶结点，并返回叶结点的个数*/
{
static unsigned int s=0;
if (a) {
inorder(a->l);
if (a->r==NULL&&a->l==NULL) {
++s;
printf("%d\t",a->data);
}
inorder(a->r);
}
return s;
}

void FreeTree(bt t) /*删除树*/
{
if (t) {
FreeTree(t->l);
FreeTree(t->r);
}
free(t);
}
int main(void)
{
bt te;
te=init();
printf("\n\nLeaf node:%d\n\n",inorder(te));
FreeTree(te);
return 0;
}
//---------------------------------------------------------------------------

Answer 2

思路都有了，自己还写不出来么

Answer 3

二叉排序树的特点是：对于任意的节点来说它本身的值都不小于它自己的左子树，同时也不大于它的右子树。

Answer 4

/* 测试数据：9 8 7 4 5 6 3 2 1 10 11 12 0 */
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define INPUT "%d"
#define OUTPUT "%d "
typedef int DataType;

typedef struct BSTNode
{
DataType data;
struct BSTNode *lchild;
struct BSTNode *rchild;
} BSTNode, *pBSTNode;

/* 清空二叉搜素树，回收所有节点内存 */
void Clear(pBSTNode root)
{
if (root)
{
Clear(root->lchild);
Clear(root->rchild);
free(root);
}
}

/* 输入节点值 */
void Insert(pBSTNode *root, DataType item)
{
pBSTNode cursor = *root, newnode = (pBSTNode)malloc(sizeof(BSTNode));
newnode->lchild = newnode->rchild = NULL;
newnode->data = item;

if (!*root)
{
*root = newnode;
return;
}

while (cursor)
{
if (item < cursor->data)
{
if (!cursor->lchild)
{
cursor->lchild = newnode;
return;
}

cursor = cursor->lchild;
}
else
{
if (!cursor->rchild)
{
cursor->rchild = newnode;
return;
}

cursor = cursor->rchild;
}
}
}
/* 先序遍历 */
void PreOrder(pBSTNode root)
{
if (root)
{
printf(OUTPUT, root->data);
PreOrder(root->lchild);
PreOrder(root->rchild);
}
}

/* 中序遍历 */
void InOrder(pBSTNode root)
{
if (root)
{
InOrder(root->lchild);
printf(OUTPUT, root->data);
InOrder(root->rchild);

}
}

/* 后缀遍历 */
void PostOrder(pBSTNode root)
{
if (root)
{
PostOrder(root->lchild);
PostOrder(root->rchild);
printf(OUTPUT, root->data);
}
}

/* 计算叶子个数 */
int SumLeaf(pBSTNode root)
{
if (root)
{
if (root->lchild == NULL && root->rchild == NULL)
return 1;
else
return SumLeaf(root->lchild) + SumLeaf(root->rchild);
}

return 0;
}

int main()
{
pBSTNode root = NULL;
DataType data;

while (1)
{
scanf(INPUT, &data);

/* 输入数据为0退出循环 */
if (data == 0)
break;

Insert(&root, data);
}

printf("\n\n");
printf("节点值：");
InOrder(root);
printf("\n\n");
printf("叶子数：%d\n", SumLeaf(root));
Clear(root);

return 0;
}

Answer 5

匿名高手，你好。我是 108416879602，问题补充次数到了，因此只能通过这种方式通知你一下：如果写得好再追加30分！

Answer 6

我是 108416879602，我是指在程序旁边要多几条“注释说明”，或最后注明一下你的程序有哪些优点（或特点），不是修改程序，写得好再追加30分！！！！！！