04079: 二叉搜索树

http://cs101.openjudge.cn/dsapre/04079/

二叉搜索树在动态查表中有特别的用处，一个无序序列可以通过构造一棵二叉搜索树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉搜索树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。

这里，我们想探究二叉树的建立和序列输出。

输入

只有一行，包含若干个数字，中间用空格隔开。（数字可能会有重复）

输出

输出一行，对输入数字建立二叉搜索树后进行前序周游的结果。

样例输入

41 467 334 500 169 724 478 358 962 464 705 145 281 827 961 491 995 942 827 436

样例输出

41 467 334 169 145 281 358 464 436 500 478 491 724 705 962 827 961 942 995

要解决这个问题，首先需要了解二叉搜索树（Binary Search Tree，BST）的基本属性和操作。二叉搜索树是一种特殊的二叉树，满足以下性质：

每个节点的键值大于其左子树上任意节点的键值。
每个节点的键值小于其右子树上任意节点的键值。
左右子树也分别为二叉搜索树。

在BST上进行前序遍历（Preorder Traversal）可以按照以下步骤进行：

访问根节点。
递归地对左子树进行前序遍历。
递归地对右子树进行前序遍历。

如果使用迭代而不是递归，您可以使用栈（Stack）数据结构来实现前序遍历。

python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def insert_into_bst(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_into_bst(root.left, val)
    elif val > root.val:
        root.right = insert_into_bst(root.right, val)
    return root

def preorder_traversal(root):
    return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right) if root else []

def preorderTraversal(root):
    if root is None:
        return []

    stack = []
    result = []
    stack.append(root)

    while stack:
        node = stack.pop()
        result.append(node.val)

        # 先将右子节点入栈，再将左子节点入栈
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result

# 读取输入并转换成整数列表
numbers = list(map(int, input().split()))

# 构造二叉搜索树
bst_root = None
for num in numbers:
    bst_root = insert_into_bst(bst_root, num)

# 前序遍历二叉搜索树并输出
#print(' '.join(map(str, preorder_traversal(bst_root))))
print(' '.join(map(str, preorderTraversal(bst_root))))

c++

#include <iostream>

using namespace std;

struct Node {
	int num;
	Node *left, *right;
	
	Node(int n) : num(n), left(NULL), right(NULL) {}
};

void insert(Node *&root, int num) {
	if (root == NULL) {
		root = new Node(num);
		return;
	}
	
	if (num == root->num) {
		return;
	}
	
	if (num < root->num) {
		insert(root->left, num);
	} else {
		insert(root->right, num);
	}
}

void preorder(Node *root) {
	if (!root)
		return;
	cout << root->num << " ";
	preorder(root->left);
	preorder(root->right);
}

void deleteTree(Node *root) {
	if (!root)
		return;
	deleteTree(root->left);
	deleteTree(root->right);
	delete root;
}

int main() {
	Node *root = NULL;
	int num;
	while (cin >> num) {
		insert(root, num);
	}
	
	preorder(root);
	cout << endl;
	
	deleteTree(root);
	return 0;
}

04079: 二叉搜索树 ​

04079: 二叉搜索树