Как создать двоичное дерево

Question

Я не имел в виду бинарное дерево поиска.

например, если я вставлю значения 1,2,3,4,5 в бинарное дерево поиска, то прохождение обхода даст 1,2,3,4,5 на выходе.

но если я вставлю те же значения в двоичное дерево, обход по порядку должен дать 4,2,5,1,3 на выходе.

Двоичное дерево может быть создано с использованием динамических массивов, в которых для каждого элемента в индексе n, 2n + 1 и 2n + 2 представляют его левого и правого потомков соответственно.

так что представление и прохождение порядка уровней здесь очень просто.

но я думаю, по-порядку, по-порядку, предзаказ трудно.

У меня вопрос, как мы можем создать двоичное дерево, подобное бинарному дереву поиска. то есть. иметь класс дерева, который содержит данные, левый и правый указатели вместо массивов. так что мы можем рекурсивно сделать обход.

Answer 1

Если я вас правильно понимаю, вы хотите создать двоичное дерево из массива

int[] values = new int[] {1, 2, 3, 4, 5};
BinaryTree tree = new BinaryTree(values);

это должно предварительно заполнить двоичное дерево значениями 1 - 5 следующим образом:

    1
   / \
  2   3
 / \
4   5

это можно сделать с помощью следующего класса:

class BinaryTree
{
    int value;
    BinaryTree left;
    BinaryTree right;

    public BinaryTree(int[] values) : this(values, 0) {}

    BinaryTree(int[] values, int index)
    {
        Load(this, values, index);
    }

    void Load(BinaryTree tree, int[] values, int index)
    {
        this.value = values[index];
        if (index * 2 + 1 < values.Length)
        {
            this.left = new BinaryTree(values, index * 2 + 1);
        }
        if (index * 2 + 2 < values.Length)
        {
            this.right = new BinaryTree(values, index * 2 + 2);
        }
    }
}

Answer 2

Поскольку я не получил никаких ответов на заданный вопрос, я опубликую свою реализацию двоичного дерева с использованием массивов. теперь я знаю, что реализация массива проще, чем я думал, но все же я не знаю, как реализовать то же самое, используя связанные списки.

код в c #

  class BinaryTree
    {
        private static int MAX_ELEM = 100;      //initial size of the array
        int lastElementIndex;
        int?[] dataArray;

        public BinaryTree()
        {
            dataArray = new int?[MAX_ELEM];
            lastElementIndex = -1;
        }

        //function to insert data in to the tree
        //insert as a complete binary tree
        public void insertData(int data)
        {
            int?[] temp;
            if (lastElementIndex + 1 < MAX_ELEM)
            {
                dataArray[++lastElementIndex] = data;
            }
            else
            {  //double the size of the array on reaching the limit
                temp = new int?[MAX_ELEM * 2];
                for (int i = 0; i < MAX_ELEM; i++)
                {
                    temp[i] = dataArray[i];
                }
                MAX_ELEM *= 2;
                dataArray = temp;
                dataArray[++lastElementIndex] = data;
            }
        }

        //internal function used to get the left child of an element in the array
        int getLeftChild(int index) {
            if(lastElementIndex >= (2*index+1))
                return (2*index + 1);
            return -1;
        }

        //internal function used to get the right child of an element in the array
        int getRightChild(int index) {
            if(lastElementIndex >= (2*index+2))
                return (2*index + 2);
            return -1;
        }
        //function to check if the tree is empty
        public bool isTreeEmpty() {
            if (lastElementIndex == -1)
                return true;
            return false;
        }

        //recursive function for inorder traversal
        public void traverseInOrder(int index) {
            if (index == -1)
                return;
            traverseInOrder(getLeftChild(index));
            Console.Write("{0} ", dataArray[index]);
            traverseInOrder(getRightChild(index));
        }

        //recursive function for preorder traversal
        public void traversePreOrder(int index) {
            if (index == -1)
                return;
            Console.Write("{0} ", dataArray[index]);
            traversePreOrder(getLeftChild(index));
            traversePreOrder(getRightChild(index));
        }

        //recursive function for postorder traversal
        public void traversePostOrder(int index) {
            if (index == -1)
                return;
            traversePostOrder(getLeftChild(index));
            traversePostOrder(getRightChild(index));
            Console.Write("{0} ", dataArray[index]);
        }

        //function to traverse the tree in level order
        public void traverseLevelOrder()
        {
            Console.WriteLine("\nPrinting Elements Of The Tree In Ascending Level Order\n");
            if (lastElementIndex == -1)
            {
                Console.WriteLine("Empty Tree!...press any key to return");
                Console.ReadKey();
                return;
            }
            for (int i = 0; i <= lastElementIndex; i++)
            {
                Console.Write("{0} ", dataArray[i]);
            }
            Console.WriteLine("\n");
        }


    }

Answer 3

Часть описания класса дерева здесь, конечно, не сложность. Вы в основном указали, как именно это объявить, в вопросе:

class BinaryTree
{
private:
    int data;
    BinaryTree *left, *right;
};

Это поддерживает различные формы обхода, например:

void Inorder(const BinaryTree *root)
{
  if(root == 0)
    return;
  Inorder(root->left);
  printf("now at %d\n", root->data);
  Inorder(root->right);
}

Вы должны быть в состоянии вывести из этого обходы до и после заказа. В реальной реализации дерево, вероятно, было бы спроектировано для хранения случайных данных, процедуры обхода были бы более общими (с вводом пользовательских данных, или, возможно, предоставленным пользователем обратным вызовом на узел, или как угодно), конечно. *

Answer 4

  class BstNode
    {
        public int data;
        public BstNode(int data)
        {
            this.data = data;
        }
        public BstNode left;
        public BstNode right;
    }
    class Program
    {
        public static BstNode Insert(BstNode root, int data)
        {
            if (root == null) root = new BstNode(data);
            else if (data <= root.data) root.left = Insert(root.left, data);
            else if (data > root.data) root.right = Insert(root.right, data);

            return root;
        }

public static void Main(string[] args)
        {
            // create/insert into BST
            BstNode Root = null;
            Root = Insert(Root, 15);
            Root = Insert(Root, 10);
            Root = Insert(Root, 20);
            Root = Insert(Root, 8);
            Root = Insert(Root, 12);
            Root = Insert(Root, 17);
            Root = Insert(Root, 25);
         }

}

Answer 5

Если вы ищете источник всеобъемлющей реализации BinaryTree, вы можете поучиться у Универсальная библиотека C5 .