汉扬编程 编程大纲 用C实现输入二叉树的前序和中序遍历

用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 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 ) ;

}

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/mianfei/6423.html

上机实验报告建立二叉树A(B(D

include的用法、区别?重定义错误及extern \”C\”

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部