Queue Application: Level Order Traversal Animation Demo

二叉树是一种树形数据结构，其中每个节点最多可以有两个子节点，称为左子节点和右子节点。

二叉树中最顶部的节点称为根，最底部的节点称为叶。二叉树可以可视化为层次结构，根位于顶部，叶子位于底部。

二叉树在计算机科学中有很多应用，包括数据存储和检索、表达式评估、网络路由和游戏人工智能。它们还可以用于实现各种算法，例如搜索、排序和图算法。

二叉树的表示：

树中的每个节点包含以下内容：

数据
指向左孩子的指针
指向右孩子的指针

二叉树

在C中，我们可以使用结构来表示树节点。在其他语言中，我们可以使用类作为其 OOP 功能的一部分。下面是具有整数数据的树节点的示例。

C

                
                      // Structure of each node of the tree
 
struct node {
    int data;
    struct node* left;
    struct node* right;
};

C++

                
                  
                      // Use any below method to implement Nodes of tree
 
// Method 1: Using "struct" to make
// user-define data type
                          
struct node {
    int data;
    struct node* left;
    struct node* right;
};
 
// Method 2: Using "class" to make
// user-define data type
                          
class Node {
public:
    int data;
    Node* left;
    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>

                    

                
              

二叉树的基本操作：

插入一个元素。
删除一个元素。
寻找一个元素。
删除一个元素。
遍历一个元素。二叉树的遍历有四种（主要是三种）类型，下面将讨论。

二叉树的辅助操作：

找到树的高度
查找树的级别
求整棵树的大小。

二叉树的应用：

在编译器中，使用表达式树，它是二叉树的应用。
霍夫曼编码树用于数据压缩算法。
优先级队列是二叉树的另一个应用，用于以 O(1) 时间复杂度搜索最大值或最小值。
表示分层数据。
用于 Microsoft Excel 和电子表格等编辑软件。
对于数据库中的分段索引很有用，对于在系统中存储缓存也很有用，
语法树用于大多数著名的编译器进行编程，例如 GCC 和 AOCL 来执行算术运算。
用于实现优先级队列。
用于在更短的时间内查找元素（二叉搜索树）
用于启用计算机中的快速内存分配。
用于执行编码和解码操作。
二叉树可用于组织和检索大型数据集中的信息，例如倒排索引和 kd 树。
二叉树可以用来表示游戏中计算机控制角色的决策过程，例如决策树。
二叉树可用于实现搜索算法，例如二叉搜索树可用于快速查找排序列表中的元素。
二叉树可用于实现排序算法，例如堆排序，它使用二叉堆对元素进行有效排序。

二叉树遍历：

树遍历算法大致可以分为两类：

深度优先搜索 (DFS) 算法
广度优先搜索 (BFS) 算法

使用深度优先搜索（DFS）算法的树遍历可以进一步分为三类：

前序遍历（当前-左-右）： 在访问左子树或右子树内的任何节点之前先访问当前节点。这里的遍历是根-左孩子-右孩子。这意味着首先遍历根节点，然后遍历其左子节点，最后遍历右子节点。
中序遍历（左-当前-右）： 在访问左子树内的所有节点之后但在访问右子树内的任何节点之前访问当前节点。这里的遍历是左孩子-根-右孩子。这意味着首先遍历左子节点，然后遍历其根节点，最后遍历右子节点。
后序遍历（左-右-当前）： 访问完左右子树的所有节点后，再访问当前节点。这里的遍历是左孩子-右孩子-根。这意味着先遍历左子节点，然后遍历右子节点，最后遍历其根节点。

使用广度优先搜索（BFS）算法的树遍历可以进一步分为一类：

层级顺序遍历： 逐级、从左到右地访问同一层级的节点。这里，遍历是逐级的。意思是最左边的孩子先遍历完，然后从左到右同级的其他孩子都遍历完。

让我们用所有四种遍历方法来遍历下面的树：

二叉树

上述树的前序遍历： 1-2-4-5-3-6-7
上述树的中序遍历： 4-2-5-1-6-3-7
后序遍历上面的树： 4-5-2-6-7-3-1
上面的树的层序遍历： 1-2-3-4-5-6-7

二叉树的实现：

让我们创建一个具有 4 个节点的简单树。创建的树如下所示。

二叉树

下面是二叉树的实现：

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;
}

                  

              
            

C++

              
                
                    #include <bits/stdc++.h>
using namespace std;
 
class Node {
public:
    int
                          data;
    Node* left;
    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*/
    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;
}

                  

              
            

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
 
 
# Driver code
if __name__ ==
                          '__main__':
    # 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
*/
</script>

                  

              
            

结论：

树是一种分层数据结构。树的主要用途包括维护分层数据、提供适度的访问和插入/删除操作。二叉树是树的特殊情况，其中每个节点最多有两个子节点。

你还能读什么？

二叉树的性质
二叉树的类型

如果您发现任何不正确的内容，或者您想分享有关上述主题的更多信息，请发表评论。