Comment créer un arbre binary

Je ne voulais pas dire arbre de recherche binary.

Par exemple, si j’insère les valeurs 1,2,3,4,5 dans un arbre de recherche binary, la traversée en ordre donnera 1,2,3,4,5 en sortie.

mais si j’insère les mêmes valeurs dans un arbre binary, la traversée en ordre devrait donner 4,2,5,1,3 en sortie.

L’arbre binary peut être créé à l’aide de tableaux dynamics dans lesquels, pour chaque élément de l’index n, 2n + 1 et 2n + 2 représentent respectivement ses fils gauche et droit.

La représentation et la traversée des niveaux sont donc très faciles ici.

mais je pense que dans l’ordre, après la commande, la précommande est difficile.

Ma question est la suivante: comment pouvons-nous créer un arbre binary comme un arbre de recherche binary? c’est à dire. avoir une classe d’arborescence qui contient des données, des pointeurs gauche et droit au lieu de tableaux. afin que nous puissions faire récursivement traversal.

Si je vous ai bien compris, vous voulez créer un arbre binary à partir d’un tableau

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

ceci devrait préremplir l’arbre binary avec les valeurs 1 – 5 comme suit:

  1 / \ 2 3 / \ 4 5 

Cela peut être fait en utilisant la classe suivante:

 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); } } } 

La partie déclaration de classe d’arbres n’est certainement pas la difficulté ici. Vous avez essentiellement dit exactement comment le déclarer, dans la question:

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

Cela supporte différentes formes de traversées, comme ceci:

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

Vous devriez pouvoir en déduire des traversées pré et post-commande. Dans une implémentation réelle, l’arborescence serait probablement conçue pour stocker des données aléatoires, les routines de parcours seraient plus générales (avec une entrée de données utilisateur, ou peut-être un rappel par noeud fourni par l’utilisateur, ou autre), bien sûr.

Si vous recherchez une implémentation complète de BinaryTree, vous pouvez vous renseigner sur The C5 Generic Collection Library .

N’ayant reçu aucune réponse à la question que j’ai posée, je publierai ma propre implémentation de l’arbre binary à l’aide de tableaux. Maintenant, je sais que la mise en oeuvre de tableaux est plus facile que je ne le pensais, mais je ne sais toujours pas comment mettre en œuvre la même chose en utilisant des listes chaînées.

le code est en 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"); } } 
  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(ssortingng[] 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); } }