树是一种一对多的非线性数据结构，可以利用顺序存储结构来存储数据，也可以利用链式结构来存储数据。
考虑到空间问题以及实用性，这里利用链式结构来存储数据。
这里由于笔者的题目输入格式是这样的：
每个输入文件包含一个测试用例。
对于每种情况，第一行给出正整数N（≤10），它是树中节点的总数 - 因此节点从0到N-1编号。
然后是N行，每行对应一个节点，并给出节点左右子节点的索引。
如果孩子不存在，将在该位置放置“ - ”。
任何一对孩子都被一个空间隔开。
输入样例：
8
1 -
- -
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; datatype left, right; if(num == 0){ head = NULL; *mark = -1; return; } node *h[num]; int root[num] = {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; } if(right != '-'){ r = right-48; h[i]->rchild = h[r]; root[r] = 1; } } 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.求树的深度（递归）
int get_depth(node *head)//得到树的深度 { if(head == NULL){ return 0; }else{ int left_depth = get_depth(head->lchild); int right_depth = get_depth(head->rchild); return (left_depth>right_depth?left_depth:right_depth) +1; } }
5.前序遍历（根左右）
这里是递归版本
void preorder(node *head)//前序遍历树 { node *i; i = head; if(i != NULL){ cout<< i->data<<endl; } preorde(i->lchild); preorde(i->rchild); } }
6.判断树的同构（递归）
bool compare(node *heada, node *headb)//比较两棵树 { if(get_depth(heada) != get_depth(headb)){//树的节点数不相同 return 0; } if(heada == NULL && headb == NULL){//两棵树为空树 return 1; } if(heada->data != headb->data){//节点数据不等 return 0; } return (compare(heada->lchild, headb->lchild) && compare(heada->rchild, headb->rchild) ||compare(heada->rchild, headb->lchild) && compare(heada->lchild, headb->rchild)); }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
