用C实现:输入二叉树的前序和中序
/* ds7_1。c: 二叉树的创建、显示、查找、遍历、插入 */
#include "stdio。h"
#include "string。 h"
#define MAXSIZE 50
typedef struct node {
char data;
struct node *lchild;
struct node *rchild;
} BTREE;
BTREE *tree;
/* ================ */
void DispTree(BTREE *t,int level,char lr)
{
int i;
if (t!= NULL) {
for ( i = 1; i da...全部
/* ds7_1。c: 二叉树的创建、显示、查找、遍历、插入 */
#include "stdio。h"
#include "string。
h"
#define MAXSIZE 50
typedef struct node {
char data;
struct node *lchild;
struct node *rchild;
} BTREE;
BTREE *tree;
/* ================ */
void DispTree(BTREE *t,int level,char lr)
{
int i;
if (t!= NULL) {
for ( i = 1; i data,lr);
DispTree(t->lchild,level+1,'L');
DispTree(t->rchild,level+1,'R');
}
}
/* ================ */
BTREE *LocateTree_DLR(BTREE *t, char ch)
{
BTREE *s;
if (t->data == ch || t == NULL ) return (t);
s = LocateTree_DLR ( t -> lchild, ch ) ;
if ( s != NULL ) return (s);
else return ( LocateTree_DLR ( t -> rchild , ch ) ) ;
}
/* ================ */
BTREE *CreateTree()
{
char ch[5];
BTREE *root, *s, *p;
/* create boot */
gets(ch); strupr(ch);
if (ch[0] == '#') return( NULL );
root = (BTREE *) malloc ( sizeof(BTREE));
root->data = ch[0];
root->lchild = NULL ; root->rchild = NULL ;
gets(ch); strupr(ch);
while ( ch[0]!= '#') {
if ( LocateTree_DLR(root,ch[0]) == NULL ) {
p = LocateTree_DLR(root, ch[1]);
if (p == NULL )
printf("%c 位置结点不存在,重新输入!\n",ch[1]);
else {
if (ch[2] == 'L' && p->lchild != NULL)
printf("%c 位置不合理,重新输入!\n",ch[2]);
else if (ch[2] == 'R' && p->rchild != NULL)
printf("%c 位置不合理,重新输入!\n",ch[2]);
else {
s = (BTREE *) malloc ( sizeof(BTREE));
s->data = ch[0]; s->lchild = NULL; s->rchild = NULL;
if (ch[2] == 'L') p->lchild = s;
else if (ch[2] == 'R') p->rchild = s;
}
}
}
else printf("%c 结点已存在,重新输入!\n", ch[0]);
gets(ch); strupr(ch);
}
return (root);
}
/* ================ */
void TraversalTree_DLR(BTREE *t)
{
if (t != NULL) {
printf("%c ", t -> data);
TraversalTree_DLR ( t -> lchild ) ;
TraversalTree_DLR ( t -> rchild ) ;
}
}
/* ================ */
void TraversalTree_LDR(BTREE *t)
{
if (t != NULL) {
TraversalTree_LDR ( t -> lchild ) ;
printf("%c ", t -> data);
TraversalTree_LDR ( t -> rchild ) ;
}
}
/* ================ */
void TraversalTree_LRD(BTREE *t)
{
if (t != NULL) {
TraversalTree_LRD ( t -> lchild ) ;
TraversalTree_LRD ( t -> rchild ) ;
printf("%c ", t -> data);
}
}
/* ================ */
int TreeInsertNode(BTREE **root, char key, char lr, char x)
{
BTREE *p, *q;
if ( *root == NULL ) {
(*root) = (BTREE *)malloc(sizeof(BTREE));
(*root) -> data = x;
(*root) -> lchild = (*root) -> rchild = NULL;
return (1);
}
p = LocateTree_DLR(*root, key);
if ( p == NULL ) return(0);
q = (BTREE *)malloc(sizeof(BTREE));
q -> data = x;
if ( ( lr == 'L' && p->lchild == NULL ) ||
( lr == 'R' && p->rchild == NULL ) ) {
if (lr == 'L') p->lchild = q;
else p->rchild = q;
q -> lchild = q -> rchild = NULL ;
} else {
if (lr == 'L') {
q -> lchild = p -> lchild;
q -> rchild = NULL;
p -> lchild = q;
} else {
q -> rchild = p -> rchild;
q -> lchild = NULL;
p -> rchild = q;
}
}
return (1);
}
/* ================ */
main(){
tree = CreateTree();
DispTree(tree,0,'T');
TreeInsertNode(&tree, 'C', 'L', 'Y');
DispTree(tree,0,'T');
printf("\n先序遍历: "); TraversalTree_DLR ( tree ) ;
printf("\n中序遍历: "); TraversalTree_LDR ( tree ) ;
printf("\n后序遍历: "); TraversalTree_LRD ( tree ) ;
}
。收起