当前位置：首页 > news >正文

树数据结构

news 2025/7/27 21:51:32

什么是树数据结构？

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

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

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

递归定义：

一棵树由一个根和零个或多个子树 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