007's Studio.

算法导论练习12.1

算法导论 二叉搜索树
字数统计: 1.1k阅读时长: 4 min
2019/08/08 Share

12.1-1 对于关键字集合$\{1,4,5,10,16,17,21\}$，分别画出高度为2、3、4、5和6的二叉搜索树。

这里说明一下：算法导论中定义的高度是根节点到叶节点的最大距离

高度为2：      高度为3：                高度为4：
    10              10                      5
   /  \            /  \                    /  \
  4    17         4   16                  4    10
 / \   /\        / \   \                 /      \
1   5 16 21     1   5   17              1        16
                         \                         \
                          21                        17
                                                     \
                                                      21
高度为5：           高度为6：
    4                       1
   / \                       \
  1   5                       4
       \                       \
        10                      5
         \                       \
          16                      10
           \                        \
            17                       16
             \                         \
              21                        17 
                                          \
                                           21

12.1-2 二叉搜索树的性质与最小堆性质之间有什么不同？能使用最小堆性质在$O(n)$时间内按序输出一颗n个结点树的关键字吗？可以的话，说明如何做，否则解释理由。

最小堆是一棵近似的完全二叉树(Perfect Binary Tree),满足堆中每个结点小于等于子结点。但是左右孩子之间的没有确定的大小关系。要想按序输出最小堆，需要使用堆排序的时间复杂度为$\Omega(nlgn)$。

12.1-3 设计一个执行中序遍历的非递归算法。（提示：一个容易的方法是使用栈作为辅助数组结构；另一种较复杂但比较简介的做法是不使用栈，但要假设能测试两个指针是否相等）。

这个问题和算法导论练习10.4-3和10.4-5的题目一致。我在另外一篇博客已经讲过，大家可以看下。
算法导论10.4-5题解

12.1-4 对于一棵有n个结点的树，请设计在$\Theta(n)$时间内完成的先序遍历算法和后序遍历算法。

下面是我的实现代码，分别给出了先序和后序遍历的递归和非递归实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<iostream>
#include<stack>
#define NIL -1
using namespace std;

struct Tree
{
	Tree *left;
	Tree *right;
	int key;
};
//创建二叉树
void createTree(Tree *&t)
{
    int key;
    cin >> key;
    if(key==NIL){
        t=nullptr;
        return;
    }
    t=new Tree();
    t->key=key;
    createTree(t->left);
    createTree(t->right);
}
void print(const Tree* x)
{
    cout << x->key << " ";
}
void preOrder_recursion(Tree* x)
{
    if(x)
    {
        print(x);
        preOrder_recursion(x->left);
        preOrder_recursion(x->right);
    }
}
void preOrder_byStack(Tree *x)
{
    stack<Tree*> sta;
    Tree *p=x;
    while(p||!sta.empty())
    {
    while(p)
    {
        print(p);
        sta.push(p);
        p=p->left;
    }
    p=sta.top();
    sta.pop();
    p=p->right;
    }
}
void postOrder_recursion(Tree *x)
{
    if(x)
    {
        postOrder_recursion(x->left);
        postOrder_recursion(x->right);
        print(x);
    }
}
void postOrder_byStack(Tree *x)
{
    Tree *pre=nullptr;
    stack<Tree*> sta;
    while(x||!sta.empty())
    {
        while(x)//达到左子树
        {
            sta.push(x);
            x=x->left;
        }
        x=sta.top();
        //没有右子树或右子树已访问
        if(!x->right||x->right==pre){
            sta.pop();
            print(x);
            pre=x;
            x=nullptr;
        }
        else
        {
            x=x->right;
        }
    }
}
int main()
{
    Tree *head;
    createTree(head);
    cout << "先序遍历递归版:\n";
    preOrder_recursion(head);
    cout << "\n先序遍历非递归版:\n";
    preOrder_byStack(head);
    cout << "\n后序遍历递归版:\n";    
    postOrder_recursion(head);
    cout << "\n后序遍历非递归版:\n";        
    postOrder_byStack(head);
}

这有两组测试数据，分别是题目12.1-1高度为2和6的二叉树。

数据1：
10 4 1 -1 -1 5 -1 -1 17 16 -1 -1 21 -1 -1
结果：
先序： 10 4 1 5 17 16 21
后序： 1 5 4 16 21 17 10

数据2：
1 -1 4 -1 5 -1 10 -1 16 -1 17 -1 21 -1 -1
结果：
先序：1 4 5 10 16 17 21
后序：21 17 16 10 5 4 1

12.1-5 因为在基于比较排序模型中，完成n个元素的排序，其最坏情况下需要$\Omega(nlgn)$时间。证明：任何基于比较的算法从n个元素的任意序列中构造一棵二叉搜索树，其最坏情况需要$\Omega(nlgn)$的时间。

证明：反证法，假设我们我可以在最坏情况$\omicron(nlgn)$下完成BST的建立。那么对于排序来说，我们可以通过构造BST树，然后遍历BST来实现。

根据定理12.1，我们可以在$\Theta(n)$的时间内完成对BST的遍历。那么意味着我们在$\omicron(nlgn)$的时间内完成对$n$个元素的排序算法。这与Chapter 8的基于比较的排序算法的下界为$\Omega(nlgn)$相矛盾。

因此，假设不成立。

原文作者：007havegone

原文链接：http://007havegone.github.io/2019/08/08/算法导论练习12-1/

发表日期：August 8th 2019, 11:54:03 pm

更新日期：August 9th 2019, 10:46:16 am

版权声明：‘原创内容，转载时请附上出处’

CATALOG
Total : 23
2019
算法导论 持久动态集合 二叉搜索树 逆序对 主方法 时间复杂度 算法分析 排序 线段树 中位数 二分查找 d叉堆 操作系统 Win10 cmd 二叉树 中序遍历 VS Code Markdown Tomcat IDEA Tomcat乱码 Server tomcat启动失败 Eclipse无法创建虚拟机 vm参数 Jdk版本过高 C++ Effective C++ 顺序统计树 Young氏矩阵 堆 红黑树 平衡树 数据结构
算法导论 操作系统 踩坑 Tomcat tomcat 读书笔记 数据结构 数据结构/算法导论