树数据结构

什么是树数据结构？

树数据结构是一种层次结构，用于以易于导航和搜索的方式表示和组织数据。它是由边连接的节点集合，节点之间具有层次关系。树的最顶端的节点称为根，它下面的节点称为子节点。每个节点可以有多个子节点，这些子节点也可以有自己的子节点，形成递归结构。

这种数据结构是在计算机中组织和存储数据以便更有效地使用的专门方法。它由中心节点、结构节点和子节点组成，它们通过边连接。我们也可以说树数据结构具有相互连接的根、枝和叶。 

树入门——数据结构与算法教程

递归定义： 

一棵树由一个根和零个或多个子树 T 1 , T 2 , … , T k组成，这样从树的根到每个子树的根都有一条边。

 

为什么 Tree 被认为是非线性数据结构？

树中的数据不是按顺序存储的，即它们不是线性存储的。相反，它们被安排在多个层次上，或者我们可以说它是一个层次结构。因此，树被认为是一种非线性数据结构。

树数据结构中的基本术语：

• 父节点：节点的前身节点称为该节点的父节点。{B}是{D, E}的父节点。
• 子节点：节点的直接后继节点称为该节点的子节点。例子：{D, E}是{B}的子节点。
• 根节点：树的最顶端节点或没有任何父节点的节点称为根节点。{A }是树的根节点。一棵非空树必须恰好包含一个根节点和从根到树的所有其他节点的恰好一条路径。
• 叶节点或外部节点：没有任何子节点的节点称为叶节点。{K, L, M, N, O, P}是树的叶节点。
• 节点的祖先：根节点到该节点的路径上的任何前任节点称为该节点的祖先。{A,B}是节点{E}的祖先节点
• 后代：从叶节点到该节点的路径上的任何后继节点。{E,I}是节点 {B} 的后代。
• 兄弟节点：同一个父节点的子节点称为兄弟节点。{D,E}称为兄弟姐妹。
• 节点级别：从根节点到该节点的路径上的边数。根节点的级别为0。
• 内部节点：至少有一个子节点的节点称为内部节点。
• 节点的邻居：该节点的父节点或子节点称为该节点的邻居。
• 子树：树的任何节点及其后代。

树的属性：

• 边数：边可以定义为两个节点之间的连接。如果一棵树有 N 个节点，那么它将有 (N-1) 条边。从每个节点到树的任何其他节点只有一条路径。
• 节点深度：节点深度定义为从根节点到该节点的路径长度。每条边为路径增加 1 个长度单位。因此，它也可以定义为从树的根到节点的路径中的边数。
• 节点的高度：节点的高度可以定义为从该节点到树的叶节点的最长路径的长度。
• 树的高度：树的高度是从树的根到树的叶节点的最长路径的长度。
• 节点的度：连接到该节点的子树的总数称为该节点的度。叶节点的度数必须为0。树的度是树中所有节点中节点的最大度。

还有一些属性是：

• 在树中遍历是通过深度优先搜索和广度优先搜索算法完成的。
• 它没有回路也没有电路
• 它没有自循环 
• 它的层次模型。

句法：

struct Node
{
   int data;
   struct Node *left_child;
   struct Node *right_child;
};

树的基本操作：

创建——在数据结构中创建一棵树。
Insert - 在树中插入数据。
Search - 在树中搜索特定数据以检查它是否存在。
Preorder Traversal – 在数据结构中以预序方式执行树的遍历。
In order Traversal——按顺序遍历树。
后序遍历——以后序方式执行树的遍历。

树数据结构示例

 

这里，

节点1是根节点

1 是 2 和 3 的父级

2和3是兄弟姐妹

4、5、6、7为叶节点

1和2是5的祖先

// C++ program to demonstrate some of the above
// terminologies
#include <bits/stdc++.h>
using namespace std;
// Function to add an edge between vertices x and y
void addEdge(int x, int y, vector<vector<int> >& adj)
{adj[x].push_back(y);adj[y].push_back(x);
}
// Function to print the parent of each node
void printParents(int node, vector<vector<int> >& adj,int parent)
{// current node is Root, thus, has no parentif (parent == 0)cout << node << "->Root" << endl;elsecout << node << "->" << parent << endl;// Using DFSfor (auto cur : adj[node])if (cur != parent)printParents(cur, adj, node);
}
// Function to print the children of each node
void printChildren(int Root, vector<vector<int> >& adj)
{// Queue for the BFSqueue<int> q;// pushing the rootq.push(Root);// visit array to keep track of nodes that have been// visitedint vis[adj.size()] = { 0 };// BFSwhile (!q.empty()) {int node = q.front();q.pop();vis[node] = 1;cout << node << "-> ";for (auto cur : adj[node])if (vis[cur] == 0) {cout << cur << " ";q.push(cur);}cout << endl;}
}
// Function to print the leaf nodes
void printLeafNodes(int Root, vector<vector<int> >& adj)
{// Leaf nodes have only one edge and are not the rootfor (int i = 1; i < adj.size(); i++)if (adj[i].size() == 1 && i != Root)cout << i << " ";cout << endl;
}
// Function to print the degrees of each node
void printDegrees(int Root, vector<vector<int> >& adj)
{for (int i = 1; i < adj.size(); i++) {cout << i << ": ";// Root has no parent, thus, its degree is equal to// the edges it is connected toif (i == Root)cout << adj[i].size() << endl;elsecout << adj[i].size() - 1 << endl;}
}
// Driver code
int main()
{// Number of nodesint N = 7, Root = 1;// Adjacency list to store the treevector<vector<int> > adj(N + 1, vector<int>());// Creating the treeaddEdge(1, 2, adj);addEdge(1, 3, adj);addEdge(1, 4, adj);addEdge(2, 5, adj);addEdge(2, 6, adj);addEdge(4, 7, adj);// Printing the parents of each nodecout << "The parents of each node are:" << endl;printParents(Root, adj, 0);// Printing the children of each nodecout << "The children of each node are:" << endl;printChildren(Root, adj);// Printing the leaf nodes in the treecout << "The leaf nodes of the tree are:" << endl;printLeafNodes(Root, adj);// Printing the degrees of each nodecout << "The degrees of each node are:" << endl;printDegrees(Root, adj);return 0;
}

 

 

The parents of each node are:
1->Root
2->1
5->2
6->2
3->1
4->1
7->4
The children of each node are:
1-> 2 3 4 
2-> 5 6 
3-> 
4-> 7 
5-> 
6-> 
7-> 
The leaf nodes of the tree are:
3 5 6 7 
The degrees of each node are:
1: 3
2: 2
3: 0
4: 1
5: 0
6: 0
7: 0

树数据结构的类型

不同类型的树数据结构如下：

1.一般树

一般的树数据结构对节点数没有限制。这意味着父节点可以有任意数量的子节点。  

2.二叉树  

二叉树的一个节点最多可以有两个子节点。在给定的树图中，节点 B、D 和 F 是左孩子，而 E、C 和 G 是右孩子。  

3.平衡树

如果左子树和右子树的高度相等或最多相差1，则该树称为平衡树。  

 

4.二叉搜索树

顾名思义，二叉搜索树用于各种搜索和排序算法。示例包括 AVL 树和红黑树。它是一种非线性数据结构。它表明左节点的值小于其父节点，而右节点的值大于其父节点。

树数据结构的应用：

树型数据结构的应用如下：

1. 生成树：它是路由器中用于将数据包定向到目的地的最短路径树。  

2. 二叉搜索树：它是一种树状数据结构，有助于维护已排序的数据流。  

1. 满二叉树
2. 完全二叉树
3. 偏二叉树
4. 严格二叉树
5. 扩展二叉树

3.分层存储数据：树型数据结构用于存储分层数据，即数据以顺序的形式排列。  

4. 语法树：语法树表示程序源代码的结构，在编译器中使用。  

5. Trie：它是一种快速有效的动态拼写检查方法。它还用于从集合中定位特定键。  

6、堆：也是一种树型数据结构，可以用数组的形式来表示。它用于实现优先级队列。

7. 人工智能：决策树和其他基于树的模型常用于机器学习和人工智能中，以进行预测和数据分类。 

8. 数据库：一些数据库使用树来组织数据以进行高效的搜索和排序。

9. 网络：网络的路由算法，例如 Internet 协议 (IP) 路由，使用树来找到数据从一个网络传输到另一个网络的最佳路径。

 树数据结构的优点

• 高效的插入、删除和搜索操作。
• 树在可以存储的数据类型方面具有灵活性。
• 它用于表示层次关系。
• 它具有表示递归结构的能力。
• 用于各种算法和数据结构，如霍夫曼编码和决策树。
• 与其他数据结构（如列表和链表）相比，树使用的空间更少。
• 树木本质上是动态的。
• 树数据结构可以在添加或删除新数据时自动自组织，这可以提高性能并降低复杂性。