Программа на языке C# для реализации обхода бинарного дерева поиска-Preorder, InOrder и Postorder

В этой статье мы узнаем: двоичный поиск дерева обхода в C#

Обход Дерева Двоичного Поиска:

Существует три метода обхода, используемые с бинарным деревом поиска: inorder, preorder и postorder.
— Inorder обход посещает все узлы в BST в порядке возрастания значений ключа узла.
— Предварительно упорядоченный обход сначала посещает корневой узел, затем узлы в поддеревьях под левым дочерним элементом корневого узла, а затем узлы в поддеревьях под правым дочерним элементом корневого узла
— Переход после заказа, метод сначала рекурсирует над левыми поддеревьями, а затем над правыми поддеревьями.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BinarySearchTree
{
    class Node
    {
        public int item;
        public Node left;
        public Node right;
        public void display()
        {
            Console.Write("[");
            Console.Write(item);
            Console.Write("]");
        }
    }
    class Tree
    {
        public Node root;
        public Tree()
        {
            root = null;
        }
        public Node ReturnRoot()
        {
            return root;
        }
        public void Insert(int id)
        {
            Node newNode = new Node();
            newNode.item = id;
            if (root == null)
                root = newNode;
            else
            {
                Node current = root;
                Node parent;
                while (true)
                {
                    parent = current;
                    if (id < current.item)
                    {
                        current = current.left;
                        if (current == null)
                        {
                            parent.left = newNode;
                            return;
                        }
                    }
                    else
                    {
                        current = current.right;
                        if (current == null)
                        {
                            parent.right = newNode;
                            return;
                        }
                    }
                }
            }
        }
        public void Preorder(Node Root)
        {
            if (Root != null)
            {
                Console.Write(Root.item + " ");
                Preorder(Root.left);
                Preorder(Root.right);
            }
        }
        public void Inorder(Node Root)
        {
            if (Root != null)
            {
                Inorder(Root.left);
                Console.Write(Root.item + " ");
                Inorder(Root.right);
            }
        }
        public void Postorder(Node Root)
        {
            if (Root != null)
            {
                Postorder(Root.left);
                Postorder(Root.right);
                Console.Write(Root.item + " ");
            }
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            Tree BST = new Tree();
            BST.Insert(30);
            BST.Insert(35);
            BST.Insert(57);
            BST.Insert(15);
            BST.Insert(63);
            BST.Insert(49);
            BST.Insert(89);
            BST.Insert(77);
            BST.Insert(67);
            BST.Insert(98);
            BST.Insert(91);
            Console.WriteLine("Inorder обход : ");
            BST.Inorder(BST.ReturnRoot());
            Console.WriteLine(" ");
            Console.WriteLine();
            Console.WriteLine("Preorder обход : ");
            BST.Preorder(BST.ReturnRoot());
            Console.WriteLine(" ");
            Console.WriteLine();
            Console.WriteLine("Postorder обход : ");
            BST.Postorder(BST.ReturnRoot());
            Console.WriteLine(" ");
            Console.ReadLine();
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace BinarySearchTree

{

class Node

{

public int item;

public Node left;

public Node right;

public void display()

{

Console.Write("[");

Console.Write(item);

Console.Write("]");

}

class Tree

{

public Node root;

public Tree()

{

root = null;

}

public Node ReturnRoot()

{

return root;

}

public void Insert(int id)

{

Node newNode = new Node();

newNode.item = id;

if (root == null)

root = newNode;

else

{

Node current = root;

Node parent;

while (true)

{

parent = current;

if (id < current.item)

{

current = current.left;

if (current == null)

{

parent.left = newNode;

return;

}

else

{

current = current.right;

if (current == null)

{

parent.right = newNode;

return;

}

public void Preorder(Node Root)

{

if (Root != null)

{

Console.Write(Root.item + " ");

Preorder(Root.left);

Preorder(Root.right);

}

public void Inorder(Node Root)

{

if (Root != null)

{

Inorder(Root.left);

Console.Write(Root.item + " ");

Inorder(Root.right);

}

public void Postorder(Node Root)

{

if (Root != null)

{

Postorder(Root.left);

Postorder(Root.right);

Console.Write(Root.item + " ");

}

class Program

{

static void Main(string[] args)

{

Tree BST = new Tree();

BST.Insert(30);

BST.Insert(35);

BST.Insert(57);

BST.Insert(15);

BST.Insert(63);

BST.Insert(49);

BST.Insert(89);

BST.Insert(77);

BST.Insert(67);

BST.Insert(98);

BST.Insert(91);

Console.WriteLine("Inorder обход : ");

BST.Inorder(BST.ReturnRoot());

Console.WriteLine(" ");

Console.WriteLine();

Console.WriteLine("Preorder обход : ");

BST.Preorder(BST.ReturnRoot());

Console.WriteLine(" ");

Console.WriteLine();

Console.WriteLine("Postorder обход : ");

BST.Postorder(BST.ReturnRoot());

Console.WriteLine(" ");

Console.ReadLine();

}

Вывод:

Inorder обход :
15 30 35 49 57 63 67 77 89 91 98

Preorder обход :
30 15 35 57 49 63 89 77 67 98 91

Postorder обход :
15 49 67 77 91 98 89 63 57 35 30

Добавить комментарий Отменить ответ