二叉搜索树

Posted on   |   In   |  

主要介绍二叉树这种数据结构

二叉树

wiki上二叉树的介绍
二叉树的详细介绍
参阅：http://yameing.blog.163.com/blog/static/1120259402010088233927/
概念：二叉树就是每个结点最多有两个子树的树形存储结构。
二叉树

满二叉树：在一棵二叉树中，所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。
满二叉树
完全二叉树：完全二叉树是每个结点都与深度为k的满二叉树中编号从1到n一一对应。
完全二叉树

二叉树的表示方式

  1. 顺序(用数组存储)，简单但浪费空间
  2. 链式

二叉树的实现

带父亲节点的实现

二叉搜索树

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
//main.c

#define MAXWORD 100
struct tnode *addTree(struct tnode *, char *);
void treeprint(struct tnode *);
int getword(char *, int);

struct tnode{
    char *word;
    int count;
    struct tnode *left;
    struct tnode *right;
};

int main()
{
    struct tnode *root;
    char word[MAXWORD];
    
    root = NULL;
    while(getword(word, MAXWORD) != EOF){
        if (isalpha(word[0]))
            root = addTree(root, word);
    }
    treeprint(root);
    return 0;
}


/*
 *tree.c(binary search tree)
 */
struct tnode *talloc()
{
    struct tnode *p;
    p = (struct tnode*)malloc(sizeof(struct tonde));
    
    if(p == NULL){
        fprintf(stderr, "can't malloc memory\n");
        exit(0);
    }
    return p;
}

char *strdup(char *s)
{
    char *p;
    
    p = (char *)malloc(strlen(s)+1);
    if (p != NULL){
        strcpy(p, s);
    }
    return p;
}

struct tnode *addTree(struct tnode *p, char *w)
{
    int cond;
    
    if (p == NULL){
        p = talloc();
        p->word  = strdup(w);
        p->count = 1;
        p->left = p->right = NULL;
    }else if ((cond = strcmp(w, p->word)) == 0){
        p->count++;
    }else if (cond < 0){
        p->left = addTree(p->left, w);
    }else
        p->right = addTree(p->right, w);
    
    return p;
}

//中序遍历
void treeprint(struct tnode *p)
{
    /*
    if (p != NULL){
        treeprint(p>left);
        printf("%4d %s", p->count, p->word);
        treeprint(p>right);
    }
    */
    //写成这样比较好容易理解递归
    if (p == NULL) return;
    treeprint(p->left);
    printf("%4d %s", p->count, p->word);
    treeprint(p->right);
}

//find min
struct tnode *find_min(struct tnode *p)
{
    struct tnode *temp;
    if (p == NULL) return NULL;
    temp = p;
    while(temp->left != NULL)
        temp = temp->left;
    return temp;
}
//find max
struct tnode *find_max(struct tnode *r)
{
    struct tnode *temp;
    if (p == NULL) return NULL;
    temp = p;
    while(temp->right != NULL)
        temp = temp->right;
    return temp;
}
//find key,find the node stores element key
struct tnode *find_value(struct tnode *r, int key)
{
    int cmp;
    if(r == NULL) return NULL;
    if ((cmp = strcmp(key, r->val)) == 0) return r;
    else if(cmp < 0)
        return find_value(r->left, key);
    else 
        return find_value(r->right, key);
}

二叉树的遍历

非递归实现1
Morris遍历
http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html

递归

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
//递归的方法
void preOrder(struct tonde *r)
{
    if (r == NULL) return;
    
    printf("%4d %s", r->count, r->word);
    preOrder(r->left);
    preOrder(r->right);
}
void inOrder(struct tnode *r)
{
    if (r == NULL) return;
    
    inOrder(r->left);
    printf("%4d %s", r->count, r->word);
    inOrder(r->right);
}
void postOrder(struct tnode *r)
{
    if (r == NULL) return;
    
    postOrder(r->left);
    postRigth(r->right);
    printf("%4d %s", r->count, r->word);
}

中序遍历的非递归方法

中序遍历，非递归的方法
对于任一结点P，
1)若其不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
2)若其为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
3)直到P为NULL并且栈为空则遍历结束。

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
//非递归的方法,中序遍历
#include <cstdio>
#include <stack>
#include <stdlib.h>

using namespace std;

struct tnode{
    int val;
    int copys;
    tnode *left;
    tnode *right;
    tnode(int x):val(x),copys(1),left(NULL),right(NULL){}
};

tnode *talloc()
{
    tnode *p;

    p = (struct tnode*)malloc(sizeof(struct tnode));

    if(p == NULL){
        fprintf(stderr, "can't malloc memory\n");
        exit(1);
    }
    return p;
}

tnode *addTree(tnode *r, int v)
{

    if (r == NULL){
        r = talloc();
        r->val = v;
        r->left = r->right= NULL;
    }else if (v == r->val){
        r->copys++;
    }else if (v < r->val){
        r->left = addTree(r->left, v);
    }else{
        r->right = addTree(r->right, v);
    }

    return r;
}

void delete_tree(tnode *r)
{
    if (r == NULL) return;

    delete_tree(r->left);
    delete_tree(r->right);

    free(r);
}

void inOrder(tnode *r)
{
    if (r == NULL) return;

    stack<tnode *> st;
    tnode *p = r;
    st.push(p);

    while(p!=NULL || !st.empty()){
        while(p!=NULL){
            st.push(p);
            p=p->left;
        }
        if(!st.empty())
        {
            p=st.top();
            printf("%d ", p->val);
            st.pop();
            p=p->right;
        }
    }
    
}
int main()
{
    tnode *root = NULL;
    root = addTree(root, 6);
    root = addTree(root, 4);
    root = addTree(root, 5);
    root = addTree(root, 3);
    root = addTree(root, 2);
    root = addTree(root, 1);
    root = addTree(root, 8);
    root = addTree(root, 9);
    root = addTree(root, 7);
    root = addTree(root, 14);
    inOrder(root);
    delete_tree(root);
    return 0;

}

前序遍历的非递归方法

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
//非递归前序遍历
void preOrder(tnode *r)
{
    if (r == NULL) return;

    stack<tnode *> st;
    tnode *p = r;

    while(p || !st.empty()){
        while(p){
            printf("%d ", p->val);
            st.push(p);
            p = p->left;
        }
        if( !st.empty()){
            p = st.top();
            st.pop();
            p = p->right;
        }
    }
}

//第二种实现（其实很类似宽度优先遍历了，只不过把队列替换成了栈）
void preorder2(tnode *r)//非递归前序遍历
{
	if (r == NULL) return;

	stack<tnode *> st;
	st.push(r);
	while (!st.empty())
	{
		tnode *p = st.top(); st.pop();
		printf("%d ", p->val);
		if (p->right) st.push(p->right);
		if (p->left) st.push(p->left);
	}
}

后续遍历的非递归方法

因为后序遍历的顺序是：左子树->右子树->根节点，于是我们在前序遍历的代码中，当访问完当前节点后，先把当前节点的左子树入栈，再把右子树入栈，这样最终得到的顺序为：根节点->右子树->左子树，刚好是后序遍历倒过来的版本，于是把这个结果做一次翻转即为真正的后序遍历。而翻转可以通过使用另外一个栈简单完成，这样的代价是需要两个栈，但就复杂度而言，空间复杂度仍然是O(h)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> postorderTraversal(tnode *r) {  
    vector<int> result;  
    if(r == NULL){  
        return result;  
    }  
    stack<tnode*> s;  
    s.push(r);  
    tnode *node;  
    while(!s.empty()){  
        node = s.top();     s.pop();  
        result.insert(result.begin(),node->val);  
        // 左子树  
        if(node->left){  
            s.push(node->left);  
        }
        // 右子树  
        if(node->right){  
            s.push(node->right);  
        }  
    }  
    return result;  
}

二叉树的相关问题

LCA，最低公共祖先

给定一棵树，同时给出树中的两个结点(n1和n2)，求它们的最低公共祖先。也就是常见的LCA(Lowest Common Ancestor )问题。

解法一:
(1)找到从根节点到$n_1$的路径，
(2)找到从根节点到$n_2$的路径；
(3)找出两条路径中第一个不相同的点，则它的父节点即是所求。

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
#include <iostream>
#include <vector>
using namespace std;

struct tnode{
    int val;
    struct tnode *left, *right;
};

tnode* newNode(int k)
{
    tnode* p = new tnode;
    p->val = k;
    p->left = p->right=NULL;
    return p;
}

bool findPath(tnode *r, int key, vector<int>& path)
{
    if (r == NULL) return false;

    path.push_back(r->val);
    if (r->val == key) return true;

    bool exsite = (findPath(r->left, key, path) || findPath(r->right, key, path));

    if (exsite) return true;
    path.pop_back();
    return false;
}

int findLCA(tnode *r, int key1, int key2)
{
    vector<int> path1, path2;
    int ret = -1;
    bool find1 = findPath(r, key1, path1);
    bool find2 = findPath(r, key2, path2);

    vector<int>::iterator iter1 = path1.begin();
    vector<int>::iterator iter2 = path2.begin();

    if (find1 && find2){
        while( iter1 != path1.end() && iter2 != path2.end()){
            if (*iter1 == *iter2){
                ret = *iter1;
                ++iter1;
                ++iter2;
            }else
                break;
        }
        return ret;
    }
    return -1;
}

int main()
{
    tnode * root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    cout << "LCA(4, 5) = " << findLCA(root, 4, 5);
    cout << "\nLCA(4, 6) = " << findLCA(root, 4, 6);
    cout << "\nLCA(3, 4) = " << findLCA(root, 3, 4);
    cout << "\nLCA(4, 2) = " << findLCA(root, 2, 4);
    cout << "\nLCA(6, 3) = " << findLCA(root, 3, 6);
    return 0;
}

解法2:递归的方法
(1)从一个根节点r开始找,如果r中的val是其中的一个，那么r就是所求的节点
(2)否则的话，遍历r->left和r->right，如果在r->left中找到两个节点，就返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
tnode *findLCA(tnode *r, int num1, int num2)
{
    if (r == NULL) return NULL;
    
    if (r->val == num1 || r->val == num2)
        return r;
        
    tnode *leftLCA = findLCA(r->left, num1, num2);
    tnode *rightLCA = findLCA(r->right, num1, num2);
    
    if (leftLCA && rightLCA)
        return r;
    else
        return (leftLCA==NULL)?rightLCA:leftLCA;
}

二叉树中两个节点的距离

公式计算

Dist(n1, n2) = Dist(root, n1) + Dist(root, n2) - 2*Dist(root, LCA)

二叉树的面试题
http://www.acmerblog.com/?s=%E4%BA%8C%E5%8F%89%E6%A0%91