Aizu

链表允许我们添加、删除、搜索数据,这种数据结构会在执行时申请必要的内存空间,便于管理动态集合。但是链表的时间复杂度为O(n)。相比之下,使用动态树结构能更加有效地添加、删除和搜索数据。

搜索树是一种可以进行动态插入、搜索、删除等操作的数据结构,可以用作字典或优先级队列。二叉搜索树属于最基本的搜索树。

二叉搜索树的各结点都拥有键值,且满足二叉搜索树的性质:

  设x为二叉搜索树的结点。如果y为x左子树中的结点,那么y的键值≤x的键值。另外,如果z为x右子树中的结点,那么x的键值≤z的键值。

以上图键值为80的结点为例,它的左子树中所有结点的键值都不超过80,右子树中所有结点的键值都不小于80。如果对二叉搜索树执行中序遍历,我们会得到一个按升序排列的键值序列。

实现二叉搜索树时,要保证数据经过插入或者删除操作后,所有结点仍然保持上述性质。与表一样,我们通过指针将结点连接成一棵树,各结点内包含值(键值)以及指向父结点、左子结点、右子结点的指针。

Binary Search Tree I

Search trees are data structures that support dynamic set operations including insert, search, delete and so on. Thus a search tree can be used both as a dictionary and as a priority queue.

Binary search tree is one of fundamental search trees. The keys in a binary search tree are always stored in such a way as to satisfy the following binary search tree property:

  • Let xx be a node in a binary search tree. If yy is a node in the left subtree of xx, then y.keyx.keyy.key≤x.key. If yy is a node in the right subtree of xx, then x.keyy.keyx.key≤y.key.

The following figure shows an example of the binary search tree.

 

For example, keys of nodes which belong to the left sub-tree of the node containing 80 are less than or equal to 80, and keys of nodes which belong to the right sub-tree are more than or equal to 80. The binary search tree property allows us to print out all the keys in the tree in sorted order by an inorder tree walk.

A binary search tree should be implemented in such a way that the binary search tree property continues to hold after modifications by insertions and deletions. A binary search tree can be represented by a linked data structure in which each node is an object. In addition to a key field and satellite data, each node contains fields leftright, and p that point to the nodes corresponding to its left child, its right child, and its parent, respectively.

To insert a new value vv into a binary search tree TT, we can use the procedure insert as shown in the following pseudo code. The insert procedure is passed a node zzfor which z.key=vz.key=v, z.left=NILz.left=NIL, and z.right=NILz.right=NIL. The procedure modifies TT and some of the fields of zz in such a way that zz is inserted into an appropriate position in the tree.

1 insert(T, z)
2     y = NIL // parent of x
3     x = 'the root of T'
4     while x ≠ NIL
5         y = x // set the parent
6         if z.key < x.key
7             x = x.left // move to the left child
8         else 
9             x = x.right // move to the right child
10    z.p = y
11
12    if y == NIL // T is empty
13        'the root of T' = z
14    else if z.key < y.key
15        y.left = z // z is the left child of y
16    else 
17        y.right = z // z is the right child of y

Write a program which performs the following operations to a binary search tree TT.

  • insert kk: Insert a node containing kk as key into TT.
  • print: Print the keys of the binary search tree by inorder tree walk and preorder tree walk respectively.

You should use the above pseudo code to implement the insert operation. TT is empty at the initial state.

Input

In the first line, the number of operations mm is given. In the following mm lines, operations represented by insert kk or print are given.

Output

For each print operation, print a list of keys obtained by inorder tree walk and preorder tree walk in a line respectively. Put a space character before each key.

Constraints

  • The number of operations 500,001≤500,001
  • The number of print operations 10≤10.
  • 2,000,000,000key2,000,000,000−2,000,000,000≤key≤2,000,000,000
  • The height of the binary tree does not exceed 100 if you employ the above pseudo code.
  • The keys in the binary search tree are all different.

Sample Input 1

8
insert 30
insert 88
insert 12
insert 1
insert 20
insert 17
insert 25
print

Sample Output 1

 1 12 17 20 25 30 88
 30 12 1 20 17 25 88
#include<iostream>
#include<cstdlib>
#include<string>
using namespace std;
struct Node
{
    int key;
    Node *right, *left, *parent;
};
Node *root;
void insert(int k)
{
    Node *y = NULL;
    Node *x = root;//
    Node *z;
    z = (Node *)malloc(sizeof(Node));
    z->key = k;
    z->left = NULL;
    z->right = NULL;
    while (x)
    {
        y = x;//设置父结点
        if (z->key<x -> key)
            x = x->left;//移动至左结点
        else
            x = x->right;//移动至右结点
    }
    z->parent = y;
    if (y == NULL)//树为空树时
        root = z;
    else
        if (z->key<y->key)
            y->left = z;//将z定为y的左子结点
        else
            y->right = z;//将z定为y的右子结点
}
void inorder(Node *u)//中序遍历
{
    if (u == NULL)
        return;
    inorder(u->left);
    cout << " " << u->key;
    inorder(u->right);
}
void preorder(Node *u)//前序遍历
{
    if (u == NULL)
        return;
    cout << " " << u->key;
    preorder(u->left);
    preorder(u->right);
}
int main()
{
    int n;
    cin >> n;
    string com;
    for (int i = 0; i<n; i++)
    {
        cin >> com;
        if (com == "insert")
        {
            int x;
            cin >> x;
            insert(x);
        }
        else if (com == "print")
        {
            inorder(root);
            cout << endl;
            preorder(root);
            cout << endl;
        }
    }
    return 0;
}
原文地址:https://www.cnblogs.com/orion7/p/7561743.html