求用C实现:输入初始关键字序列,构造一个二叉排序树。 谢谢!
不用C++
4条回答 默认 最新
- 江南丨烟雨 2015-06-28 02:47关注
// 二叉树_C.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include "malloc.h" #define MAX 1240 typedef struct bitnode { char data; struct bitnode *lchild,*rchild; }BiTNode,*BiTree; /*初始化*/ BiTree Initiate() { BiTNode *bt; bt=NULL; return bt; } /*生成根节点*/ BiTree Create(char x,BiTree lbt,BiTree rbt) { BiTree p; if((p=(BiTNode *)malloc(sizeof(BiTNode)))==NULL)return NULL; p->data=x; p->lchild=lbt; p->rchild=rbt; return p; } /*添加左节点*/ BiTree InsertL(BiTree bt,char x,BiTree parent) { BiTree p; if(parent==NULL) { printf("\n插入出错!\n"); return NULL; } if((p=(BiTNode *)malloc(sizeof(BiTNode)))==NULL) return NULL; p->data=x; p->lchild=NULL; p->rchild=NULL; if(parent->lchild==NULL) parent->lchild=p; else { p->lchild=parent->lchild; parent->lchild=p; } return bt; } /*添加右节点*/ BiTree InsertR(BiTree bt,char x,BiTree parent) { BiTree p; if(parent==NULL) { printf("\n插入出错!"); return NULL; } if((p=(BiTNode *)malloc(sizeof(BiTNode)))==NULL) return NULL; p->data=x; p->lchild=NULL; p->rchild=NULL; if(parent->rchild==NULL) parent->rchild=p; else { p->rchild=parent->rchild; parent->rchild=p; } return bt; } /*删除左子树*/ BiTree DeleteL(BiTree bt,BiTree parent) { BiTree p; if(parent==NULL||parent->lchild==NULL) { printf("\n删除出错!"); return NULL; } p=parent->lchild; parent->lchild=NULL; free(p); return bt; } /*删除右子树*/ BiTree DeleteR(BiTree bt,BiTree parent) { BiTree p; if(parent==NULL||parent->rchild==NULL) { printf("\n删除出错!"); return NULL; } p=parent->rchild; parent->rchild=NULL; free(p); return bt; } /*访问节点值*/ void Vist(BiTree bt) { printf("%c\t",bt->data); } /*递归前序遍历*/ void PreOrder(BiTree bt) { if(bt==NULL) return; Vist(bt); PreOrder(bt->lchild); PreOrder(bt->rchild); } /*递归中序遍历*/ void InOrder(BiTree bt) { if(bt==NULL) return; InOrder(bt->lchild); Vist(bt); InOrder(bt->rchild); } /*递归后序遍历*/ void PostOrder(BiTree bt) { if(bt==NULL) return; PostOrder(bt->lchild); PostOrder(bt->rchild); Vist(bt); } /*非递归前序遍历*/ void NRPreOrder(BiTree bt) { BiTNode *stack[MAX],*p; int top=-1; //栈初始化为空 if(bt==NULL) return; p=bt; //p指向根结点 while(! (p == NULL && top == -1)) { while(p!=NULL) { Vist(p); top++; stack[top]=p; p=p->lchild; } if(top<0) return; else { p=stack[top]; top--; p=p->rchild; } } } /*非递归中序遍历*/ void NRInOrder(BiTree bt) { BiTNode *stack[MAX],*p; int top=-1; //栈初始化为空 if(bt==NULL) return; p=bt; //p指向根结点 while(! (p == NULL && top == -1)) { while(p!=NULL) { top++; stack[top]=p; p=p->lchild; } if(top<0) return; else { p=stack[top]; Vist(p); top--; p=p->rchild; } } } /*非递归后序遍历*/ void NRPostOrder(BiTree bt) { BiTNode *stack[MAX]; int Frist[MAX]; //判断在栈中的次数,正则第一次,负则第二次 BiTNode *p; int top=-1; //栈初始化为空 if(bt==NULL) return; p=bt; //p指向根结点 while(! (p == NULL && top == -1)) { while(p != NULL) { top++; stack[top]=p; Frist[top]=1; p=p->lchild; } if(top > -1) { if(Frist[top] > 0) { p=stack[top]->rchild; Frist[top]=-Frist[top]; } else { p=stack[top]; top--; Vist(p); p=NULL; } } } } /*层次遍历*/ void LevelOrder(BiTree bt) { BiTNode *Queue[MAX]; int front,rear; if(bt==NULL)return; front=-1; rear=0; Queue[rear]=bt; while(front!=rear) { front++; Vist(Queue[front]); //出队,并取值输出 if(Queue[front]->lchild!=NULL) //入队操作 { rear++; Queue[rear]=Queue[front]->lchild; } if(Queue[front]->rchild!=NULL) { rear++; Queue[rear]=Queue[front]->rchild; } } } int _tmain(int argc, _TCHAR* argv[]) { BiTree t,tr=NULL,tl=NULL; t=Initiate(); t=Create('A',tl,tr); printf("根节点:\n"); PreOrder(t); t=InsertL(t,'B',t); t=InsertR(t,'C',t); t=InsertL(t,'D',t->lchild); t=InsertR(t,'G',t->lchild->lchild); t=InsertL(t,'E',t->rchild); t=InsertR(t,'F',t->rchild); printf("\n二叉树遍历情况如下:\n"); printf("递归法前序遍历: "); PreOrder(t); printf("\n"); printf("非递归法前序遍历:"); NRPreOrder(t); printf("\n"); printf("\n"); printf("递归法中序遍历: "); InOrder(t); printf("\n"); printf("非递归法中序遍历:"); NRInOrder(t); printf("\n"); printf("\n"); printf("递归法后序遍历: "); PostOrder(t); printf("\n"); printf("非递归法中序遍历:"); NRPostOrder(t); printf("\n"); printf("\n"); printf("层次遍历: "); LevelOrder(t); printf("\n"); //printf("\n删除后的为:\n"); //t=DeleteL(t,t->lchild); //printf("前序遍历:"); //PreOrder(t); return 0; }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥50 永磁型步进电机PID算法
- ¥15 sqlite 附加(attach database)加密数据库时,返回26是什么原因呢?
- ¥88 找成都本地经验丰富懂小程序开发的技术大咖
- ¥15 如何处理复杂数据表格的除法运算
- ¥15 如何用stc8h1k08的片子做485数据透传的功能?(关键词-串口)
- ¥15 有兄弟姐妹会用word插图功能制作类似citespace的图片吗?
- ¥200 uniapp长期运行卡死问题解决
- ¥15 latex怎么处理论文引理引用参考文献
- ¥15 请教:如何用postman调用本地虚拟机区块链接上的合约?
- ¥15 为什么使用javacv转封装rtsp为rtmp时出现如下问题:[h264 @ 000000004faf7500]no frame?