Question

数据结构二叉排序树问题

一个二叉数，存储结构包括结点DATA，左右孩子指针，求：树中可能存在数据域值相同的结点，设计一个算法，按递增顺序打印各结点的数据域值，但相同的数据元素仅打印一个。
我的问题：
1。二叉排序树中怎么会有域值相同的结点？再生成二叉排序树的时候相同的结点就合并了吗？
2。如果没有相同的结点，那就是题的一个陷阱喽？那就不用管它，用递归的方法，中序遍历二叉树同时打印，就这一个函数就够了对吧？
3。如果有相同的结点，那就需要在遍历前生成一个链表，每查到一个结点就插入链表，然后打印，这个方法是不是麻烦了？

Answer 1

1. 二叉排序树中怎么会有域值相同的结点？再生成二叉排序树的时候相同的结点就合并了吗？
不论是生成还是再生成，如果生成过程中不检查并排除域值相同的情形，就会有域值相同的结点。关键在于生成程序如何处理域值相同的情形。
2. 此问题不存在.
3. 如果有相同的结点，那就需要在遍历前生成一个链表，每查到一个结点就插入链表，然后打印，这个方法是不是麻烦了？
是麻烦了. 是否可以在每打印一个节点前检查与前次打印的节点域值是否相同。不相同再打印. 以下程序供参考。主程序调用printnode时用语句：printnode(root);

typedef struct _node {
struct _node *left;
struct _node *right;
int data;
} NODE;

NODE *root = NULL;

//主程序及构造二叉排序树略.

void printnode(NODE *p)
{
static NODE *p0;
if (p==root) p0=NULL;//如果程序只调用一次，这两句可以合并为 static NODE *p0=NULL;
if (p) {
printnode(p->left);
if (p0==NULL || p0->data!=p->data)
{
printf("%d ", p->data);
p0 = p;
}
printnode(p->right);
}
}

Answer 2

排序问题中是存在相同关键字元素的现象的，不过我还没遇到过二叉排序树处理相同值的情况。
1.不应该合并结点，排序的关键字相同，但两个元素的主码可能不同，是两个不同的元素，合并了就丢失信息了，不好。
2.我认为应该先规定一下，左子树的值都小于等于其父结点，或右子树的值都大于等于其父结点，这样就可以处理相同值的情况了。
3.按递增顺序打印值时，相同数据元素仅打印一个，也不需要做链表啊，中序遍历顺次输出就行了，用一个变量保存前一次输出的值，遍历后一个元素时，比较如果相同就不输出，再继续往后就行了。