第四講樹（中）_ZenDei技術網路在線

04 樹4：是否同一棵二叉搜索樹 Description: 給定一個插入序列就可以唯一確定一棵二叉搜索樹。然而，一棵給定的二叉搜索樹卻可以由多種不同的插入序列得到。例如分別按照序列{2, 1, 3}和{2, 3, 1}插入初始為空的二叉搜索樹，都得到一樣的結果。於是對於輸入的各種插入序列，你需要判斷 ...

04-樹4：是否同一棵二叉搜索樹

Description:

給定一個插入序列就可以唯一確定一棵二叉搜索樹。然而，一棵給定的二叉搜索樹卻可以由多種不同的插入序列得到。例如分別按照序列{2, 1, 3}和{2, 3, 1}插入初始為空的二叉搜索樹，都得到一樣的結果。於是對於輸入的各種插入序列，你需要判斷它們是否能生成一樣的二叉搜索樹。

Input:

輸入包含若幹組測試數據。每組數據的第1行給出兩個正整數N≤10和L，分別是每個序列插入元素的個數和需要檢查的序列個數。第2行給出N個以空格分隔的正整數，作為初始插入序列。最後L行，每行給出N個插入的元素，屬於L個需要檢查的序列。

簡單起見，我們保證每個插入序列都是1到N的一個排列。當讀到N為0時，標誌輸入結束，這組數據不要處理。

Output:

對每一組需要檢查的序列，如果其生成的二叉搜索樹跟對應的初始序列生成的一樣，輸出“Yes”，否則輸出“No”。

SampleInput:

4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0

SampleOutput:

Yes
No
No

Codes:

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode* Tree;
struct TreeNode
{
    int data;
    Tree left,right;
    int flag;
}; 

Tree NewNode(int data)
{
    Tree T = (Tree)malloc(sizeof(struct TreeNode));
    T->data = data;
    T->left = T->right = NULL;
    T->flag = 0;
    return T;
}

Tree Insert(Tree T,int data)
{
    if( !T )
        T = NewNode(data);
    else {
        if(data > T->data)
            T->right = Insert(T->right, data);
        else
            T->left = Insert(T->left, data);
    }
    return T;
}

Tree MakeTree(int N)
{
    Tree T;
    int data;
    scanf("%d",&data);
    T = NewNode(data);
    for(int i = 1; i < N; i++) {
        scanf("%d",&data);
        T = Insert(T,data);
    }
    return T;
}

bool check (Tree T,int data)
{
    if(T->flag) {
        if(data < T->data)
            return check(T->left,data);
        else if(data > T->data)
            return check(T->right,data);
    }else {
        if(data == T->data) {    //是要找的結點 
            T->flag = 1;
            return true;
        }
        else return false;            //不是 不一致 
    }
}

int Judge(Tree T,int N)
{
    int data;
    int flag = 0;//0代表目前仍一致 1代表已經不一致
    scanf("%d",&data);
    if(data != T->data)    //    判斷根節點是否一致 
        flag = 1; 
    else T->flag = 1;
    for(int i = 1; i < N; i++) {    //確保L讀完 
        scanf("%d",&data);
        if( (!flag) && (!check(T,data)) )    //不一致 
            flag = 1;
    }
    if(flag)     //不一致 
        return 0;
    else return 1;
}

void ResetT(Tree T)//清除T中各結點的flag標記
{
    if(T->left)
        ResetT(T->left);
    if(T->right)
        ResetT(T->right);
    T->flag = 0;
} 

void FreeTree(Tree T) //釋放T的空間
{
    if(T->left)
        FreeTree(T->left);
    if(T->right)
        FreeTree(T->right);
    free(T);
} 

int main()
{
    int N, L;
    Tree T;
    scanf("%d",&N);
    while(N) {
        scanf("%d",&L);
        T = MakeTree(N);
        for(int i = 0; i < L; i++) {
            if(Judge(T, N))
                printf("Yes\n");
            else
                printf("No\n");
            ResetT(T);        //清除T中的標記flag 
        } 
        FreeTree(T);
        scanf("%d",&N);
    }
    
    return 0;
}

PAT-1066:Root of AVL Tree.

Description:

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.

Input:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output:

For each test case, print ythe root of the resulting AVL tree in one line.

SampleInput1:

5
88 70 61 96 120

SampleOutput1:

SampleInput2:

7
88 70 61 96 120 90 65

SampleOutput2:

Codes:

#include <cstdio>
#include <algorithm>
using namespace std;
struct node{
    node *left, *right;
    int v, w;
    node(int value, node* l, node* r) : v(value), left(l), right(r), w(0) {}
};
node *nil = new node(0, NULL, NULL);
node *head = nil;
void leftrotate(node *&head){
    node *t = head->right;
    head->right = t->left;
    t->left = head;
    head = t;
    head->left->w = max(head->left->right->w, head->left->left->w) + 1;
    head->w = max(head->right->w, head->left->w) + 1;
}
void rightrotate(node *&head){
    node *t = head->left;
    head->left = t->right;
    t->right = head;
    head = t;
    head->right->w = max(head->right->right->w, head->right->left->w) + 1;
    head->w = max(head->right->w, head->left->w) + 1;
}
void insert(node *&head, int v){
    if (head == nil){
        head = new node(v, nil, nil);
    }else if (v > head->v){
        insert(head->right, v);
        if (2 == head->right->w - head->left->w){
            if (v > head->right->v){
                leftrotate(head);
            }else{
                rightrotate(head->right);
                leftrotate(head);
            }
        }
    }else{
        insert(head->left, v);
        if (2 == head->left->w - head->right->w){
            if (v <= head->left->v){
                rightrotate(head);
            }else{
                leftrotate(head->left);
                rightrotate(head);
            }
        }
    }
    head->w = max(head->left->w, head->right->w) + 1;
}
int main()
{
    int n, a;
    scanf("%d", &n);
    while (n--){
        scanf("%d", &a);
        insert(head, a);
    }
    printf("%d\n", head->v);
    return 0;
}

PAT-1064:Complete Binary Search Tree.

Description:

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.
A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right.

Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST.

Input:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=1000). Then N distinct non-negative integer keys are given in the next line. All the numbers in a line are separated by a space and are no greater than 2000.

Output:

For each test case, print in one line the level order traversal sequence of the corresponding complete binary search tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

SampleInput:

10
1 2 3 4 5 6 7 8 9 0

SampleOutput:

6 3 8 1 5 7 9 0 2 4

Codes:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<int> preOrder;

void PreTraversal(int root)
{
    if (root > n)
        return;
    PreTraversal(2 * root);
    preOrder.push_back(root);
    PreTraversal(2 * root + 1);
}

int main()
{
    cin >> n;

    int num[1001], levelOrder[1001];
    for (int i = 0; i < n; i++)
        cin >> num[i];

    sort(num, num + n);
    PreTraversal(1);
    for (int i = 0; i < preOrder.size(); i++)
        levelOrder[preOrder[i]] = num[i];
    for (int i = 1; i < n; i++)
        cout << levelOrder[i] << " ";
    cout << levelOrder[n];
        
}

第四講 樹（中）

04-樹4：是否同一棵二叉搜索樹

Description:

Input:

Output:

SampleInput:

SampleOutput:

Codes:

PAT-1066:Root of AVL Tree.

Description:

Input:

Output:

SampleInput1:

SampleOutput1:

SampleInput2:

SampleOutput2:

Codes:

PAT-1064:Complete Binary Search Tree.

Description:

Input:

Output:

SampleInput:

SampleOutput:

Codes:

第四講樹（中）