写在前面：
今天我们开始进入树的学习啦，在学习高级搜索树之前，我们先看看一些简单树的实现，先理解好概念，入门就很快了。另外，本讲将会为大家介绍双亲表示法、孩子表示法和孩子兄弟表示法的代码实现。

树的定义

之前我们学习的是线性表，也就是线性的存储结构。今天我们开始学习非线性的存储结构，树就是非线性的存储结构，它可以拥有一对多的元素。在学习代码之前，我们先弄明白下面这几个定义：
结点： 使用树结构存储的每⼀个数据元素都被称为“结点”。

根结点： 有⼀个特殊的结点，这个结点没有前驱，我们将这种结点称之为根结点。

父结点（双亲结点）、子结点和兄弟结点：

叶子结点： 如果⼀个结点没有任何子结点，那么此结点就称之为叶子结点。

结点的度： 结点拥有的子树的个数，就称之为结点的度。
树的度： 在各个结点当中，度的最大值为树的度。
树的深度或者高度： 结点的层次从根结点开始定义起，根为第一层，根的孩子为第二层，依次类推。

双亲表示法

我们可以定义一个结点的结构体，用来保存数据以及它的父节点的下标，并且定义根结点的父节点下标为-1，然后用一个结构体数组来储存所有的结点。

代码实现

#include<bits/stdc++.h>
using namespace std;

//树结点的结构体定义
struct tree_node {
    int data;    //数据
    int parent;    //该结点的父亲结点
};

tree_node* Node[5];        //结构体数组，存放结点
int Size;                //当前树的结点个数
int maxSize;            //树的最大结点个数

void init_tree();
void root_insert(int);
void child_insert(int,int);
int find_node(int);

int main() {
    init_tree();
    root_insert(1);
    child_insert(2, 1);
    child_insert(3, 1);
    child_insert(4, 2);
    cout << Node[0]->data << " " << Node[0]->parent<< endl;
    cout << Node[1]->data << " " << Node[1]->parent << endl;
    cout << Node[3]->data << " " << Node[3]->parent << endl;
}

//树的初始化
void init_tree() {
    Size = 0;
    maxSize = 5;
}

//创建根结点
void root_insert(int key) {
    if (Size != 0) {
        cout << "已经创建根节点！" << endl;
        return;
    }
    tree_node* root_node = new tree_node;
    root_node->data = key;
    root_node->parent = -1;
    Node[Size++] = root_node;
}

//孩子结点的插入
void child_insert(int key, int parent) {
    if (Size == 0) {
        cout << "请先创建根节点" << endl;
    }
    else if (Size == maxSize) {
        cout << "节点数已满" << endl;
    }
    else {
        int parent_index = find_node(parent);    //判断是否有该父节点
        if (parent_index == -1) {
            cout << "没有该父节点" << endl;
        }
        else {
            tree_node* child_node = new tree_node;
            child_node->data = key;
            child_node->parent = parent_index;
            Node[Size++] = child_node;
        }
    }
}

//寻找结点
int find_node(int parent) {
    for (int i = 0; i < Size; i++) {
        if (parent == Node[i]->data) {
            return Node[i]->data;
        }
    }
    return -1;
}

优缺点

我们可以通过每个结点parent的值，快速访问其双亲结点。但是如果想知道每个结点的孩子结点，就需要全部遍历一遍，非常麻烦。

孩子表示法

孩子表示法同样用一个数组来保存所有结点，但是每个结点不再是存储父结点的下标，而是定义一个指针，将该结点的所有孩子连起来：

代码实现

#include <bits/stdc++.h>
using namespace std;

//树结点的结构体定义
struct tree_node {
    int data;            //存储数据
    tree_node *next;    //用链表将该结点的所有孩子串起来
};

int Size;                //当前树的结点数量
tree_node *Node[8];        //存储结点的数组

void init_node(int);
void child_insert(int, int);
int find_node(int);

int main() {
    init_node(1);
    child_insert(4, 1);
    child_insert(5, 1);
    child_insert(6, 4);
    child_insert(3, 4);
    child_insert(7, 3);
    for (int i = 0; i < Size; i++) {
        cout << "父节点为" << Node[i]->data;
        tree_node *temp_node = Node[i];
        while (temp_node->next != NULL) {
            temp_node = temp_node->next;
            cout << " 孩子节点为" << temp_node->data;
        }
        cout << endl;
    }
}

//初始化树
void init_node(int key) {
    tree_node *new_node = new tree_node;
    new_node->data = key;
    new_node->next = NULL;
    Size = 0;
    Node[Size] = new_node;
    Size++;
}

//插入孩子结点
void child_insert(int key, int parent) {
    if (Size == 0) {
        cout << "请先创建根节点" << endl;
    } else {
        Node[Size] = new tree_node;
        Node[Size]->data = key;
        Node[Size]->next = NULL;
        Size++;
        int index = find_node(parent);    //寻找父结点在数组中的下标
        if (index == -1) {
            cout << "未找到该父节点" << endl;
        } else {
            tree_node *new_node = new tree_node;
            new_node->data = key;
            new_node->next = Node[index]->next;    //将插入结点的next指向父结点的下个结点
            Node[index]->next = new_node;    //将父结点的next指向该插入结点
        }
    }
}

//找到该结点位置
int find_node(int parent) {
    for (int i = 0; i < Size; i++) {
        if (Node[i]->data == parent) {
            return i;
        }
    }
    return -1;
}

孩子兄弟表示法

孩子表示法需要用数组来存储结点，如果不用数组的话，我们可以在定义结点结构体时，多定义一个指向兄弟的指针，用来连接与该结点同级的结点。

全部代码

#include<bits/stdc++.h>
using namespace std;

struct tree_node {
    int data;
    tree_node* child;
    tree_node* sibling;
};

tree_node* root_node = NULL;    //根结点
tree_node* temp_node = NULL;    //临时节点，方便从根节点开始遍历
void root_init(int);
void child_insert(int, int);
void find_node(tree_node*, int);
void show(tree_node* root_node);

int main() {
    root_init(1);
    child_insert(2, 1);
    child_insert(3, 1);
    child_insert(4, 2);
    child_insert(6, 4);
    show(root_node);
}

//遍历树
void show(tree_node* root_node)
{
    if (root_node == NULL)
        return;
    cout << root_node->data << " ";
    show(root_node->sibling);
    show(root_node->child);
}

//根结点初始化
void root_init(int key) {
    root_node = new tree_node;
    root_node->data = key;
    root_node->child = NULL;
    root_node->sibling = NULL;
}

//插入孩子结点
void child_insert(int key, int parent) {
    if (root_node == NULL) {
        cout << "请先创建根节点" << endl;
    }
    else {
        temp_node = NULL;    //用临时指针找到父结点
        find_node(root_node, parent);    //找到父结点的位置
        if (temp_node == NULL) {
            cout << "未找到该父节点" << endl;
        }
        else {
            tree_node* new_node = new tree_node;
            new_node->data = key;
            new_node->sibling = temp_node->child;    //将该结点的兄弟指向父结点的孩子（如果没有就指向空）
            new_node->child = NULL;
            temp_node->child = new_node;    //将父结点的孩子指向该结点
        }
    }
}

//找到该结点的位置
void find_node(tree_node* node, int parent) {
    //如果找到该结点，就将临时指针指向它
    if (node->data == parent) {
        temp_node = node;
    }
    else {
        //先查看结点的兄弟
        if (node->sibling != NULL) {
            find_node(node->sibling, parent);
        }
        //再查看结点的孩子
        if (node->child != NULL) {
            find_node(node->child, parent);
        }
    }
}

如果大家有什么问题的话，欢迎在下方评论区进行讨论哦~