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

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

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 

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

每个输入文件包含一个测试用例。
对于每种情况，第一行给出正整数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, 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);
    }
        
}

 

 

 

 

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄