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

本文概述

C/C++
python
Java
C#
C ++
C
python
Java
C#

树木：与数组, 链表, 堆栈和队列(它们是线性数据结构)不同, 树是分层数据结构。
树词汇：最顶层的节点称为树的根。元素正下方的元素称为其子元素。某物正上方的元素称为其父元素。例如, " a"是" f"的子级, 而" f"是" a"的父级。最后, 没有子元素的元素称为叶子。

tree ---- j< -- root / \ fk / \\ ahz< -- leaves

为什么使用树？
1.使用树的一个原因可能是因为你要存储自然形成层次结构的信息。例如, 计算机上的文件系统：

file system ----------- /< -- root /\ ...home /\ ugradcourse //|\ ...cs101cs112cs113

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语言中的第一棵简单树
让我们用C中的4个节点创建一个简单的树。创建的树如下。

tree ---- 1< -- root / \ 23 / 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 = https://www.lsbin.com/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 statement1 / NULL NULL */root-> left = new Node(2); root-> right = new Node(3); /* 2 and 3 become left and right children of 1 1 / 23 // NULL NULL NULL NULL */root-> left-> left = new Node(4); /* 4 becomes left child of 2 1 / 23 // 4 NULL NULL NULL / NULL NULL */return 0; }

#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 = https://www.lsbin.com/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 / 23 / / NULL NULL NULL NULL */root-> left-> left = newNode(4); /* 4 becomes left child of 2 1 / 23 // 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 / \ NoneNone'''root.left= Node( 2 ); root.right= Node( 3 ); ''' 2 and 3 become left and right children of 1 1 / \ 23 /\/\ None None None None'''root.left.left= Node( 4 ); '''4 becomes left child of 2 1 /\ 23 / \/\ 4NoneNoneNone /\ 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 statement1 / \ nullnull*/tree.root.left = new Node( 2 ); tree.root.right = new Node( 3 ); /* 2 and 3 become left and right children of 1 1 / \ 23 /\/\ null null null null*/tree.root.left.left = new Node( 4 ); /* 4 becomes left child of 2 1 /\ 23 / \/\ 4nullnullnull / \ null null */ } }

//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 statement1 /\ 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 /\ 23 /\ /\ null null null null */ tree.root.left.left = new Node(4); /* 4 becomes left child of 2 1 /\ 23 /\/\ 4 null null null /\ null null */ } }//This code is contributed by PrinciRaj1992

概要：树是分层数据结构。树的主要用途包括维护分层数据, 提供适度的访问权限以及插入/删除操作。二叉树是树的特殊情况, 其中每个节点最多有两个孩子。
以下是该帖子的第2组和第3组。
二叉树的性质
二叉树的类型
【二叉树入门原理介绍和实现指南】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。