# 从BST构建二叉树，使其遍历级别顺序可打印排序的数据

2021年4月22日15:04:33 发表评论 955 次浏览

## 本文概述

• 执行给定的二进制搜索树的有序遍历。
• 按级别顺序将每个节点添加到二叉树
• 最后, 打印创建的二叉树的级别顺序遍历。

## C ++

``````//C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;

//Structure to hold the contents
//of the new node
struct node {
int data;
node *left, *right;
}* root1 = NULL;

{
node* newnode = new node;
newnode->data = data;
newnode->left = newnode->right = NULL;
return newnode;
}

//Function to add a node to the
//Binary Tree in the level order
{

//If it is the first node
//it the root node
if (root1 == NULL)
else {
queue<node*> Q;
Q.push(root1);
while (!Q.empty()) {

//Get and remove the front
node* temp = Q.front();
Q.pop();

//If the left child of the current
//node is null then create the new
//node here and break
if (temp->left == NULL) {
break ;
}
else
Q.push(temp->left);

//If the right child of the current
//node is null then create the new
//node here and break
if (temp->right == NULL) {
break ;
}
else
Q.push(temp->right);
}
}
}

//Function to add a node to
//the Binary Search tree
{

//If the current node is null
//then create a new node here
//with the given data
if (root == NULL)

//If the data is smaller than the
//current node's data then recur
//for the left sub-tree
else if (data <root->data)

//Else recur for the right sub-tree
else
return root;
}

//Function to perform a level order
//insertion in the Binary Tree from
//the given Binary Search tree
{
if (root == NULL)
return ;
}

//Function to print the level order
//traversal of the binary tree
void printlvl()
{
queue<node*> Q;

//Push root to the queue
Q.push(root1);
while (!Q.empty()) {

//Get the front
node* temp = Q.front();

//Remove the front
Q.pop();

//Print the data
cout <<temp->data <<" " ;

//Push the left child
if (temp->left != NULL)
Q.push(temp->left);

//Push the right child
if (temp->right != NULL)
Q.push(temp->right);
}
}

//Driver code
int main()
{
//Create the Binary Search Tree
node* root = NULL;

//Add nodes of the Binary Search
//Tree to the Binary Tree

//Print the level order traversal
//of the Binary Tree
printlvl();

return 0;
}``````

## Java

``````//Java implementation of the approach
import java.util.*;

class GFG
{

//Structure to hold the contents
//of the new node
static class node
{
int data;
node left, right;
}
static node root1 = null ;

{
node newnode = new node();
newnode.data = data;
newnode.left = newnode.right = null ;
return newnode;
}

//Function to add a node to the
//Binary Tree in the level order
{

//If it is the first node
//it the root node
if (root1 == null )
else
{
while (!Q.isEmpty())
{

//Get and remove the front
node temp = Q.peek();
Q.remove();

//If the left child of the current
//node is null then create the new
//node here and break
if (temp.left == null )
{
break ;
}
else

//If the right child of the current
//node is null then create the new
//node here and break
if (temp.right == null )
{
break ;
}
else
}
}
}

//Function to add a node to
//the Binary Search tree
static node addinBST(node root, int data)
{

//If the current node is null
//then create a new node here
//with the given data
if (root == null )

//If the data is smaller than the
//current node's data then recur
//for the left sub-tree
else if (data <root.data)

//Else recur for the right sub-tree
else
return root;
}

//Function to perform a level order
//insertion in the Binary Tree from
//the given Binary Search tree
{
if (root == null )
return ;
}

//Function to print the level order
//traversal of the binary tree
static void printlvl()
{

//Push root to the queue
while (!Q.isEmpty())
{

//Get the front
node temp = Q.peek();

//Remove the front
Q.remove();

//Print the data
System.out.print(temp.data + " " );

//Push the left child
if (temp.left != null )

//Push the right child
if (temp.right != null )
}
}

//Driver code
public static void main(String[] args)
{
//Create the Binary Search Tree
node root = null ;

//Add nodes of the Binary Search
//Tree to the Binary Tree

//Print the level order traversal
//of the Binary Tree
printlvl();
}
}

//This code is contributed by Rajput-Ji``````

## Python3

``````# Python3 implementation of the approach

# Structure to hold the contents
# of the new node

# Constructor to create a new node
def __init__( self , data):
self .data = data
self .left = self .right = None

root1 = None

# Function to add a node to the
# Binary Tree in the level order
global root1

# If it is the first node
# to be added then make
# it the root node
if (root1 = = None ):
else :
Q = [root1]
while ( len (Q)):

# Get and remove the front
temp = Q[ 0 ]
Q.pop( 0 )

# If the left child of the current
# node is None then create the new
# node here and break
if (temp.left = = None ):
break
else :
Q.append(temp.left)

# If the right child of the current
# node is None then create the new
# node here and break
if (temp.right = = None ):
break
else :
Q.append(temp.right)

# Function to add a node to
# the Binary Search tree

# If the current node is None
# then create a new node here
# with the given data
if (root = = None ):

# If the data is smaller than the
# current node's data then recur
# for the left sub-tree
elif (data <root.data):

# Else recur for the right sub-tree
else :
return root

# Function to perform a level order
# insertion in the Binary Tree from
# the given Binary Search tree
if (root = = None ):
return

# Function to print the level order
# traversal of the binary tree
def printlvl():

Q = []

# Push root to the
Q.append(root1)
while ( len (Q)):

# Get the front
temp = Q[ 0 ]

# Remove the front
Q.pop( 0 )

# Print the data
print (temp.data , end = " " )

# Push the left child
if (temp.left ! = None ):
Q.append(temp.left)

# Push the right child
if (temp.right ! = None ):
Q.append(temp.right)

# Driver code

# Create the Binary Search Tree

# Add nodes of the Binary Search
# Tree to the Binary Tree

# Print the level order traversal
# of the Binary Tree
printlvl()

# This code is contributed by SHUBHAMSINGH10``````

## C#

``````//C# implementation of the approach
using System;
using System.Collections.Generic;

class GFG
{

//Structure to hold the contents
//of the new node
public class node
{
public int data;
public node left, right;
}
static node root1 = null ;

{
node newnode = new node();
newnode.data = data;
newnode.left = newnode.right = null ;
return newnode;
}

//Function to add a node to the
//Binary Tree in the level order
{

//If it is the first node
//it the root node
if (root1 == null )
else
{
Queue<node> Q = new Queue<node>();
Q.Enqueue(root1);
while (Q.Count != 0)
{

//Get and remove the front
node temp = Q.Peek();
Q.Dequeue();

//If the left child of the current
//node is null then create the new
//node here and break
if (temp.left == null )
{
break ;
}
else
Q.Enqueue(temp.left);

//If the right child of the current
//node is null then create the new
//node here and break
if (temp.right == null )
{
break ;
}
else
Q.Enqueue(temp.right);
}
}
}

//Function to add a node to
//the Binary Search tree
static node addinBST(node root, int data)
{

//If the current node is null
//then create a new node here
//with the given data
if (root == null )

//If the data is smaller than the
//current node's data then recur
//for the left sub-tree
else if (data <root.data)

//Else recur for the right sub-tree
else
return root;
}

//Function to perform a level order
//insertion in the Binary Tree from
//the given Binary Search tree
{
if (root == null )
return ;
}

//Function to print the level order
//traversal of the binary tree
static void printlvl()
{
Queue<node> Q = new Queue<node>();

//Push root to the queue
Q.Enqueue(root1);
while (Q.Count != 0)
{

//Get the front
node temp = Q.Peek();

//Remove the front
Q.Dequeue();

//Print the data
Console.Write(temp.data + " " );

//Push the left child
if (temp.left != null )
Q.Enqueue(temp.left);

//Push the right child
if (temp.right != null )
Q.Enqueue(temp.right);
}
}

//Driver code
public static void Main(String[] args)
{
//Create the Binary Search Tree
node root = null ;

//Add nodes of the Binary Search
//Tree to the Binary Tree
``1 2 3 4 5``