d526: Binary Search Tree (BST)

解題心得

在 insert function 要回傳 tree node 這邊卡超久，一開始沒加，還想說為什麼都沒被更新到。

後來才搞清楚丟到function裡的是a copy of pointer，兩個指標指到同樣的位置(此處為null)，如果要有預期的行為，就需要把function裡的pointer更新回去。 同理，動到left node跟right node也要接收遞迴函式的回傳值。

比對以前寫的類似的程式，才恍然大悟為什麼以前會用class寫──因為就不是copy一份過去了。

程式碼

#include <iostream>
using namespace std;
struct Node
{
	int data;
	Node* left; Node* right;
};

Node* insert(Node* tree, int val)
{
	
	if (tree == NULL)
	{
		tree = new Node;
		tree->data = val;
		tree->left = tree->right = NULL;
	}
	else
	{
		if (val < tree->data)
			tree->left = insert(tree->left, val);
		else
			tree->right = insert(tree->right, val);
	}
	return tree;
}

void printPreorder(Node* tree)
{
	if (tree == NULL) return;

	cout << tree->data << " ";
	printPreorder(tree->left);
	printPreorder(tree->right);
}

int main()
{
	int n, temp;
	while (cin >> n)
	{
		Node* root = NULL;
		while (n--)
		{
			cin >> temp;
			root = insert(root, temp);
		}
		printPreorder(root);
		cout << endl;
	}
	return 0;
}