本文概述

• C ++
• C
• Java
• python
• C#
• C ++
• C
• Java
• python
• C#

给定二元搜索树的遍历顺序, 构造BST。
例如, 如果给定的遍历为{10, 5, 1, 7, 40, 50}, 则输出应为以下树的根。

10 /\ 540 /\\ 1750

方法1 (O(n^2)时间复杂度)
预遍历的第一个元素始终是根。我们首先构造根。然后我们找到第一个元素的索引, 该索引大于根。假设索引为" i"。根和" i"之间的值将成为左子树的一部分, 而" i + 1"和" n-1"之间的值将成为右子树的一部分。将给定的pre []划分为索引" i", 然后对左右子树重复进行。
例如在{10, 5, 1, 7, 40, 50}中, 10是第一个元素, 因此我们将其设为根。现在, 我们寻找第一个大于10的元素, 找到40。因此, 我们知道BST的结构如下。

10 /\ /\ {5, 1, 7}{40, 50}

我们对子数组{5, 1, 7}和{40, 50}递归地执行上述步骤, 并获得完整的树。
C ++

/* A O(n^2) program for construction of BST from preorder * traversal */ #include < bits/stdc++.h> using namespace std; /* A binary tree node has data, pointer to left child and a pointer to right child */ class node { public : int data; node* left; node* right; }; // A utility function to create a node node* newNode( int data) { node* temp = new node(); temp-> data = https://www.lsbin.com/data; temp-> left = temp-> right = NULL; return temp; } // A recursive function to construct Full from pre[]. // preIndex is used to keep track of index in pre[]. node* constructTreeUtil( int pre[], int * preIndex, int low, int high, int size) { // Base case if (*preIndex > = size || low > high) return NULL; // The first node in preorder traversal is root. So take // the node at preIndex from pre[] and make it root, and // increment preIndex node* root = newNode(pre[*preIndex]); *preIndex = *preIndex + 1; // If the current subarry has only one element, no need // to recur if (low == high) return root; // Search for the first element greater than root int i; for (i = low; i < = high; ++i) if (pre[i] > root-> data) break ; // Use the index of element found in preorder to divide // preorder array in two parts. Left subtree and right // subtree root-> left = constructTreeUtil(pre, preIndex, *preIndex, i - 1, size); root-> right = constructTreeUtil(pre, preIndex, i, high, size); return root; } // The main function to construct BST from given preorder // traversal. This function mainly uses constructTreeUtil() node* constructTree( int pre[], int size) { int preIndex = 0; return constructTreeUtil(pre, & preIndex, 0, size - 1, size); } // A utility function to print inorder traversal of a Binary // Tree void printInorder(node* node) { if (node == NULL) return ; printInorder(node-> left); cout < < node-> data < <" " ; printInorder(node-> right); } // Driver code int main() { int pre[] = { 10, 5, 1, 7, 40, 50 }; int size = sizeof (pre) / sizeof (pre[0]); node* root = constructTree(pre, size); cout < < "Inorder traversal of the constructed tree: \n" ; printInorder(root); return 0; } // This code is contributed by rathbhupendra

C

/* A O(n^2) program for construction of BST from preorder * traversal */ #include < stdio.h> #include < stdlib.h> /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node* left; struct node* right; }; // A utility function to create a node struct node* newNode( int data) { struct node* temp = ( struct node*) malloc ( sizeof ( struct node)); temp-> data = https://www.lsbin.com/data; temp-> left = temp-> right = NULL; return temp; } // A recursive function to construct Full from pre[]. // preIndex is used to keep track of index in pre[]. struct node* constructTreeUtil( int pre[], int * preIndex, int low, int high, int size) { // Base case if (*preIndex > = size || low > high) return NULL; // The first node in preorder traversal is root. So take // the node at preIndex from pre[] and make it root, and // increment preIndex struct node* root = newNode(pre[*preIndex]); *preIndex = *preIndex + 1; // If the current subarry has only one element, no need // to recur if (low == high) return root; // Search for the first element greater than root int i; for (i = low; i < = high; ++i) if (pre[i] > root-> data) break ; // Use the index of element found in preorder to divide // preorder array in two parts. Left subtree and right // subtree root-> left = constructTreeUtil(pre, preIndex, *preIndex, i - 1, size); root-> right = constructTreeUtil(pre, preIndex, i, high, size); return root; } // The main function to construct BST from given preorder // traversal. This function mainly uses constructTreeUtil() struct node* constructTree( int pre[], int size) { int preIndex = 0; return constructTreeUtil(pre, & preIndex, 0, size - 1, size); } // A utility function to print inorder traversal of a Binary // Tree void printInorder( struct node* node) { if (node == NULL) return ; printInorder(node-> left); printf ("%d " , node-> data); printInorder(node-> right); } // Driver code int main() { int pre[] = { 10, 5, 1, 7, 40, 50 }; int size = sizeof (pre) / sizeof (pre[0]); struct node* root = constructTree(pre, size); printf ( "Inorder traversal of the constructed tree: \n" ); printInorder(root); return 0; }

Java

// Java program to construct BST from given preorder // traversal // A binary tree node class Node { int data; Node left, right; Node( int d) { data = https://www.lsbin.com/d; left = right = null ; } } class Index { int index = 0 ; } class BinaryTree { Index index = new Index(); // A recursive function to construct Full from pre[]. // preIndex is used to keep track of index in pre[]. Node constructTreeUtil( int pre[], Index preIndex, int low, int high, int size) { // Base case if (preIndex.index > = size || low > high) { return null ; } // The first node in preorder traversal is root. So // take the node at preIndex from pre[] and make it // root, and increment preIndex Node root = new Node(pre[preIndex.index]); preIndex.index = preIndex.index + 1 ; // If the current subarry has only one element, no // need to recur if (low == high) { return root; } // Search for the first element greater than root int i; for (i = low; i < = high; ++i) { if (pre[i] > root.data) { break ; } } // Use the index of element found in preorder to // divide preorder array in two parts. Left subtree // and right subtree root.left = constructTreeUtil( pre, preIndex, preIndex.index, i - 1 , size); root.right = constructTreeUtil(pre, preIndex, i, high, size); return root; } // The main function to construct BST from given // preorder traversal. This function mainly uses // constructTreeUtil() Node constructTree( int pre[], int size) { return constructTreeUtil(pre, index, 0 , size - 1 , size); } // A utility function to print inorder traversal of a // Binary Tree void printInorder(Node node) { if (node == null ) { return ; } printInorder(node.left); System.out.print(node.data +" " ); printInorder(node.right); } // Driver code public static void main(String[] args) { BinaryTree tree = new BinaryTree(); int pre[] = new int [] { 10 , 5 , 1 , 7 , 40 , 50 }; int size = pre.length; Node root = tree.constructTree(pre, size); System.out.println( "Inorder traversal of the constructed tree is " ); tree.printInorder(root); } } // This code has been contributed by Mayank Jaiswal

python

# A O(n^2) Python3 program for construction of BST from preorder traversal # A binary tree node class Node(): # A constructor to create a new node def __init__( self , data): self .data = https://www.lsbin.com/data self .left = None self .right = None # constructTreeUtil.preIndex is a static variable of # function constructTreeUtil # Function to get the value of static variable # constructTreeUtil.preIndex def getPreIndex(): return constructTreeUtil.preIndex # Function to increment the value of static variable # constructTreeUtil.preIndex def incrementPreIndex(): constructTreeUtil.preIndex + = 1 # A recurseive function to construct Full from pre[]. # preIndex is used to keep track of index in pre[[]. def constructTreeUtil(pre, low, high, size): # Base Case if (getPreIndex() > = size or low > high): return None # The first node in preorder traversal is root. So take # the node at preIndex from pre[] and make it root, # and increment preIndex root = Node(pre[getPreIndex()]) incrementPreIndex() # If the current subarray has onlye one element, # no need to recur if low = = high: return root # Search for the first element greater than root for i in range (low, high + 1 ): if (pre[i] > root.data): break # Use the index of element found in preorder to divide # preorder array in two parts. Left subtree and right # subtree root.left = constructTreeUtil(pre, getPreIndex(), i - 1 , size) root.right = constructTreeUtil(pre, i, high, size) return root # The main function to construct BST from given preorder # traversal. This function mailny uses constructTreeUtil() def constructTree(pre): size = len (pre) constructTreeUtil.preIndex = 0 return constructTreeUtil(pre, 0 , size - 1 , size) def printInorder(root): if root is None : return printInorder(root.left) print root.data, printInorder(root.right) # Driver code pre = [ 10 , 5 , 1 , 7 , 40 , 50 ] root = constructTree(pre) print"Inorder traversal of the constructed tree:" printInorder(root) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

using System; // C# program to construct BST from given preorder traversal // A binary tree node public class Node { public int data; public Node left, right; public Node( int d) { data = https://www.lsbin.com/d; left = right = null ; } } public class Index { public int index = 0; } public class BinaryTree { public Index index = new Index(); // A recursive function to construct Full from pre[]. // preIndex is used to keep track of index in pre[]. public virtual Node constructTreeUtil( int [] pre, Index preIndex, int low, int high, int size) { // Base case if (preIndex.index > = size || low > high) { return null ; } // The first node in preorder traversal is root. So // take the node at preIndex from pre[] and make it // root, and increment preIndex Node root = new Node(pre[preIndex.index]); preIndex.index = preIndex.index + 1; // If the current subarry has only one element, no // need to recur if (low == high) { return root; } // Search for the first element greater than root int i; for (i = low; i < = high; ++i) { if (pre[i] > root.data) { break ; } } // Use the index of element found in preorder to // divide preorder array in two parts. Left subtree // and right subtree root.left = constructTreeUtil( pre, preIndex, preIndex.index, i - 1, size); root.right = constructTreeUtil(pre, preIndex, i, high, size); return root; } // The main function to construct BST from given // preorder traversal. This function mainly uses // constructTreeUtil() public virtual Node constructTree( int [] pre, int size) { return constructTreeUtil(pre, index, 0, size - 1, size); } // A utility function to print inorder traversal of a // Binary Tree public virtual void printInorder(Node node) { if (node == null ) { return ; } printInorder(node.left); Console.Write(node.data +" " ); printInorder(node.right); } // Driver code public static void Main( string [] args) { BinaryTree tree = new BinaryTree(); int [] pre = new int [] { 10, 5, 1, 7, 40, 50 }; int size = pre.Length; Node root = tree.constructTree(pre, size); Console.WriteLine( "Inorder traversal of the constructed tree is " ); tree.printInorder(root); } } // This code is contributed by Shrikant13

输出如下

Inorder traversal of the constructed tree: 1 5 7 10 40 50

时间复杂度：O(n^2)
方法2(O(n)时间复杂度)
诀窍是为每个节点设置范围{min .. max}。将范围初始化为{INT_MIN .. INT_MAX}。第一个节点肯定在范围内, 因此请创建根节点。要构造左子树, 请将范围设置为{INT_MIN…root-> data}。如果值在{INT_MIN .. root-> data}范围内, 则这些值是左子树的一部分。要构建正确的子树, 请将范围设置为{root-> data..max .. INT_MAX}。
以下是上述想法的实现：
C ++

/* A O(n) program for construction of BST from preorder traversal */ #include < bits/stdc++.h> using namespace std; /* A binary tree node has data, pointer to left child and a pointer to right child */ class node { public : int data; node* left; node* right; }; // A utility function to create a node node* newNode( int data) { node* temp = new node(); temp-> data = https://www.lsbin.com/data; temp-> left = temp-> right = NULL; return temp; } // A recursive function to construct // BST from pre[]. preIndex is used // to keep track of index in pre[]. node* constructTreeUtil( int pre[], int * preIndex, int key, int min, int max, int size) { // Base case if (*preIndex > = size) return NULL; node* root = NULL; // If current element of pre[] is in range, then // only it is part of current subtree if (key > min & & key < max) { // Allocate memory for root of this // subtree and increment *preIndex root = newNode(key); *preIndex = *preIndex + 1; if (*preIndex < size) { // Construct the subtree under root // All nodes which are in range // {min .. key} will go in left // subtree, and first such node // will be root of left subtree. root-> left = constructTreeUtil(pre, preIndex, pre[*preIndex], min, key, size); } if (*preIndex < size) { // All nodes which are in range // {key..max} will go in right // subtree, and first such node // will be root of right subtree. root-> right = constructTreeUtil(pre, preIndex, pre[*preIndex], key, max, size); } } return root; } // The main function to construct BST // from given preorder traversal. // This function mainly uses constructTreeUtil() node* constructTree( int pre[], int size) { int preIndex = 0; return constructTreeUtil(pre, & preIndex, pre[0], INT_MIN, INT_MAX, size); } // A utility function to print inorder // traversal of a Binary Tree void printInorder(node* node) { if (node == NULL) return ; printInorder(node-> left); cout < < node-> data < <" " ; printInorder(node-> right); } // Driver code int main() { int pre[] = { 10, 5, 1, 7, 40, 50 }; int size = sizeof (pre) / sizeof (pre[0]); // Function call node* root = constructTree(pre, size); cout < < "Inorder traversal of the constructed tree: \n" ; printInorder(root); return 0; } // This is code is contributed by rathbhupendra

C

/* A O(n) program for construction of BST from preorder * traversal */ #include < limits.h> #include < stdio.h> #include < stdlib.h> /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node* left; struct node* right; }; // A utility function to create a node struct node* newNode( int data) { struct node* temp = ( struct node*) malloc ( sizeof ( struct node)); temp-> data = https://www.lsbin.com/data; temp-> left = temp-> right = NULL; return temp; } // A recursive function to construct BST from pre[]. // preIndex is used to keep track of index in pre[]. struct node* constructTreeUtil( int pre[], int * preIndex, int key, int min, int max, int size) { // Base case if (*preIndex > = size) return NULL; struct node* root = NULL; // If current element of pre[] is in range, then // only it is part of current subtree if (key > min & & key < max) { // Allocate memory for root of this subtree and // increment *preIndex root = newNode(key); *preIndex = *preIndex + 1; if (*preIndex < size) { // Construct the subtree under root // All nodes which are in range {min .. key} // will go in left subtree, and first such node // will be root of left subtree. root-> left = constructTreeUtil(pre, preIndex, pre[*preIndex], min, key, size); } if (*preIndex < size) { // All nodes which are in range {key..max} will // go in right subtree, and first such node will // be root of right subtree. root-> right = constructTreeUtil(pre, preIndex, pre[*preIndex], key, max, size); } } return root; } // The main function to construct BST from given preorder // traversal. This function mainly uses constructTreeUtil() struct node* constructTree( int pre[], int size) { int preIndex = 0; return constructTreeUtil(pre, & preIndex, pre[0], INT_MIN, INT_MAX, size); } // A utility function to print inorder traversal of a Binary // Tree void printInorder( struct node* node) { if (node == NULL) return ; printInorder(node-> left); printf ("%d " , node-> data); printInorder(node-> right); } // Driver code int main() { int pre[] = { 10, 5, 1, 7, 40, 50 }; int size = sizeof (pre) / sizeof (pre[0]); // function call struct node* root = constructTree(pre, size); printf ( "Inorder traversal of the constructed tree: \n" ); printInorder(root); return 0; }

Java

// Java program to construct BST from given preorder // traversal // A binary tree node class Node { int data; Node left, right; Node( int d) { data = https://www.lsbin.com/d; left = right = null ; } } class Index { int index = 0 ; } class BinaryTree { Index index = new Index(); // A recursive function to construct BST from pre[]. // preIndex is used to keep track of index in pre[]. Node constructTreeUtil( int pre[], Index preIndex, int key, int min, int max, int size) { // Base case if (preIndex.index > = size) { return null ; } Node root = null ; // If current element of pre[] is in range, then // only it is part of current subtree if (key > min & & key < max) { // Allocate memory for root of this // subtree and increment *preIndex root = new Node(key); preIndex.index = preIndex.index + 1 ; if (preIndex.index < size) { // Construct the subtree under root // All nodes which are in range {min .. key} // will go in left subtree, and first such // node will be root of left subtree. root.left = constructTreeUtil( pre, preIndex, pre[preIndex.index], min, key, size); } if (preIndex.index < size) { // All nodes which are in range {key..max} // will go in right subtree, and first such // node will be root of right subtree. root.right = constructTreeUtil( pre, preIndex, pre[preIndex.index], key, max, size); } } return root; } // The main function to construct BST from given // preorder traversal. This function mainly uses // constructTreeUtil() Node constructTree( int pre[], int size) { int preIndex = 0 ; return constructTreeUtil(pre, index, pre[ 0 ], Integer.MIN_VALUE, Integer.MAX_VALUE, size); } // A utility function to print inorder traversal of a // Binary Tree void printInorder(Node node) { if (node == null ) { return ; } printInorder(node.left); System.out.print(node.data +" " ); printInorder(node.right); } // Driver code public static void main(String[] args) { BinaryTree tree = new BinaryTree(); int pre[] = new int [] { 10 , 5 , 1 , 7 , 40 , 50 }; int size = pre.length; // Function call Node root = tree.constructTree(pre, size); System.out.println( "Inorder traversal of the constructed tree is " ); tree.printInorder(root); } } // This code has been contributed by Mayank Jaiswal

python

# A O(n) program for construction of BST from preorder traversal INT_MIN = float ( "-infinity" ) INT_MAX = float ( "infinity" ) # A Binary tree node class Node: # Constructor to created a new node def __init__( self , data): self .data = https://www.lsbin.com/data self .left = None self .right = None # Methods to get and set the value of static variable # constructTreeUtil.preIndex for function construcTreeUtil() def getPreIndex(): return constructTreeUtil.preIndex def incrementPreIndex(): constructTreeUtil.preIndex + = 1 # A recursive function to construct BST from pre[]. # preIndex is used to keep track of index in pre[] def constructTreeUtil(pre, key, mini, maxi, size): # Base Case if (getPreIndex() > = size): return None root = None # If current element of pre[] is in range, then # only it is part of current subtree if (key > mini and key < maxi): # Allocate memory for root of this subtree # and increment constructTreeUtil.preIndex root = Node(key) incrementPreIndex() if (getPreIndex() < size): # Construct the subtree under root # All nodes which are in range {min.. key} will # go in left subtree, and first such node will # be root of left subtree root.left = constructTreeUtil(pre, pre[getPreIndex()], mini, key, size) if (getPreindex() < size): # All nodes which are in range{key..max} will # go to right subtree, and first such node will # be root of right subtree root.right = constructTreeUtil(pre, pre[getPreIndex()], key, maxi, size) return root # This is the main function to construct BST from given # preorder traversal. This function mainly uses # constructTreeUtil() def constructTree(pre): constructTreeUtil.preIndex = 0 size = len (pre) return constructTreeUtil(pre, pre[ 0 ], INT_MIN, INT_MAX, size) # A utility function to print inorder traversal of Binary Tree def printInorder(node): if node is None : return printInorder(node.left) print node.data, printInorder(node.right) # Driver code pre = [ 10 , 5 , 1 , 7 , 40 , 50 ] # Function call root = constructTree(pre) print"Inorder traversal of the constructed tree: " printInorder(root) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// C# program to construct BST from given preorder traversal using System; // A binary tree node public class Node { public int data; public Node left, right; public Node( int d) { data = https://www.lsbin.com/d; left = right = null ; } } public class Index { public int index = 0; } public class BinaryTree { public Index index = new Index(); // A recursive function to construct BST from pre[]. // preIndex is used to keep track of index in pre[]. public virtual Node constructTreeUtil( int [] pre, Index preIndex, int key, int min, int max, int size) { // Base case if (preIndex.index > = size) { return null ; } Node root = null ; // If current element of pre[] is in range, then // only it is part of current subtree if (key > min & & key < max) { // Allocate memory for root of this subtree // and increment *preIndex root = new Node(key); preIndex.index = preIndex.index + 1; if (preIndex.index < size) { // Construct the subtree under root // All nodes which are in range // {min .. key} will go in left // subtree, and first such node will // be root of left subtree. root.left = constructTreeUtil( pre, preIndex, pre[preIndex.index], min, key, size); } if (preIndex.index < size) { // All nodes which are in range // {key..max} will go in right // subtree, and first such node // will be root of right subtree. root.right = constructTreeUtil( pre, preIndex, pre[preIndex.index], key, max, size); } } return root; } // The main function to construct BST from given // preorder traversal. This function mainly uses // constructTreeUtil() public virtual Node constructTree( int [] pre, int size) { return constructTreeUtil(pre, index, pre[0], int .MinValue, int .MaxValue, size); } // A utility function to print inorder traversal of a // Binary Tree public virtual void printInorder(Node node) { if (node == null ) { return ; } printInorder(node.left); Console.Write(node.data +" " ); printInorder(node.right); } // Driver code public static void Main( string [] args) { BinaryTree tree = new BinaryTree(); int [] pre = new int [] { 10, 5, 1, 7, 40, 50 }; int size = pre.Length; // Function call Node root = tree.constructTree(pre, size); Console.WriteLine( "Inorder traversal of the constructed tree is " ); tree.printInorder(root); } } // This code is contributed by Shrikant13

输出如下

Inorder traversal of the constructed tree: 1 5 7 10 40 50

时间复杂度：O(n^2)
我们很快将在另一篇文章中发布O(n)迭代解决方案。
【如何根据给定的遍历构造BST（ |S1）】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

推荐阅读

• 

  南宁：房贷利率新政实施后买房能省多少钱？
• 

  drive|希捷推出 Xbox 专用外置 SSD：1TB 约 1095元，USB 3.2 Gen1 接口
• 

  农户贷款如何界定 「一般农户指什么」
• 

  java用什么软件写代码，JAVA用什么软件编写
• 

  不要吃发物 不要吃过甜过咸和酸性的食物
• 

  八角金盘的介绍-八角金盘的作用
• 

  flutter添加横线，flutter虚线边框
• 

  为什么戒烟后会发胖？
• 

  佛珠多肉烂根怎么办 佛珠多肉烂了怎么办
• 

  中国知名菜刀有什么牌子？中国十大菜刀品牌排行
• 

  从入门到精通，轻松应对各种错误 打印机1700代码解析
• 

  水果礼盒制作步骤大全图解 水果礼盒的制作技巧是怎么样的
• 

  支付宝花呗当面花怎么使用？使用方法及店铺详细介绍
• 

  恒为科技的军方服务器具有怎样的性能？ 恒为科技军方服务器怎么样
• 

  gis中画的图成无效的书签，gis图没了
• 

  工商银行主要业务有哪些
• 

  iphone皮套
• 

  爱普生1430喷墨机清零
• 

  关于vb.neteval的信息
• 

  非诚勿扰影视产业分析

• Java中抽象类和接口之间有什么区别（）
• 页面布局（CSS如何使用flex属性（））
• 多线程编程（C/C++如何使用线程函数（））
• 在C ++中将字符串和数字互相转换
• 电脑公司windows7 64位纯净版旗舰最新系统推荐
• 雨林木风ghost win8 64位精简优化版最新系统推荐
• 最新萝卜家园win764旗舰版最新系统推荐
• 深度技术win7专业版32位纯净版最新系统推荐
• dell windows8 64位专业版最新系统推荐