Logische Fehler BST ... falsche Ergebnisse

Question

HALLO ich habe diesen Code mit Hilfe von Marc GRA in

Warum kann ich nicht finden _Left und _right in BinarySearchTree?
&
Wie korrigiere ich eine implizite Konvertierung Fehler in # -Code BST C?

, dessen binärer Suchbaum, aber jetzt logischen Fehler Ich habe die kommenden Ergebnisse falsch sind der Ausgang meines Codes ist folgende:

2
3
5
6
10
17
------------------------------------------------
17
2
------------------------------------------------
3                 
6
Press any key to continue . . .

die beiden letzten Nummer muss die Gesamtzahl der eingefügten Elemente 6 geben aber seine zeigt 9

und aber die Art und Weise wie kann ich die Höhe des Baumes erhalten?!

---

using System;
using System.Collections.Generic;
using System.Text;

namespace errors
{
    class Program
    {
        static void Main(string[] args)
        {
            BinarySearchTree t = new BinarySearchTree();

            t.insert(ref t.root, 10);
            t.insert(ref t.root, 5);
            t.insert(ref t.root, 6);
            t.insert(ref t.root, 17);
            t.insert(ref t.root, 2);
            t.insert(ref t.root, 3);

            BinarySearchTree.print(t.root);

            Console.WriteLine("------------------------------------------------");
            Console.WriteLine(t.FindMax());
            Console.WriteLine(t.FindMin());
            Console.WriteLine("------------------------------------------------");

            Console.WriteLine(t.CountLeaves(t.root));
            Console.WriteLine(t.CountNodes(t.root));

        }

        public class TreeNode
        {
            public int n;
            public TreeNode _left;
            public TreeNode _right;


            public TreeNode(int n, TreeNode _left, TreeNode _right)
            {
                this.n = n;
                this._left = _left;
                this._right = _right;
            }


            public void DisplayNode()
            {
                Console.Write(n);
            }


        }


        public class BinarySearchTree
        {
            public TreeNode root;


            public BinarySearchTree()
            {
                root = null;
            }


            public void insert(ref TreeNode root, int x)
            {
                if (root == null)
                {
                    root = new TreeNode(x, null, null);
                }
                else
                    if (x < root.n)
                        insert(ref root._left, x);
                    else
                        insert(ref root._right, x);
            }

            public int FindMin()
            {
                TreeNode current = root;

                while (current._left != null)
                    current = current._left;

                return current.n;
            }

            public int FindMax()
            {
                TreeNode current = root;

                while (current._right != null)
                    current = current._right;

                return current.n;
            }



            public TreeNode Find(int key)
            {
                TreeNode current = root;

                while (current.n != key)
                {
                    if (key < current.n)
                        current = current._left;
                    else
                        current = current._right;
                    if (current == null)
                        return null;
                }
                return current;
            }



            public void InOrder(ref TreeNode root)
            {
                if (root != null)
                {
                    InOrder(ref root._left);
                    root.DisplayNode();
                    InOrder(ref root._right);
                }
            }

            public int CountNodes(TreeNode root)
            {
                int count=1;
                if (root._left != null)
                    count += CountNodes(root._left);
                if (root._right != null)
                    count += CountNodes(root._right);
                return count;
            }

            public int CountLeaves(TreeNode root)
            {
                int count = (root._left == null && root._right == null) ? 1 : 0;
                if (root._left != null)
                    count += CountLeaves(root._left);
                if (root._right != null)
                    count += CountLeaves(root._right);
                return count;
            }


            public static void print(TreeNode root)
            {
                if (root != null)
                {
                    print(root._left);
                    Console.WriteLine(root.n.ToString());
                    print(root._right);
                }

            }



        }

    }
}

Danke im Voraus und speziellen Dank an Marc GRA.

Answer 1

Wenn das, was Sie in CountNodes bedeuten, alle Nicht-Blattknoten zu zählen, müssen Sie diese Zeile:

int count=1;

, dies zu lesen:

int count = (root._left == null && root._right == null) ? 0 : 1;

(das Gegenteil von dem, was in CountLeaves ist).

Und das wird Sie die Höhe des Baumes erhalten:

public int Height(TreeNode root)
{
    int height = 1;
    if (root._left != null)
        height = Math.Max(height, Height(root._left));
    if (root._right != null)
        height = Math.Max(height, Height(root._right));
    return height;   
}

Answer 2

Im Hinblick auf die Baumhöhe bekommen, verwenden Sie die folgende rekursive Pseudo-Code, nodeHeight(root) Aufruf:

nodeHeight(node)
    left=0
    right=0

    if (node == null) return 0

    left = 1 + nodeHeight(getLeft(node))
    right = 1 + nodeHeight(getRight(node))

    return max(left,right)

Answer 3

Es scheint nicht, dass Sie Ihren Baum balancieren, so dass Sie nur eine einfache verknüpfte Liste, die für Ihre falsche Werte ausmachen. Ein richtig ausgeglichener Baum wird eine maximale Höhe von log2 (N) hat.