算法刷题笔记五之二叉树中篇

1.是否同一棵二叉搜索树

Problem
给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。详细描述

Analysis

1. 确定树的链表表示，根据第一输入序列建立一棵二叉搜索树，然后判断余下的序列与建立的树是否一致。
2. 如何判断输入序列是否一致？可以在树BST中按顺序搜索输入序列的元素，如果搜索所经过的节点在前面都出现过，则一致。对于每个树节点可设置一个tag表示该节点是否被访问过。
3. 本题需要注意的是，如果发现序列与二叉搜索树不一致时，不需要进行check判断，但还是要遍历完该行序列，不然会影响后面数据输入正确性。

Code

#include <stdio.h>
#include <stdlib.h>
using namespace std;

typedef int ElementType;
typedef struct TreeNode* BinTree;
struct TreeNode {
    ElementType data;
    BinTree left;
    BinTree right;  
    int tag;
};

// 清空树，释放空间
void freeTree(BinTree BST) {
    if(BST->left) freeTree(BST->left);
    if(BST->right) freeTree(BST->right);
    free(BST);
}

// 初始化tag为未被访问状态 
void resetTag(BinTree BST) {
    if(BST->left) resetTag(BST->left);
    if(BST->right) resetTag(BST->right);
    BST->tag = 0;
}

//
BinTree newNode(int data) {
    BinTree node = (BinTree)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = node->right = NULL;
    node->tag = 0;
    return node;
} 

// 二叉搜索树中插入节点 
BinTree insert(BinTree BST, int data) {
    if(!BST) BST = newNode(data);
    else {
        if(data > BST->data) {
            BST->right = insert(BST->right, data);
        } else if(data < BST->data) {
            BST->left = insert(BST->left, data);
        }
    }
    return BST;
}


// 建立二叉搜索树 
BinTree buildTree(int N){
    int data;
    scanf("%d", &data);
    BinTree BST = newNode(data);
    for(int i = 1; i < N; i++) {
        scanf("%d", &data);
        BST = insert(BST, data);
    }
    return BST;
}

// 判断当前结点是否一致
int check(BinTree BST, ElementType data) {
    if(BST->tag) {
        if(data < BST->data) return check(BST->left, data);
        else if(data > BST->data) return check(BST->right, data);
        else return 0;
    } else {
        if(data == BST->data) {
            BST->tag = 1;
            return 1;
        }
        return 0;
    }
} 

// 判断序列是否同为一棵二叉搜索树 
int judge(BinTree BST, int N) {
    int data, flag = 1; // flag=1表示目前一致 

    scanf("%d", &data);
    if(data != BST->data) flag = 0;
    else BST->tag = 1;
    for(int i = 1; i < N; i++) {
        scanf("%d", &data);
        if(flag == 1 && !check(BST, data)) flag = 0;
    }
    
    if(flag == 0) return 0;
    return 1;
}

int main() {
    int N,L;
    BinTree BST;
    
    #ifndef ONLINE_JUDGE
    freopen("BSTree.txt", "r", stdin);
    #endif
    
    scanf("%d", &N);
    while(N) {
        scanf("%d", &L);
        BST = buildTree(N);
        for(int i = 0; i < L; i++) {
            if(judge(BST, N)) {
                printf("Yes\n");
            } else {
                printf("No\n");
            }
            resetTag(BST);
        }
        freeTree(BST);
        scanf("%d", &N);
    }
    
    return 0;
} 

2.Root of AVL Tree

Problem
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.详细描述

Property

1. 旋转:被破坏节点与破坏结点的路径决定是什么类型的旋转(LL,RR,LR,RL),然后关注从被破坏结点开始(包括被破坏节点)的三个结点如何调整，旋转的根节点一定是这三者中中间大的那个。
2. 设N(h)高度为h的平衡二叉树的最少结点数，则有 N(h) = N(h-1) + N(h-2) + 1

Analysis
实质是构建一棵平衡二叉树得过程，如果平衡被破坏则通过旋转重新使得树平衡。

Code

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

typedef int ElementType;
typedef struct AVLNode* AVLTree;
struct AVLNode {
    ElementType value;
    int height;
    AVLTree left;
    AVLTree right;
};

int getHeight(AVLTree T);
int max(int a, int b);

AVLTree LLRotate(AVLTree root);
AVLTree RRRotate(AVLTree root);
AVLTree LRRotate(AVLTree root);
AVLTree RLRotate(AVLTree root);

AVLTree insert(AVLTree T, ElementType val);

//------------------------------
int max(int a, int b){
    return a > b ? a : b;
}
    
        
int getHeight(AVLTree T) {
    if(T == NULL) {
        return -1;
    }
    return T->height;
}

AVLTree LLRotate(AVLTree root) {
    AVLTree newRoot = root->left;  
    root->left = newRoot->right;
    newRoot->right = root;
    
    root->height = max(getHeight(root->left), getHeight(root->right))+1;
    newRoot->height = max(getHeight(newRoot->left), getHeight(newRoot->right))+1;
    
    return newRoot;
}

AVLTree RRRotate(AVLTree root) {
    AVLTree newRoot = root->right; 
    root->right = newRoot->left;
    newRoot->left = root;
    
    root->height = max(getHeight(root->left), getHeight(root->right))+1;
    newRoot->height = max(getHeight(newRoot->left), getHeight(newRoot->right))+1;
    
    return newRoot;
}

AVLTree LRRotate(AVLTree root) {
     root->left = RRRotate(root->left);
     return LLRotate(root);
}

AVLTree RLRotate(AVLTree root) {
    root->right = LLRotate(root->right);
    return RRRotate(root);
}

// insert node and rebalanced
AVLTree insert(AVLTree T, ElementType val) {
    if(T == NULL) {
        T = (AVLTree)malloc(sizeof(struct AVLNode));
        T->value = val;
        T->height = 0;
        T->left = NULL;
        T->right = NULL;
    } else {
        if(val < T->value) {
            T->left = insert(T->left, val);
            
            // check this tree is balanced or not
            if(getHeight(T->left) - getHeight(T->right) == 2) {
                if(val < T->left->value) {
                    T = LLRotate(T);
                } else {
                    T = LRRotate(T);
                }
            }
        } else if(val > T->value) {
            T->right = insert(T->right, val);
            
            if(getHeight(T->left) - getHeight(T->right) == -2) {
                if(val > T->right->value) {
                    T = RRRotate(T);
                } else {
                    T = RLRotate(T);
                }   
            } 
        } 
    }
    
    T->height = max(getHeight(T->left), getHeight(T->right))+1;
    
    return T;
}

int main()
{
    int num,val; 
    AVLTree T=NULL; // must be NULL else error

    #ifndef ONLINE_JUDGE
    freopen("BBTree.txt", "r", stdin);
    #endif
    
    // read node num
    scanf("%d\n", &num);
    
    // loop build the balanced binary tree and get root
    for(int i = 0; i < num; i++) {
        scanf("%d", &val);
        T = insert(T, val);
        //printf("%d ", val); 
    }
    
    printf("%d\n", T->value);
        
    return 0;
} 

参考资料：
1.AVL树的构建
2.AVL平衡二叉树

3.Complete Binary Search Tree

Problem
给出构成一棵树的序列，已知该树为完全二叉搜索树的序列，求层次遍历顺序。详细描述

Analysis

1. 对于二叉搜索树，中序遍历为从小到大的序列，那么问题可以转化为已知中序求层次遍历顺序。
2. 建树过程根据中序遍历建树，则为建立左子树，构造根，建立右子树。与中序遍历LVR有异曲同工之妙。
3. 层次遍历输出对于数组存储的二叉查找树来说，即遍历顺序。

Code

#include <iostream>
#include <algorithm>
using namespace std;

const int MaxSize = 1001;
int N;
int in[MaxSize], tree[MaxSize]; 
int index = 1;

void buildTree(int root) 
{
    if(root > N) return ; 
    int leftIndex = root*2;
    int rightIndex = leftIndex+1;
    buildTree(leftIndex);
    tree[root] = in[index++];
    buildTree(rightIndex);
}

// 对于数组存储的二叉树，顺序输出即 层次遍历结果 
void levelOrderTraversal() 
{
    cout<<tree[1];
    for(int i = 2; i <= N; i++) 
    {
        cout<<" "<<tree[i];
    }
    cout<<endl;
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("CBSTree.txt", "r", stdin);
    #endif
    
    scanf("%d", &N);
    for(int i = 1; i <= N; i++) {
        scanf("%d", &in[i]);
    }
    // 排序得到中序遍历结果 
    sort(in+1, in+N+1);
    // 根据中序遍历构建完全二插搜索树
    buildTree(1); 
    levelOrderTraversal();
    
    return 0;
}

4.二叉搜索树的操作集

Problem
本题要求实现给定二叉搜索树的5种常用操作。详细描述

Analysis
考察二叉搜索树的基本操作，递归版本和非递归版本都要掌握，其中删除结点需要重点掌握。

Code

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

typedef int ElementType;
typedef struct TNode* Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

void PreorderTraversal( BinTree BT ); /* 先序遍历，由裁判实现，细节不表 */
void InorderTraversal( BinTree BT );  /* 中序遍历，由裁判实现，细节不表 */

BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );

int main()
{
    BinTree BST, MinP, MaxP, Tmp;
    ElementType X;
    int N, i;
    
    #ifndef
    freopen("BSTreeOpre.txt", "r", stdin);
    #endif

    BST = NULL;
    scanf("%d", &N);
    for ( i=0; i<N; i++ ) {
        scanf("%d", &X);
        BST = Insert(BST, X);
    }
    printf("Preorder:"); PreorderTraversal(BST); printf("\n");
    MinP = FindMin(BST);
    MaxP = FindMax(BST);
    scanf("%d", &N);
    for( i=0; i<N; i++ ) {
        scanf("%d", &X);
        Tmp = Find(BST, X);
        if (Tmp == NULL) printf("%d is not found\n", X);
        else {
            printf("%d is found\n", Tmp->Data);
            if (Tmp==MinP) printf("%d is the smallest key\n", Tmp->Data);
            if (Tmp==MaxP) printf("%d is the largest key\n", Tmp->Data);
        }
    }
    scanf("%d", &N);
    for( i=0; i<N; i++ ) {
        scanf("%d", &X);
        BST = Delete(BST, X);
    }
    printf("Inorder:"); InorderTraversal(BST); printf("\n");

    return 0;
}

//-----------------------------------------------------
void PreorderTraversal(BinTree BT) {
    if(BT) {
        printf("%d ", BT->Data);
        PreorderTraversal(BT->Left);
        PreorderTraversal(BT->Right);
    }
} 

void InorderTraversal(BinTree BT) {
    if(BT) {
        InorderTraversal(BT->Left);
        printf("%d ", BT->Data);
        InorderTraversal(BT->Right);
    }
}

BinTree Insert( BinTree BST, ElementType X ) {
    if(BST == NULL) {
        BST = (BinTree)malloc(sizeof(struct TNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    } else {
        if(X < BST->Data) {
            BST->Left = Insert(BST->Left, X);
        } else if(X > BST->Data) {
            BST->Right = Insert(BST->Right, X);
        }
    }
    return BST;
}

BinTree Delete( BinTree BST, ElementType X ) {
    Position tmp;
    if(BST == NULL) { 
        printf("Not Found\n");
    }
    else if(X < BST->Data) {
        BST->Left = Delete(BST->Left, X); 
    } else if(X > BST->Data) {
        BST->Right = Delete(BST->Right, X);
    } else {
        if(BST->Left && BST->Right) {
            tmp = FindMin(BST->Right);
            BST->Data = tmp->Data;
            BST->Right = Delete(BST->Right, BST->Data);
        } else {
            tmp = BST;
            if(!BST->Left) {
                BST = BST->Right;
            } else if(!BST->Right) {
                BST = BST->Left;
            }
            free(tmp);
        }
    }
    
    return BST;
}

Position Find( BinTree BST, ElementType X ) {
    if(BST == NULL) return NULL;
    Position T = BST;
    if(X < T->Data) T = Find(T->Left, X);
    else if(X > T->Data) T = Find(T->Right, X);
    
    return T;   
}

Position FindMin( BinTree BST ) {
    if(BST == NULL) return NULL;
    Position T = BST;
    while(T->Left) {
        T = T->Left;
    }
    return T;
}

Position FindMax( BinTree BST ) {
    if(BST == NULL) return NULL;
    Position T = BST;
    while(T->Right) {
        T = T->Right;
    }
    return T;
}

声明：本站所有文章均为原创或翻译，遵循署名 - 非商业性使用 - 禁止演绎 4.0 国际许可协议，如需转载请确保您对该协议有足够了解，并附上作者名 (Tsukasa) 及原文地址