// 创建二叉树的原数组数据: 40 20 60 10 30 50 70
让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：域名申请、网页空间、营销软件、网站建设、太康网站维护、网站推广。
// 前序遍历序列: 40 20 10 30 60 50 70
// 中序遍历序列: 10 20 30 40 50 60 70
// 后序遍历序列: 10 30 20 50 70 60 40
// 输入关键字k1,k2的数值: 30 50
// 打印的结果:
// 40 30 50
//
// 二叉树示意图:
//
// 40
// / \
// 20 60
// / \ / \
// 10 30 50 70
#include "stdio.h"
#include "stdlib.h"
struct Tree
{
int data;
struct Tree *left;
struct Tree *right;
};
typedef struct Tree TreeNode;
typedef TreeNode *Bitree;
Bitree insertNode(Bitree root,int data) //插入结点
{
Bitree newnode;
Bitree current;
Bitree back;
newnode=(Bitree)malloc(sizeof(TreeNode));
if(newnode==NULL)
{
printf("\n动态分配内存出错.\n");
exit(1);
}
newnode-data=data;
newnode-left=NULL;
newnode-right=NULL;
if(root==NULL)
{
return newnode;
}
else
{
current=root;
while(current!=NULL)
{
back=current;
if(current-data data)
current=current-left;
else
current=current-right;
}
if(back-data data)
back-left=newnode;
else
back-right=newnode;
}
return root;
}
Bitree createTree(int *data,int len) //创建二叉树(非递归)
{
Bitree root=NULL;
int i;
for(i=0;ilen;i++)
{
root=insertNode(root,data[i]);
}
return root;
}
void preOrder(Bitree ptr) //先序遍历(递归法)
{
if(ptr!=NULL)
{
printf("%d ",ptr-data);
preOrder(ptr-left);
preOrder(ptr-right);
}
}
void inOrder(Bitree ptr) //中序遍历(递归法)
{
if(ptr!=NULL)
{
inOrder(ptr-left);
printf("%d ",ptr-data);
inOrder(ptr-right);
}
}
void postOrder(Bitree ptr) //后序遍历(递归法)
{
if(ptr!=NULL)
{
postOrder(ptr-left);
postOrder(ptr-right);
printf("%d ",ptr-data);
}
}
//根据关键字k1和k2,进行区间查找(递归法)
void btreeSearch(Bitree ptr,int k1,int k2)
{
if(ptr!=NULL)
{
if(ptr-data k1 ptr-data k2)
{
btreeSearch(ptr-right,k1,k2);
}
else if(ptr-data == k1 ptr-data k2)
{
printf("%d ",ptr-data);
btreeSearch(ptr-right,k1,k2);
}
else if(ptr-data k1 ptr-data k2)
{
printf("%d ",ptr-data);
btreeSearch(ptr-left,k1,ptr-data);
btreeSearch(ptr-right,ptr-data,k2);
}
else if(ptr-data k1 ptr-data == k2)
{
printf("%d ",ptr-data);
btreeSearch(ptr-left,k1,k2);
}
else if(ptr-data k1 ptr-data k2)
{
btreeSearch(ptr-left,k1,k2);
}
else if(ptr-data == k1 ptr-data == k2)
{
printf("%d ",ptr-data);
}
else
{
printf("其它情况,当前节点的数值是%d",ptr-data);
}
}
}
int main()
{
Bitree T=NULL; //T是二叉查找树
int data[]={40,20,60,10,30,50,70};
int len;
int i;
int k1,k2; //关键字k1,k2
int tmp;
len=sizeof(data)/sizeof(int);
printf("创建二叉树的原数组数据: ");
for(i=0;ilen;i++)
{
printf("%d ",data[i]);
}
T=createTree(data,len); //创建二叉树
printf("\n前序遍历序列: ");
preOrder(T);
printf("\n中序遍历序列: ");
inOrder(T);
printf("\n后序遍历序列: ");
postOrder(T);
printf("\n输入关键字k1,k2的数值: ");
scanf("%d%d",k1,k2);
if(k1k2)
{
tmp=k1;
k1=k2;
k2=tmp;
}
//根据关键字k1和k2,进行区间查找(递归法)
btreeSearch(T,k1,k2);
printf("\n");
return 0;
}
void read_file(void) //函数定义
{
FILE *fp; //文件指针
vistor *p;
fp=fopen("f1.txt","rb");
if(!fp){printf("文件不存在\n");return;}
p=applynode();
while(fscanf(fp,"%s %s %s %s %s",p-number,p-name,p-day,p-time,p-telephone)0)
{
insertnode(p);p=applynode();
}fclose(fp);
}
函数的功能：
无参函数，void 型。
以2进制方式打开文件f1.txt，用于读。若打开失败，显示 文件不存在，并返回。
若成功，调用 applynode(); 返回一个 vistor 形指针。
下面开始循环：
从文件读入5个字符串，放入 vistor 的成员变量 number,name,day,time,telephone，如果读成功了其中1个或1个以上，则执行循环体：调用 insertnode(p); 插入这个 节点p. 再 调用 applynode(); 返回一个新的 vistor 形指针。
当 fscanf 没能读到数据，while 循环结束。
#include "stdlib.h"
#include "stdio.h"
//链表的类型定义
typedef struct node
{
int data; //值域
struct node *link; //指针域
}*PNode,*LinkList;
//typedef struct node *PNode;
//typedef struct node *LinkList;
//创建空链表
LinkList createNullist_link(void)
{
LinkList list=(LinkList)malloc(sizeof(struct node));//申请表头结点空间
if(list!=NULL) list-link=NULL;
else printf("Out of space!\n");//创建失败
return(list);
}
//判断空链表
int isNullist_linkq(LinkList list)
{
return(list-link==NULL);
}
//在单链表中求某元素的存储位置
PNode locate_link(LinkList list,int x)
{//在list 带有头结点的单链表中找第一个值为x的结点存储位置
PNode p;
if(list-link==NULL) return(NULL);
p=list-link;
while(p!=NULL p-data!=x) p=p-link;
return(p);
}
// 单链表的插入
int insertPost_link(LinkList list,PNode p,int x)
{//在list 带有头结点的单链表中,p所指结点后面插入元素x
PNode q=(PNode )malloc(sizeof(struct node));
if(q==NULL)
{
printf("Out of space!!!\n");
return(0);
}
else
{
q-data=x;
q-link=p-link;
p-link=q;
return(1);
}
}
// 在单链表求p所指结点的前驱结点
PNode locatePre_link(LinkList list,PNode p)
{
PNode p1;
if(list-link==NULL) return(NULL);
while(p1!=NULL p1-link!=p) p1=p1-link;
return(p1);
}
// 单链表的删除
int insertPost_link(LinkList list,int x)
{//在list 带有头结点的单链表中删除第一个值为x的结点
PNode p,q ;
p=list;
if(p-link==NULL) return(0);
while(p-link!=NULL p-link-data!=x)
p=p-link;//找值为x的结点的前驱结点的存储位置
if(p-link==NULL) //没找到值为x的结点
{
printf("Not exist!\n");
return(0);
}
else
{
q=p-link;
p-link=q-link;
free(q);
return(1);
}
}
void main()
{
int i,x;
PNode p;
LinkList list1;
list1=createNullist_link();
if(list1!=NULL)
printf("创建空表成功！\n");
p=list1;
for(i=0;i5;i++)
{
printf("请输入第 %d 个结点的值：",i+1);
scanf("%d",x);
insertPost_link(list1,p,x);
p=p-link;
}
printf("\n");
p=list1-link;
while(p!=NULL)
{
if(p-link==NULL)
printf("%d",p-data);
else
printf("%d-",p-data);
p=p-link;
}
printf("\n");
printf("请输入删除结点的值：",i+1);
scanf("%d",x);
insertPost_link(list1,x);
printf("\n");
p=list1-link;
while(p!=NULL)
{
if(p-link==NULL)
printf("%d",p-data);
else
printf("%d-",p-data);
p=p-link;
}
}
#includestdio.h
#includestdlib.h
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef struct _Tree{
char data;
struct _Tree *lchild, *rchild;
}Tree;
typedef struct _List{
Tree *data;
struct _List *next;
}List;
typedef struct _stack{
List *top;
int size;
}Stack;
Tree* getTop(Stack stack)
{
if (stack.size 0)
return (stack.top)-data;
return NULL;
}
int Pop(Stack *stack)
{
if (stack-size 0){
List *top = stack-top;
stack-top = top-next;
stack-size--;
free(top);
return OK;
}
return ERROR;
}
int Push(Stack *stack, Tree *tree)
{
List *node = (List*)malloc(sizeof(List));
if (!node) exit(OVERFLOW);
node-data = tree;
node-next = stack-top;
stack-top = node;
stack-size++;
return OK;
}
void init(Tree **tree)
{
//输入一个字符作为该节点的数据，
//如果输入空格，'_'代表节点为NULL，先序输入字符
char data;
*tree = NULL;
data = getchar();
if (data != '_'){
*tree = (Tree*)malloc(sizeof(Tree));
(*tree)-data = data;
init((*tree)-lchild); //初始化左子树
init((*tree)-rchild); //初始化右子树
}
}
Tree* findPreKey1(Tree *tree, int K)
{
//二叉树中求位于先序序列中第K个位置的结点
//如果函数返回的结果为NULL, 则说明不存在
//递归版本
Tree* _findPreKey1(Tree *tree, int *p);
int p[1] = {K};
Tree *node;
node = _findPreKey1(tree, p);
return node;
}
Tree* _findPreKey1(Tree *tree, int *p)
{
Tree *node;
if (tree != NULL){
if (*p == 1) //当*p == 1时，则这个节点就是需要查找的节点
return tree;
else{
if (tree-lchild != NULL){
//如果tree的左子树不为NULL，结果即为左子树的先序序列的第*p-1个元素
(*p)--;
node = _findPreKey1(tree-lchild, p);
}
if (*p == 1) //在左子树中找到第K个元素,返回结果
return node;
//当在左子树已经遍历完，此时有*p != 1，即还没遍历到第K个元素
if (tree-rchild != NULL){
//如果右子树不为NULL，此时已经遍历了K-*p + 1个元素，那么结果即为右子树的先序
//序列的第*p-1个元素
(*p)--;
node = _findPreKey1(tree-rchild, p);
}
return node;
}
}
return NULL;
}
Tree* findPreKey2(Tree *tree, int K)
{
//二叉树中求位于先序序列中第K个位置的结点
//如果函数返回的结果为NULL, 则说明不存在
//非递归版本
Stack s = {top:NULL, size:0};
List *top;
Tree *node;
f(tree == NULL)
return NULL;
else{
Push(s, tree);
while(K != 1 s.size 0){
node = getTop(s);
Pop(s);
if (node-rchild)
Push(s, node-rchild);
if (node-lchild)
Push(s, node-lchild);
K--;
}
if (K == 1)
return getTop(s);
else
return NULL;
}
}
int main()
{
Tree *tree, *node1, *node2;
int K;
printf("按先序建立二叉树，'_'(下画线)代表节点为NULL:\n");
init(tree);
printf("请输入先序序列中的第K个位置（注意不要超过树的节点数）：\n");
scanf("%d", K);
node1 = findPreKey1(tree, K);
if (node1 != NULL)
printf("(递归版本)先序序列中的第%d个位置元素的值为：%c\n", K,node1-data);
else
printf("(递归版本)先序序列中不存在第%d个位置元素\n", K);
node2 = findPreKey2(tree, K);
if (node2 != NULL)
printf("(非递归版本)先序序列中的第%d个位置元素的值为：%c\n", K,node2-data);
else
printf("(非递归版本)先序序列中不存在第%d个位置元素\n", K);
return 0;
}
测试结果：
按先序建立二叉树，'_'(下画线)代表节点为NULL:
ABC__DE_G__F___
请输入先序序列中的第K个位置（注意不要超过树的节点数）：
6
(递归版本)先序序列中的第6个位置元素的值为：G
(非递归版本)先序序列中的第6个位置元素的值为：G
虽然代码显得有点冗余，不过还望楼主采纳！！
线性表可以直接用malloc申请连续空间，按数组保存。但这样不方便后期增删。
所以，建议使用链表来实现。
下面代码就是用链表实现线性表。
其中initList函数是生成了一个10节点的单向链表作为线性表。
ListLength就是题目要的函数。（函数中顺带打印了链表内容，你不想要显示链表内容，就删掉printf语句）。
#includestdio.h
#includemalloc.h
struct Sqlist
{
int num;
struct Sqlist *next;
};
struct Sqlist *initList();//初始化一个线性链表
int ListLength(struct Sqlist MyList);
int main()
{
struct Sqlist *mylist;
mylist=initList();
printf("\n线性表中元素个数为：%d\n",ListLength(*mylist));
return 0;
}
int ListLength(struct Sqlist MyList)
{
int cnt=0;
struct Sqlist *headList=MyList;
printf("生成的线性表各元素值为：");
while(headList)
{
printf("%d ",headList-num);
cnt++;
headList=headList-next;
}
return cnt;
}
struct Sqlist *initList()
{
int i;
struct Sqlist *newList=NULL,*firstList=NULL,*lastList=NULL;
for(i=1;i=10;i++)
{
newList=(struct Sqlist *)malloc(sizeof(struct Sqlist));
if(!newList)
return NULL;
newList-num=i;
newList-next=NULL;
if(!firstList)
firstList=newList;
else
lastList-next=newList;
lastList=newList;
}
return firstList;
};
