How to create a binary tree

Question

I did not mean the binary search tree.

for example, if I paste the values ​​1,2,3,4,5 into a binary search tree, then going around in order will give 1,2,3,4,5 as an output.

but if I insert the same values ​​into a binary tree, then going around in order should give 4,2,5,1,3 as an output.

The binary tree can be created using dynamic arrays in which for each element of the index n, 2n + 1 and 2n + 2 are their left and right child elements, respectively.

therefore, introducing and circumventing the level order here is very easy.

But I think the order is in order, pre-order is difficult.

My question is how can we create a binary tree, such as a binary search tree. i.e. have a tree class that contains data, left and right pointers instead of arrays. so that we can recursively traverse.

Answer 1

If I understand you correctly, you want to create a binary tree from an array

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

this should preset the binary tree with values ​​1 to 5 as follows:

  1 / \ 2 3 / \ 4 5 

this can be done using the following class:

 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

Part of the tree class declaration, of course, is not a difficulty. You basically stated exactly how to state this in the question:

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

This supports various forms of workaround, for example:

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

You should be able to withdraw from this pre- and post-warrant. In a real implementation, the tree would probably be a template for storing random data, traversal procedures would be more general (with a request for user data or, possibly, with a request for a user call) or something).

Answer 3

Since I did not get any answers to the question I asked, I will post my own implementation of the binary tree using arrays. now I know that implementing an array is easier than I thought, but still I don’t know how to implement the same with linked lists.

code is in 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 4

If you use the source for a comprehensive implementation of BinaryTree, you can find out from the C5 Generic Collection Library .

Answer 5

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