如何创建二叉树

我不是指二进制搜索树。

例如，如果我将值1,2,3,4,5插入到二叉搜索树中，则inorder遍历将给出1,2,3,4,5作为输出。

但是如果我将相同的值插入到二叉树中，则inorder遍历应该给出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

树类声明部分当然不是困难。 你在这个问题中基本上已经说明了如何声明它：

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

这支持各种forms的遍历，如下所示：

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

您应该能够从中推断出订单前和订单后的遍历。 在实际实现中，树可能会模板化存储随机数据，当然，遍历例程将更通用（使用用户数据输入，或者可能是用户提供的每节点回调，或其他）。

Answer 3

如果您正在寻找全面的BinaryTree实现，您可以从中学习C5通用集合库 。

Answer 4

由于我没有收到我问过的问题的任何答案，我将使用数组发布我自己的二叉树实现。 现在我知道数组实现比我想象的更容易，但我仍然不知道如何使用链表实现相同的。

代码在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 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); } }