http://bbs.csdn.net/topics/340042324
搜遍了google搜索的所有文章
第14页终于让哥找到了这个方法:
/*
这是一个在字符环境中,用ASCII码打印二叉树形状的算法。
在Linux控制台下写的例题,在DOS中稍有点乱。
采用层次遍法。
算法拙劣,仅供初学者做练习,(本人也是初学者,自学数据结构,刚好学到这二叉树这一章,
半路出家,基础差有点吃力头大,搞几个二叉的例题,却不知道其构造形状,
想调用图形API做个美观点的,却有点偏离本章的学习目的,只好用字符打印,
linux环境中打印的还可以,DOS中有点不稳定,如果您有更好的算法一定不吝赐教。
我的QQ:137241638 mail:hnflcp@139.com
*/
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100
//Pstart是二叉树根结点在一行中的位置,一行最能打印124个字符,取其1/2。
//如果你的屏不够宽的话,可以输出文本文件里, aa.exe>>aa.txt
#define Pstart 62
typedef struct node //二叉树存储结构
{
int key;
int data;
struct node *lchild,
*rchild;
}BTNode;
typedef struct pnode //为打印二叉树建了一个结构。
{
int key; //关键字数据1
int data; //关键字数据2
struct pnode *lchild, //左孩子
*rchlid, //右孩子
*parent; //父节点
int lrflag, //标记本节点是左孩子(等于0时),还是右孩子(等于1时)
space, //存储本节点打印位置
level; //存储本节点所在层次。
}PBTNode;
/*建立二叉树。
用括号表示法表示二叉树字符串,创建二叉树。
*/
BTNode* CreateBTNode(char *s)
{
char ch;
BTNode *p=NULL,
*b=NULL,
*ps[MaxSize];
int top=-1,
tag=-1;
ch=*s;
while(ch)
{
switch(ch)
{
case '(':ps[++top]=p;tag=1;break;
case ',':tag=2;break;
case ')':top--;break;
default:
p=(BTNode*)malloc(sizeof(BTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
if(b==NULL)
b=p;
else
{
switch(tag)
{
case 1:ps[top]->lchild=p;break;
case 2:ps[top]->rchild=p;break;
}
}
}
ch=*(++s);
}
return b;
}
//用适号表示法打印二叉树。
void DispBTNode(BTNode *b)
{
if(b!=NULL)
{
printf("%c",b->data);
if(b->lchild!=NULL||b->rchild!=NULL)
{
printf("(");
DispBTNode(b->lchild);
if(b->rchild!=NULL)printf(",");
DispBTNode(b->rchild);
printf(")");
}
}
}
int BTNodeHeight(BTNode *b)
{
int lchildh,rchildh;
if(b==NULL)return 0;
else
{
lchildh=BTNodeHeight(b->lchild);
rchildh=BTNodeHeight(b->rchild);
return (lchildh>rchildh)?(lchildh+1):(rchildh+1);
}
}
/*建立一个二叉树打印结点的信息,
只被int CreatePBTNode(BTNode *b,PBTNode *pqu[])调用*/
void SetPBTNodeInfo(BTNode *b,PBTNode *parent,PBTNode *pb,int level,int lrflag)
{
int f=3;
pb->data=b->data;
pb->key =b->key;
pb->parent=parent;
pb->level=level;
pb->lrflag=lrflag;
pb->space=-1;
}
/*用层次遍历法,BTNode结构存储的二叉树转换为,PBTNode结构的二叉树*/
int CreatePBTNode(BTNode *b,PBTNode *pqu[])
{
BTNode *p;
BTNode *qu[MaxSize];
int front=-1,
rear=-1;
rear++;
qu[rear]=b;
pqu[rear]=(PBTNode*)malloc(sizeof(PBTNode));
SetPBTNodeInfo(b,NULL,pqu[rear],1,-1);
while(rear!=front)
{
front++;
p=qu[front];
if(p->lchild!=NULL)
{
rear++;
qu[rear]=p->lchild;
pqu[rear]=(PBTNode*)malloc(sizeof(PBTNode));
SetPBTNodeInfo(p->lchild,pqu[front],pqu[rear],pqu[front]->level+1,0);
}
if(p->rchild!=NULL)
{
rear++;
qu[rear]=p->rchild;
pqu[rear]=(PBTNode*)malloc(sizeof(PBTNode));
SetPBTNodeInfo(p->rchild,pqu[front],pqu[rear],pqu[front]->level+1,1);
}
}
return rear;
}
//打印一层结点,及该层结点与父结点的连线路径。
void PBTNodePrint(PBTNode *pb[],int n,int h)
{
int l=-1,
r=0,
i,j,k,
end;
char c;
PBTNode *p;
if(n<=0||h<=0)
{
return;
}
else if(n==1)
{
for(i=0;i<pb[0]->space;i++)
printf(" ");
printf("%c",pb[0]->data);
printf("\n");
return;
}
h=h-pb[0]->level+2;
for(k=0;k<h;k++)
{
j=0;
l--;
r++;
for(i=0;i<n;i++)//打印线条
{
p=pb[i];
end=(p->lrflag==0)?l:r;
end+=p->parent->space;
for(;j<end;j++)
printf(" ");
c=(p->lrflag==0)?'/':'\\';
printf("%c",c);
}
printf("\n");
}
for(i=0;i<n;i++)//计算本层结点打印位置
{
p=pb[i];
if(p->lrflag==0)
p->space=p->parent->space+l;
else
p->space=p->parent->space+r;
}
for(i=0,j=0;i<n;i++)//打印关键字数据
{
p=pb[i];
for(;j<p->space;j++)
printf(" ");
printf("%c",p->data);
}
printf("\n");
}
//循环打印所有层的数据
void DispBTree(BTNode *b)
{
int n,i,j,high,
level;
PBTNode *p;
PBTNode *pqu[MaxSize];
PBTNode *levelpqu[MaxSize];
n=CreatePBTNode(b,pqu);
high=BTNodeHeight(b);
j=0;
level=1;
pqu[0]->space=Pstart;
for(i=0;i<=n;i++)
{
p=pqu[i];
if(p->level==level)
{
levelpqu[j]=p;
j++;
}
else
{
PBTNodePrint(levelpqu,j,high);
level=p->level;
j=0;
levelpqu[j]=p;
j++;
}
}
PBTNodePrint(levelpqu,j,high);
}
void main()
{
int iDepth=0,
iWidth=0,
iCount=0;
char *str1="A(B(D,E(H,X(J,K(L,M(T,Y))))),C(F,G(X,I)))";
char *str2="A(B(D(,G)),C(E,F))";
BTNode *b=CreateBTNode(str1);
DispBTNode(b);printf("\n");
iDepth=BTNodeHeight(b);
printf("Depth:%d\n",iDepth);
DispBTree(b);
}
- 大小: 28.9 KB
分享到:
相关推荐
平衡二叉树-红黑树的实现
数据结构 树、二叉树、红黑树、堆、图等结构教程
数据结构 和算法分析 二叉树、红黑树、堆、图等数据结构
高级数据结构代码 红黑树 二叉树 B树
描述了红黑树的基本结构 以及与二叉树的性能比较
该生成器可以根据用户的要求生成任何用户所需要的类型的二叉树
2,为什么索引结构默认使用B+Tree,而不是Hash,二叉树,红黑树? 3、MySQL里记录货币用什么字段类型好 4、数据库自增主键可能遇到什么问题。 5、从锁的类别角度讲,MySQL都有哪些锁呢? 6、索引失效情况? 7、优化...
talerbtree红黑树二叉树.zip
红黑树的本质是二叉树,二叉树在插入元素的时候是根据关键字(可以理解为用来识别每个节点的id,一般是hash 来判断)的大小来判断插入到哪一个分支的,如下图所示: (备注:大写字母代表每个节点相当于每个节点的...
红黑树&二叉树
B树和二叉树的区别:二叉树最多能有两个子节点;B树最多只能有M个子节点,最少有三个子节点 三、B+树 介绍:B+树是B树的升级版本,就目前情况,绝大部分都已经用B+树代替了B树了,文件管理、索引等等 四、红黑树 ...
红黑树是一种特化的AVL树(平衡二叉树),都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。 它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的:...
主要实现有普通树的生成、查询方法,与继承于普通树的二叉树、红黑树的实现。
二叉树 非递归实现 数据结构 c++ 广度遍历,非递归实现广度遍历生成二叉树。 数据结构与算法上机作业。
1按先序次序输入二叉树中结点的值(一个字符),`0`表示空树,生成二叉树的二叉链表存储结构。然后按中序和后序顺序遍历二叉树输出结果。
这是一个关于二叉树的代码,演示了红黑树的数据结构。仅供大家学习和参考!
26红黑树 27红黑树_0 28红黑树_1 29红黑树_2 30红黑树_3 31红黑树_4 32红黑树_5 33红黑树_6 34堆 35堆排序 36哈希与映射的概述 37B树有什么用 38B树的概念 39图_邻接矩阵 40图_邻接表 41图_DFS 42图_BFS
26红黑树 27红黑树_0 28红黑树_1 29红黑树_2 30红黑树_3 31红黑树_4 32红黑树_5 33红黑树_6 34堆 35堆排序 36哈希与映射的概述 37B树有什么用 38B树的概念 39图_邻接矩阵 40图_邻接表 41图_DFS 42图_BFS
用先序生成二叉树,然后按先序,中序,后序和层次对二叉树进行排序
使用java语言编程实现了平衡二叉树、二叉树、二叉搜索树、红黑树四种树相关的数据结构,还实现了多种排序算法。并且是在J2EE下实现的。