树： 与线性数据结构的数组、链表、堆栈和队列不同，树是分层数据结构。 树词汇： 最顶端的节点称为树的根。元素正下方的元素称为其子元素。直接位于某物上方的元素称为其父元素。例如，“a”是“f”的子代，“f”是“a”的父代。最后，没有子元素的元素称为叶子。
null
tree ---- j <-- root / f k / a h z <-- leaves
为什么是树？ 1. 使用树的一个原因可能是，您希望存储自然形成层次结构的信息。例如，计算机上的文件系统：
file system----------- / <-- root / ... home / ugrad course / / | ... cs101 cs112 cs113
2. 树（带有一些顺序，例如BST）提供适度的访问/搜索（比链表快，比数组慢）。 3. 树提供适度的插入/删除（比数组快，比无序链表慢）。 4. 与链表和数组不同，树对节点数没有上限，因为节点是使用指针链接的。 树木的主要用途包括： 1. 操纵分层数据。 2. 使信息易于搜索（请参见树遍历）。 3. 操作已排序的数据列表。 4. 作为合成数字图像以获得视觉效果的工作流。 5. 路由器算法 6. 多阶段决策的形式（参见商业国际象棋）。 二叉树： 元素最多有两个子元素的树称为二叉树。由于二叉树中的每个元素只能有两个子元素，我们通常将它们命名为左和右子元素。 C语言中的二叉树表示法： 树由指向树中最顶端节点的指针表示。如果树为空，则root的值为NULL。 树节点包含以下部分。 1.数据 2.指向左孩子的指针 3.指向正确孩子的指针 在C语言中，我们可以使用结构来表示树节点。下面是一个包含整数数据的树节点示例。
C++
struct node { int data; struct node* left; struct node* right; }; |
python
# A Python class that represents an individual node # in a Binary Tree class Node: def __init__( self ,key): self .left = None self .right = None self .val = key |
JAVA
/* Class containing left and right child of current node and key value*/ class Node { int key; Node left, right; public Node( int item) { key = item; left = right = null ; } } |
C#
/* Class containing left and right child of current node and key value*/ class Node { int key; Node left, right; public Node( int item) { key = item; left = right = null ; } } |
Javascript
<script> /* Class containing left and right child of current node and key value*/ class Node { constructor(item) { this .key = item; this .left = this .right = null ; } } // This code is contributed by umadevi9616 </script> |
C语言中的第一棵简单树 让我们在C中创建一个包含4个节点的简单树。
tree ---- 1 <-- root / 2 3 / 4
C++
#include <bits/stdc++.h> using namespace std; struct Node { int data; struct Node* left; struct Node* right; // val is the key or the value that // has to be added to the data part Node( int val) { data = val; // Left and right child for node // will be initialized to null left = NULL; right = NULL; } }; int main() { /*create root*/ struct Node* root = new Node(1); /* following is the tree after above statement 1 / NULL NULL */ root->left = new Node(2); root->right = new Node(3); /* 2 and 3 become left and right children of 1 1 / 2 3 / / NULL NULL NULL NULL */ root->left->left = new Node(4); /* 4 becomes left child of 2 1 / 2 3 / / 4 NULL NULL NULL / NULL NULL */ return 0; } |
C
#include <stdio.h> #include <stdlib.h> struct node { int data; struct node* left; struct node* right; }; /* newNode() allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode( int data) { // Allocate memory for new node struct node* node = ( struct node*) malloc ( sizeof ( struct node)); // Assign data to this node node->data = data; // Initialize left and // right children as NULL node->left = NULL; node->right = NULL; return (node); } int main() { /*create root*/ struct node* root = newNode(1); /* following is the tree after above statement 1 / NULL NULL */ root->left = newNode(2); root->right = newNode(3); /* 2 and 3 become left and right children of 1 1 / 2 3 / / NULL NULL NULL NULL */ root->left->left = newNode(4); /* 4 becomes left child of 2 1 / 2 3 / / 4 NULL NULL NULL / NULL NULL */ getchar (); return 0; } |
JAVA
/* Class containing left and right child of current node and key value*/ class Node { int key; Node left, right; public Node( int item) { key = item; left = right = null ; } } // A Java program to introduce Binary Tree class BinaryTree { // Root of Binary Tree Node root; // Constructors BinaryTree( int key) { root = new Node(key); } BinaryTree() { root = null ; } public static void main(String[] args) { BinaryTree tree = new BinaryTree(); /*create root*/ tree.root = new Node( 1 ); /* following is the tree after above statement 1 / null null */ tree.root.left = new Node( 2 ); tree.root.right = new Node( 3 ); /* 2 and 3 become left and right children of 1 1 / 2 3 / / null null null null */ tree.root.left.left = new Node( 4 ); /* 4 becomes left child of 2 1 / 2 3 / / 4 null null null / null null */ } } |
python
# Python program to introduce Binary Tree # A class that represents an individual node in a # Binary Tree class Node: def __init__( self ,key): self .left = None self .right = None self .val = key # create root root = Node( 1 ) ''' following is the tree after above statement 1 / None None''' root.left = Node( 2 ); root.right = Node( 3 ); ''' 2 and 3 become left and right children of 1 1 / 2 3 / / None None None None''' root.left.left = Node( 4 ); '''4 becomes left child of 2 1 / 2 3 / / 4 None None None / None None''' |
C#
// A C# program to introduce Binary Tree using System; /* Class containing left and right child of current node and key value*/ public class Node { public int key; public Node left, right; public Node( int item) { key = item; left = right = null ; } } public class BinaryTree { // Root of Binary Tree Node root; // Constructors BinaryTree( int key) { root = new Node(key); } BinaryTree() { root = null ; } // Driver Code public static void Main(String[] args) { BinaryTree tree = new BinaryTree(); /*create root*/ tree.root = new Node(1); /* following is the tree after above statement 1 / null null */ tree.root.left = new Node(2); tree.root.right = new Node(3); /* 2 and 3 become left and right children of 1 1 / 2 3 / / null null null null */ tree.root.left.left = new Node(4); /* 4 becomes left child of 2 1 / 2 3 / / 4 null null null / null null */ } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> /* Class containing left and right child of current node and key value*/ class Node { constructor(val) { this .key = val; this .left = null ; this .right = null ; } } // A javascript program to introduce Binary Tree // Root of Binary Tree var root = null ; /*create root*/ root = new Node(1); /* following is the tree after above statement 1 / null null */ root.left = new Node(2); root.right = new Node(3); /* 2 and 3 become left and right children of 1 1 / 2 3 / / null null null null */ root.left.left = new Node(4); /* 4 becomes left child of 2 1 / 2 3 / / 4 null null null / null null */ // This code contributed by umadevi9616 </script> |
总结： 树是一种层次化的数据结构。树的主要用途包括维护分层数据、提供适度访问和插入/删除操作。二叉树是树的特例，每个节点最多有两个子节点。 https://youtu.be/W6aZKAJcNJA 下面是这篇文章的第二组和第三组。 二叉树的性质 二叉树的类型 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
