来自 技术 2019-04-17 的文章

树的基本操作(连载中) - 陈述v

树是一种一对多的非线性数据结构,可以利用顺序存储结构来存储数据,也可以利用链式结构来存储数据。

考虑到空间问题以及实用性,这里利用链式结构来存储数据。

这里由于笔者的题目输入格式是这样的:

每个输入文件包含一个测试用例。对于每种情况,第一行给出正整数N(≤10),它是树中节点的总数 - 因此节点从0到N-1编号。然后是N行,每行对应一个节点,并给出节点左右子节点的索引。如果孩子不存在,将在该位置放置“ - ”。任何一对孩子都被一个空间隔开。输入样例:

81 -- -0 -2 7- -- -5 -4 6

所以后面的基本操作就以这种输入格式为基础啦。


1.树节点的定义

typedef char datatype;typedef struct node{//定义节点 datatype data; struct node *lchild, *rchild;}node;


2.树的初始化

//创建树 //传入数据:树的节点个数,头指针//传出数据:根节点下标,指向根节点的头指针void create_tree(int num, int *mark, node *&head){ int i; datatype data, left, right; node *h[num];//指针数组,指向树节点 int root[num] = {0};//root[]数组初始化为0 for(i=0; i<num; i++){ h[i] = new node;//给树节点申请空间 h[i]->lchild = h[i]->rchild = NULL; } for(i=0; i<num; i++){ cin>>data>>left>>right; int l, r; h[i]->data = data; if(left != '-'){ l = left-48;//转化为int类型 h[i]->lchild = h[l]; root[l] = 1;//表示如果h[l]有双亲,root[l] = 1 } if(right != '-'){ r = right-48; h[i]->rchild = h[r]; root[r] = 1; } } //扫描root[]数组,root[i] == 0 时,i为根节点下标 for(i=0; i<num; i++){ if(root[i] == 0){ *mark = i; break; } } head = h[*mark];//头指针指向根节点 }


3. 判断是否为叶节点(是返回1,否返回0)

bool is_leave(node *n)//判断是否为叶节点:是返回1,否返回0 { if(n->lchild == NULL && n->rchild == NULL){ return true; }else{ return false; }}


4.前序遍历(根左右)

这里是递归版本

void preorder(node *head)//前序遍历树{ node *i; i = head; if(i != NULL){ cout<< i->data<<endl; } preorde(i->lchild); preorde(i->rchild); } }


标签:   linux 纯命令行系统      Global变量   
上一篇:PostgreSQL 源码解读(168)- 查询#88(PG中的词法定义
下一篇:没有了