二叉树叶子结点从左到右链成单链表
#include
#include
#include
using namespace std;
#define max 50
typedef struct xiaofei//定义结构体
{
int data; struct xiaofei *lchild,*rchild;//定义结点的左右指针
}test;
xiaofei *root,*p,*q[max],*head,*first;
int sum=0;
int m=sizeof(test);//生成二叉排序树
void insert_data(int x)
{
xiaofei *p,*q,*s; s=(test*)malloc(m); s->data=x; s->lchild=NULL; s->rchild=NULL; if(!root) {
} root=s; p=root; while(p)/*接入二叉排序树的适当位置*/ { q=p; if(p->data==x) { } else if(x
data) p=p->lchild; printf("Data already exist!\n"); return;
else
p=p->rchild;
} if(xdata) q->lchild=s;
else
}
/*将二叉树叶子结点利用指针rchild生成单链表*/ q->rchild=s;
void PreOrderTraverse(xiaofei *root)//先序遍历二叉树
{
xiaofei *n; n=root; if(!n)return; if(n->lchild==NULL&&n->rchild==NULL){//判断叶子结点并利用指针rchild生成单链表
}
/*查找二叉树第最左边第一个叶子结点*/
xiaofei FinFLea(xiaofei *root)
{
xiaofei *n; n=root; if(n->lchild==NULL&&n->rchild==NULL) {//查找最左边第一个叶子结点,在链表输出时调用 } if(n->lchild) PreOrderTraverse(n->lchild); if(n->rchild) PreOrderTraverse(n->rchild); return; head->rchild=n; head=n; return;
} } if(n->lchild) { } else if(n->rchild) { } return *first; n=n->rchild; FinFLea(n); n=n->lchild; FinFLea(n);
/*递归输出二叉树*/
void printtree(xiaofei *root)
{
}
/*按从左到右的顺序打印叶子结点*/
void printlist(xiaofei *lea)
{ if(root) printf(" %d",root->data); if(root->lchild) printtree(root->lchild); if(root->rchild) printtree(root->rchild);
} n=lea; while(n) {//输出链表 } printf("\n"); return; printf(" %d",n->data); n=n->rchild;
int main() //先生成二叉排序树
{
int i,x; i=1; root=NULL;//赋初值给root do { printf("请输入数据%d:",i); i++; scanf("%d",&x);//从键盘输入数据,以0表示输入结束 if(x==0){ printf("\n输出的数据如下:\n");
} else insert_data(x);//调用插入数据元素的函数 while(x!=0); printf("###################二叉树创建成功###################\n");
数
printf("##########叶子结点按从左到右链成单链表成功printf("----------------------------------------------------\n"); printtree(root);//打印二叉树 printf("\n----------------------------------------------------\n"); FinFLea(root);//调用查找最左边的叶子结点函数 head=(xiaofei *)malloc(sizeof(xiaofei));//申请头结点 PreOrderTraverse(root);//调用将二叉树按从左到右生成单链表函##########\n");
} printlist(first);//打印二叉树叶子结点链表