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