问：使用链表实现二叉树的程序

2025年3月17日 | 阅读 10 分钟

说明

在此程序中，我们需要通过插入节点和以中序方式显示节点来创建二叉树。典型的二叉树可以表示如下

Program to implement Binary Tree using the linked list

在二叉树中，每个节点最多可以有两个子节点。每个节点可以有零个、一个或两个子节点。二叉树中的每个节点包含以下信息

Data 表示存储在节点中的值。

Left 表示指向左子节点的指针。

Right 表示指向右子节点的指针。

算法

定义 Node 类，它有三个属性：data、left 和 right。其中，left 表示节点的左子节点，right 表示节点的右子节点。
创建节点时，将数据传递给节点的 data 属性，并将 left 和 right 都设置为 null。
定义另一个类，该类有一个 root 属性。
1. 根表示树的根节点，并将其初始化为 null。
insert() 将向树添加一个新节点
1. 它检查 root 是否为 null，这意味着树是空的。它将新节点添加为 root。
2. 否则，它将 root 添加到队列中。
3. 变量 node 表示当前节点。
4. 首先，它检查节点是否有左子节点和右子节点。如果有，它将两个节点都添加到队列中。
5. 如果左子节点不存在，它将新节点添加为左子节点。
6. 如果左子节点存在，则它将新节点添加为右子节点。
Inorder() 将以中序方式显示树的节点。
1. 它遍历整个树，然后打印左子节点，然后是根节点，然后是右子节点。

解决方案

Python

#Represent a node of binary tree
class Node:
    def __init__(self,data):
        #Assign data to the new node, set left and right children to None
        self.data = data;
        self.left = None;
        self.right = None;
 
class BinaryTree:
    def __init__(self):
        #Represent the root of binary tree
        self.root = None;
        
    #insertNode() will add new node to the binary tree
    def insertNode(self, data):
        #Create a new node
        newNode = Node(data);
        
        #Check whether tree is empty
        if(self.root == None):
            self.root = newNode;
            return;
        else:
            queue = [];
            #Add root to the queue
            queue.append(self.root);
            
            while(True):
                node = queue.pop(0);
                #If node has both left and right child, add both the child to queue
                if(node.left != None and node.right != None):
                    queue.append(node.left);
                    queue.append(node.right);
                else:
                    #If node has no left child, make newNode as left child
                    if(node.left == None):
                        node.left = newNode;
                        queue.append(node.left);
                    else:
                        #If node has left child but no right child, make newNode as right child
                        node.right = newNode;
                        queue.append(node.right);
                    break;
                    
    #inorder() will perform inorder traversal on binary search tree
    def inorderTraversal(self, node):
        
        #Check whether tree is empty
        if(self.root == None):
            print("Tree is empty");
            return;
        else:
            if(node.left != None):
                self.inorderTraversal(node.left);
            print(node.data),
            if(node.right!= None):
                self.inorderTraversal(node.right);
                
bt = BinaryTree();
#Add nodes to the binary tree
 
bt.insertNode(1);
#1 will become root node of the tree
print("Binary tree after insertion");
#Binary after inserting nodes
bt.inorderTraversal(bt.root);
 
bt.insertNode(2);
bt.insertNode(3);
#2 will become left child and 3 will become right child of root node 1
print("\nBinary tree after insertion");
#Binary after inserting nodes
bt.inorderTraversal(bt.root);
 
bt.insertNode(4);
bt.insertNode(5);
#4 will become left child and 5 will become right child of node 2
print("\nBinary tree after insertion");
#Binary after inserting nodes
bt.inorderTraversal(bt.root);
 
bt.insertNode(6);
bt.insertNode(7);
#6 will become the left child and 7 will become the right child of node 3
print("\nBinary tree after insertion");
#Binary after inserting nodes
bt.inorderTraversal(bt.root);

输出

Binary tree after insertion
1 
Binary tree after insertion
2 1 3 
Binary tree after insertion
4 2 5 1 3 
Binary tree after insertion
4 2 5 1 6 3 7

C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
//Represent a node of binary tree
struct node{
    int data;
    struct node *left;
    struct node *right;
};
 
//Represent the root of binary tree
struct node *root = NULL;
 
//createNode() will create a new node
struct node* createNode(int data){
    //Create a new node
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    //Assign data to newNode, set left and right child to NULL
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    
    return newNode;
}
 
//Represent a queue
struct queue
{
    int front, rear, size;
    struct node* *arr;
};
 
//createQueue() will create a queue
struct queue* createQueue()
{
    struct queue* newQueue = (struct queue*) malloc(sizeof( struct queue ));
 
    newQueue->front = -1;
    newQueue->rear = 0;
    newQueue->size = 0;

    newQueue->arr = (struct node**) malloc(100 * sizeof( struct node* ));
 
    return newQueue;
}
 
//Adds a node to queue
void enqueue(struct queue* queue, struct node *temp){
    queue->arr[queue->rear++] = temp;
    queue->size++;
}
 
//Deletes a node from queue
struct node *dequeue(struct queue* queue){
    queue->size--;
    return queue->arr[++queue->front];
}
 
 
//insertNode() will add new node to the binary tree
void insertNode(int data) {
    //Create a new node
    struct node *newNode = createNode(data);
    //Check whether tree is empty
    if(root == NULL){
        root = newNode;
        return;
    }
    else {
        //Queue will be used to keep track of nodes of tree level-wise
        struct queue* queue = createQueue();
        //Add root to the queue
        enqueue(queue, root);
        
        while(true) {
            struct node *node = dequeue(queue);
            //If node has both left and right child, add both the child to queue
            if(node->left != NULL && node->right != NULL) {
                enqueue(queue, node->left);
                enqueue(queue, node->right);
            }
            else {
                //If node has no left child, make newNode as left child
                if(node->left == NULL) {
                    node->left = newNode;
                    enqueue(queue, node->left);
                }
                //If node has left child but no right child, make newNode as right child
                else {
                    node->right = newNode;
                    enqueue(queue, node->right);
                }
                break;
            }
        }
    }
}
 
//inorder() will perform inorder traversal on binary search tree
void inorderTraversal(struct node *node) {
    //Check whether tree is empty
    if(root == NULL){
        printf("Tree is empty\n");
        return;
    }
    else {
          
        if(node->left != NULL)
            inorderTraversal(node->left);
        printf("%d ", node->data);
        if(node->right != NULL)
            inorderTraversal(node->right);
              
        }
    }
          
int main(){
    
    //Add nodes to the binary tree
    insertNode(1);
    //1 will become root node of the tree
    printf("Binary tree after insertion: \n");
    //Binary after inserting nodes
    inorderTraversal(root);
    
    insertNode(2);
    insertNode(3);
    //2 will become left child and 3 will become right child of root node 1
    printf("\nBinary tree after insertion: \n");
    //Binary after inserting nodes
    inorderTraversal(root);
    
    insertNode(4);
    insertNode(5);
    //4 will become left child and 5 will become right child of node 2
    printf("\nBinary tree after insertion: \n");
    //Binary after inserting nodes
    inorderTraversal(root);
    
    insertNode(6);
    insertNode(7);
    //6 will become left child and 7 will become right child of node 3
    printf("\nBinary tree after insertion: \n");
    //Binary after inserting nodes
    inorderTraversal(root);
    
    return 0;
}

输出

Binary tree after insertion
1 
Binary tree after insertion
2 1 3 
Binary tree after insertion
4 2 5 1 3 
Binary tree after insertion
4 2 5 1 6 3 7

JAVA

import java.util.LinkedList;
import java.util.Queue;
 
public class BinaryTree {
      
      //Represent a node of binary tree
      public static class Node{
        int data;
        Node left;
        Node right;
        
        public Node(int data){
          //Assign data to the new node, set left and right children to null
          this.data = data;
          this.left = null;
          this.right = null;
        }
      }
      
      //Represent the root of binary tree
      public Node root;
      
      public BinaryTree(){
        root = null;
      }
      
      //insertNode() will add new node to the binary tree
      public void insertNode(int data) {
          //Create a new node
          Node newNode = new Node(data);
          
          //Check whether tree is empty
          if(root == null){
              root = newNode;
              return;
          }
          else {
             Queue<Node> queue = new LinkedList<Node>();
             //Add root to the queue
             queue.add(root);
             
             while(true) {
               
                 Node node = queue.remove();
                //If node has both left and right child, add both the child to queue
                 if(node.left != null && node.right != null) {
                     queue.add(node.left);
                     queue.add(node.right);
                 }
                 else {
                    //If node has no left child, make newNode as left child
                     if(node.left == null) {
                         node.left = newNode;
                         queue.add(node.left);
                     }
                    //If node has left child but no right child, make newNode as right child
                     else {
                         node.right = newNode;
                         queue.add(node.right);
                     }
                     break;
                 }
             }
          }
      }
      
      //inorder() will perform inorder traversal on binary search tree
      public void inorderTraversal(Node node) {
          
          //Check whether tree is empty
          if(root == null){
              System.out.println("Tree is empty");
              return;
          }
          else {
              
              if(node.left!= null)
                  inorderTraversal(node.left);
              System.out.print(node.data + " ");
              if(node.right!= null)
                  inorderTraversal(node.right);
                  
              }      
          }
      
      public static void main(String[] args) {
       
        BinaryTree bt = new BinaryTree();
        //Add nodes to the binary tree
        
        bt.insertNode(1);
        //1 will become root node of the tree
        System.out.println("Binary tree after insertion");
        //Binary after inserting nodes
        bt.inorderTraversal(bt.root);
        
        bt.insertNode(2);
        bt.insertNode(3);
        //2 will become left child and 3 will become right child of root node 1
        System.out.println("\nBinary tree after insertion");
        //Binary after inserting nodes
        bt.inorderTraversal(bt.root);
        
        bt.insertNode(4);
        bt.insertNode(5);
        //4 will become left child and 5 will become right child of node 2
        System.out.println("\nBinary tree after insertion");
        //Binary after inserting nodes
        bt.inorderTraversal(bt.root);
        
        bt.insertNode(6);
        bt.insertNode(7);
        //6 will become left child and 7 will become right child of node 3
        System.out.println("\nBinary tree after insertion");
        //Binary after inserting nodes
        bt.inorderTraversal(bt.root);
        
      }
    }

输出

Binary tree after insertion
1 
Binary tree after insertion
2 1 3 
Binary tree after insertion
4 2 5 1 3 
Binary tree after insertion
4 2 5 1 6 3 7

C#

using System;
using System.Collections.Generic;
namespace Tree 
{                     
    public class Program
    {
        //Represent a node of binary tree
        public class Node<T>{
            public T data;
            public Node<T> left;
            public Node<T> right;
            
            public Node(T data) {
                //Assign data to the new node, set left and right children to null
                this.data = data;
                this.left = null;
                this.right = null;
            }
        }
        
        public class BinaryTree<T>{
            //Represent the root of binary tree
            public Node<T> root;
            
            public BinaryTree(){
                root = null;
            }
            
            //insertNode() will add new node to the binary tree
            public void insertNode(T data) {
                //Create a new node
                Node<T> newNode = new Node<T>(data);
 
                //Check whether tree is empty
                if(root == null){
                  root = newNode;
                  return;
                }
                else {
                    Queue<Node<T>> queue = new Queue<Node<T>>();
                    //Add root to the queue
                    queue.Enqueue(root);
 
                    while(true) {
 
                        Node<T> node = queue.Dequeue();
                        //If node has both left and right child, add both the child to queue
                        if(node.left != null && node.right != null) {
                            queue.Enqueue(node.left);
                            queue.Enqueue(node.right);
                        }
                        else {
                            //If node has no left child, make newNode as left child
                            if(node.left == null) {
                                node.left = newNode;
                                queue.Enqueue(node.left);
                            }
                            //If node has left child but no right child, make newNode as right child
                            else {
                                node.right = newNode;
                                queue.Enqueue(node.right);
                            }
                            break;
                        }
                    }
                }
            }
      
            //inorder() will perform inorder traversal on binary search tree
            public void inorderTraversal(Node<T> node) {
              
                //Check whether tree is empty
                if(root == null){
                    Console.WriteLine("Tree is empty");
                    return;
                }
                else {
                  
                    if(node.left!= null)
                      inorderTraversal(node.left);
                    Console.Write(node.data + " ");
                    if(node.right!= null)
                      inorderTraversal(node.right);
                }      
            }
        }
        
        public static void Main()
        {
            BinaryTree<int> bt = new BinaryTree<int>();
            //Add nodes to the binary tree
        
            bt.insertNode(1);
            //1 will become root node of the tree
            Console.WriteLine("Binary tree after insertion");
            //Binary after inserting nodes
            bt.inorderTraversal(bt.root);
 
            bt.insertNode(2);
            bt.insertNode(3);
            //2 will become left child and 3 will become right child of root node 1
            Console.WriteLine("\nBinary tree after insertion");
            //Binary after inserting nodes
            bt.inorderTraversal(bt.root);
 
            bt.insertNode(4);
            bt.insertNode(5);
            //4 will become left child and 5 will become right child of node 2
            Console.WriteLine("\nBinary tree after insertion");
            //Binary after inserting nodes
            bt.inorderTraversal(bt.root);
 
            bt.insertNode(6);
            bt.insertNode(7);
            //6 will become left child and 7 will become right child of node 3
            Console.WriteLine("\nBinary tree after insertion");
            //Binary after inserting nodes
            bt.inorderTraversal(bt.root);                
        }    
    }
}

输出

Binary tree after insertion
1 
Binary tree after insertion
2 1 3 
Binary tree after insertion
4 2 5 1 3 
Binary tree after insertion
4 2 5 1 6 3 7

PHP

<!DOCTYPE html>
<html>
<body>
<?php
//Represent a node of binary tree
class Node{
    public $data;
    public $left;
    public $right;
    
    function __construct($data){
        //Assign data to the new node, set left and right children to NULL
        $this->data = $data;
        $this->left = NULL;
        $this->right = NULL;
    }
}
class BinaryTree{
    //Represent the root of binary tree
    public $root;
    function __construct(){
        $this->root = NULL;
    }
    
    //insertNode() will add new node to the binary tree
    function insertNode($data) {
        //Create a new node
        $newNode = new Node($data);
        //Check whether tree is empty
        if($this->root == NULL){
            $this->root = $newNode;
            return;
        }
        else {
            $queue = array();
            //Add root to the queue
            array_push($queue, $this->root);
            while(true) {
                $node = array_shift($queue);
                //If node has both left and right child, add both the child to queue
                if($node->left != NULL && $node->right != NULL) {
                    array_push($queue, $node->left);
                    array_push($queue, $node->right);
                }
                else {
                    //If node has no left child, make newNode as left child
                    if($node->left == NULL) {
                        $node->left = $newNode;
                        array_push($queue, $node->left);
                    }
                    //If node has left child but no right child, make newNode as right child
                    else {
                        $node->right = $newNode;
                        array_push($queue, $node->right);
                    }
                    break;
                }
            }
        }
    }
      
    //inorder() will perform inorder traversal on binary search tree
    function inorderTraversal($node) {
        
        //Check whether tree is empty
        if($this->root == NULL){
            print("Tree is empty <br>");
            return;
        }
        else {
            
            if($node->left != NULL)
                $this->inorderTraversal($node->left);
            print($node->data . " ");
            if($node->right != NULL)
                $this->inorderTraversal($node->right);
        }      
    }  
}
    
$bt = new BinaryTree();
//Add nodes to the binary tree
 
$bt->insertNode(1);
//1 will become root node of the tree
print("\nBinary tree after insertion <br>");
//Binary after inserting nodes
$bt->inorderTraversal($bt->root);    
 
$bt->insertNode(2);
$bt->insertNode(3);
//2 will become left child and 3 will become right child of root node 1
print("<br> Binary tree after insertion <br>");
//Binary after inserting nodes
$bt->inorderTraversal($bt->root);    
 
$bt->insertNode(4);
$bt->insertNode(5);
//4 will become left child and 5 will become right child of node 2
print("<br> Binary tree after insertion <br>");
//Binary after inserting nodes
$bt->inorderTraversal($bt->root);    
 
$bt->insertNode(6);
$bt->insertNode(7);
//6 will become left child and 7 will become right child of node 3
print("<br> Binary tree after insertion <br>");
//Binary after inserting nodes
$bt->inorderTraversal($bt->root);      
?>
</body>
</html>

输出

Binary tree after insertion
1 
Binary tree after insertion
2 1 3 
Binary tree after insertion
4 2 5 1 3 
Binary tree after insertion
4 2 5 1 6 3 7

下一个主题程序列表

问：使用链表实现二叉树的程序

说明

算法

解决方案

Python

C

JAVA

C#

PHP

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

程序

问：使用链表实现二叉树的程序

说明

算法

解决方案

Python

C

JAVA

C#

PHP

相关帖子

显示上三角矩阵的程序

打印数组中元素数量的程序

确定两个字符串是否为变位词（anagram）的程序

在循环链表中间插入新节点的程序

编写查找六棱柱（Hexagonal Prism）面积的程序

将英尺转换为毫米的程序

在双向链表中间插入新节点的程序

将厘米转换为英尺和英寸的程序

将英寸转换为米的程序

打印数组中最大元素的程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器