写在前面：
今天我们开始进入树的学习啦，在学习高级搜索树之前，我们先看看一些简单树的实现，先理解好概念，入门就很快了。另外，本讲将会为大家介绍双亲表示法、孩子表示法和孩子兄弟表示法的代码实现。
树的定义
之前我们学习的是线性表，也就是线性的存储结构。今天我们开始学习非线性的存储结构，树就是非线性的存储结构，它可以拥有一对多的元素。在学习代码之前，我们先弄明白下面这几个定义：
结点： 使用树结构存储的每⼀个数据元素都被称为“结点”。
根结点： 有⼀个特殊的结点，这个结点没有前驱，我们将这种结点称之为根结点。
父结点（双亲结点）、子结点和兄弟结点：
叶子结点： 如果⼀个结点没有任何子结点，那么此结点就称之为叶子结点。
结点的度： 结点拥有的子树的个数，就称之为结点的度。
树的度： 在各个结点当中，度的最大值为树的度。
树的深度或者高度： 结点的层次从根结点开始定义起，根为第一层，根的孩子为第二层，依次类推。
双亲表示法
我们可以定义一个结点的结构体，用来保存数据以及它的父节点的下标，并且定义根结点的父节点下标为-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);
}
}
}如果大家有什么问题的话，欢迎在下方评论区进行讨论哦~
