(PAT 1099) Build A Binary Search Tree(通过哈希思想建立结点与左右子的关系)

偏执的太偏执、 2022-04-22 02:54 91阅读 0赞

099 Build A Binary Search Tree （30 分）

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

*  The left subtree of a node contains only nodes with keys less than the node's key.
 *  The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
 *  Both the left and right subtrees must also be binary search trees.

Given the structure of a binary tree and a sequence of distinct integer keys, there is only one way to fill these keys into the tree so that the resulting tree satisfies the definition of a BST. You are supposed to output the level order traversal sequence of that tree. The sample is illustrated by Figure 1 and 2.

![figBST.jpg][]

### Input Specification: ###

Each input file contains one test case. For each case, the first line gives a positive integer N (≤100) which is the total number of nodes in the tree. The next N lines each contains the left and the right children of a node in the format `left_index right_index`, provided that the nodes are numbered from 0 to N−1, and 0 is always the root. If one child is missing, then −1 will represent the NULL child pointer. Finally N distinct integer keys are given in the last line.

### Output Specification: ###

For each test case, print in one line the level order traversal sequence of that tree. All the numbers must be separated by a space, with no extra space at the end of the line.

### Sample Input: ###

9
    1 6
    2 3
    -1 -1
    -1 4
    5 -1
    -1 -1
    7 -1
    -1 8
    -1 -1
    73 45 11 58 82 25 67 38 42

### Sample Output: ###

58 25 82 11 38 67 45 73 42

思路:

这道题给出了各结点的左右子,使用数组下标法不是太方便,这个时候还是需要建立静态二叉树

struct node
    {
    	int data;
    	int lchild;
    	int rchild;
    
    }Nodes[101];

我们在读入数据时,就把各结点的左右子输入

for (int i = 0; i < n; ++i) {
    		int ln, rn;
    		cin >> ln >> rn;
    		Nodes[i].lchild = ln;
    		Nodes[i].rchild = rn;
    	}

之后我们通过中序遍历就可以把二叉查找树建立起来了(注意数组要排序):

int index = 0;
    void midTraverse(int root) {
    	if (Nodes[root].lchild != -1) {
    		midTraverse(Nodes[root].lchild);
    	}
    	Nodes[root].data = a[index++];
    	if (Nodes[root].rchild != -1) {
    		midTraverse(Nodes[root].rchild);
    	}
    }

最后利用队列层序输出即可

#include <iostream>
    #include <algorithm>
    #include <queue>
    using namespace std;
    int a[101];
    int n = 0;
    struct node
    {
    	int data;
    	int lchild;
    	int rchild;
    
    }Nodes[101];
    
    int index = 0;
    void midTraverse(int root) {
    	if (Nodes[root].lchild != -1) {
    		midTraverse(Nodes[root].lchild);
    	}
    	Nodes[root].data = a[index++];
    	if (Nodes[root].rchild != -1) {
    		midTraverse(Nodes[root].rchild);
    	}
    }
    
    void layerTraverse() {
    	queue<node> qque;
    	qque.push(Nodes[0]);
    
    	while (!qque.empty()) {
    		node currentNode = qque.front();		
    		if (currentNode.lchild != -1) {
    			qque.push(Nodes[currentNode.lchild]);
    		}
    		if (currentNode.rchild != -1) {
    			qque.push(Nodes[currentNode.rchild]);
    		}
    
    		if (qque.size() > 1) {
    			cout << currentNode.data << " ";
    		}
    		else {
    			cout << currentNode.data;
    		}
    		qque.pop();
    	}
    }
    
    int main() {
    
    	cin >> n;
    	for (int i = 0; i < n; ++i) {
    		int ln, rn;
    		cin >> ln >> rn;
    		Nodes[i].lchild = ln;
    		Nodes[i].rchild = rn;
    	}
    
    	
    	for (int j = 0; j < n; ++j) {
    		cin >> a[j];
    	}
    	sort(a, a + n);
    	midTraverse(0);
    	layerTraverse();
    	
    	system("PAUSE");
    	return 0;
    }

[figBST.jpg]: /images/20220422/efbf5259f73f4d6192341164d4d16669.png