二叉树入门原理介绍和实现指南

2021年4月21日15:44:15 发表评论 1,208 次浏览

本文概述

树木：与数组, 链表, 堆栈和队列(它们是线性数据结构)不同, 树是分层数据结构。

树词汇：最顶层的节点称为树的根。元素正下方的元素称为其子元素。某物正上方的元素称为其父元素。例如, " a"是" f"的子级, 而" f"是" a"的父级。最后, 没有子元素的元素称为叶子。

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.多阶段决策的形式(请参阅商务象棋)。

二叉树：一棵其元素最多具有2个子代的树称为二叉树。由于二叉树中的每个元素只能有2个子节点, 因此我们通常将其命名为left和right子节点。

C中的二叉树表示形式：

一棵树由指向树中最高节点的指针表示。如果树为空, 则root的值为NULL。

树节点包含以下部分。

1.数据

2.指向左孩子的指针

3.指向右孩子的指针

在C语言中, 我们可以使用结构表示树节点。以下是具有整数数据的树节点的示例。

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

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

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'''

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
          */
     }
}

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

概要：树是分层数据结构。树的主要用途包括维护分层数据, 提供适度的访问权限以及插入/删除操作。二叉树是树的特殊情况, 其中每个节点最多有两个孩子。

以下是该帖子的第2组和第3组。

二叉树的性质

二叉树的类型

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: