数据结构（五）-树和二叉树

发表于 | 分类于 ，

1. 概述

  • 树是n个结点的有限集
  • 有且仅有一个特定的根，称为根结点
  • 当$n > 1$时，其余结点可分为m个互不相交的有限集，其中每一个集合本身又是一棵树，称为子树
  • 结点拥有的子树称之为度，度为0的节点称为叶子结点
  • 结点的层次是从根开始定义起的，根为第一层，根的孩子为第二层
  • 树中结点最大的层次称为深度
  • 森林是m棵互不相交的数的集合

2. 二叉树

  • 每个结点至多只有两棵子树，有左右之分，其次序不能随意颠倒
  • 性质
    • 在二叉树的第i层上至多有$2^{i-1}$个结点（$i\geq 1$）
    • 深度为k的二叉树至多有$2^k - 1$个结点（$k \geq 1$）
    • 对任何一颗二叉树T，如果其终端结点数为n，度为2的结点数为$n_2$，那么$n = n_2 + 1$
    • 具有n个结点的完全二叉树的深度为$[\log_2 n] + 1$
    • 如果对一棵有n个结点的完全二叉树

3. 二叉树代码实现

  • BinaryTree.hpp
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
//
//  BinaryTree.hpp
//  Tree
//

#ifndef BinaryTree_hpp
#define BinaryTree_hpp

#include <iostream>

using namespace std;

typedef int dataType;

static int n = 0;
static int m = 0;

struct Tree {
    dataType data;
    Tree *left, *right;
};

class BinaryTree {
    
public:
    BinaryTree() {
        root = NULL;
    };
    ~BinaryTree() {};
    
    Tree *root;
    
    void Create(dataType data);
    void PreOrder(Tree *, string name);
    void InOrder(Tree *);
    void PostOrder(Tree *);
    int GetCount(Tree *);
    int FindLeaf(Tree *);
    int FindNode(Tree *);
    
    void PrintPreOrder() {
        PreOrder(root, "Root");
        cout << endl;
    }
    
    void PrintInOrder() {
        InOrder(root);
        cout << endl;
    }
    
    void PrintPostOrder() {
        PostOrder(root);
        cout << endl;
    }
    
};

#endif /* BinaryTree_hpp */
  • BinaryTree.cpp
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
//
//  BinaryTree.cpp
//  Tree
//

#include "BinaryTree.hpp"

void BinaryTree::Create(dataType data) {
    Tree *newNode = new Tree;
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    if (NULL == root) {
        root = newNode;
        return;
    }
    Tree *back = NULL, *current = root;
    while (NULL != current) {
        back = current;
        if (current->data > data) {
            current = current->left;
        } else {
            current = current->right;
        }
    }
    if (NULL == back) {
        return;
    }
    if (back->data > data) {
        back->left = newNode;
    } else {
        back->right = newNode;
    }
    
}

void BinaryTree::PreOrder(Tree *p, string name) {
    if (NULL == p) {
        return;
    }
    std::cout << name << ": " << p->data << " ";
    PreOrder(p->left, "left");
    PreOrder(p->right, "right");
}

void BinaryTree::InOrder(Tree *p) {
    if (NULL == p) {
        return;
    }
    InOrder(p->left);
    cout << p->data << " ";
    InOrder(p->right);
}

void BinaryTree::PostOrder(Tree *p) {
    if (NULL == p) {
        return;
    }
    PostOrder(p->left);
    PostOrder(p->right);
    cout << p->data << " ";
}

int BinaryTree::GetCount(Tree *p) {
    if (NULL == p) {
        return 0;
    }
    return GetCount(p->left) + GetCount(p->right) + 1;
}

int BinaryTree::FindLeaf(Tree *p) {
    if (NULL == p) {
        return 0;
    }
    if (NULL == p->left && NULL == p->right) {
        return n+=1;
    }
    FindLeaf(p->left);
    FindLeaf(p->right);
    return n;
}

int BinaryTree::FindNode(Tree *p) {
    if (NULL == p) {
        return 0;
    }
    if (NULL != p->left && NULL != p->right) {
        FindNode(p->left);
        FindNode(p->right);
    }
    if (NULL == p->left && NULL != p->right) {
        FindNode(p->right);
        m ++;
    }
    if (NULL != p->left && NULL == p->right) {
        FindNode(p->left);
        m ++;
    }
    
    return m;
}

4. 平衡二叉树

  • 左右子树的高度相差不超过 1 的树为平衡二叉树
  • AVL树的查找、插入、删除操作在平均和最坏的情况下都是O（logn）
  • 最小失衡子树
    • 在新插入的结点向上查找，以第一个平衡因子的绝对值超过 1 的结点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树
  • 平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的
    • 旋转的目的就是减少高度，通过降低整棵树的高度来平衡。哪边的树高，就把那边的树向上旋转
    • 左旋
      • 节点的右孩子替代此节点位置
      • 右孩子的左子树变为该节点的右子树
      • 节点本身变为右孩子的左子树
    • 右旋
      • 节点的左孩子代表此节点
      • 节点的左孩子的右子树变为节点的左子树
      • 将此节点作为左孩子节点的右子树

4.1 插入操作

  • 假设一颗 AVL 树的某个节点为 A，有四种操作会使 A 的左右子树高度差大于 1，从而破坏了原有 AVL 树的平衡性。平衡二叉树插入节点的情况分为以下四种
    • 在A的左子树根节点的左子树上插入节点而破坏平衡，需要右旋
    • 在A的右子树根节点的右子树上插入节点而破坏平衡，需要左旋
    • 在A的左子树根节点的右子树上插入节点而破坏平衡，需要先左旋后右旋
    • 在A的右子树根节点的左子树上插入节点而破坏平衡，需要先右旋后左旋

4.2 删除操作

4.3 代码实现

  • AVLTree.hpp
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
//
//  AVLTree.hpp
//  Tree
//

#ifndef AVLTree_hpp
#define AVLTree_hpp

#include <stdio.h>
#include <iostream>

using namespace std;

typedef int dataType;

class AVLTree {
    
    struct Tree {
        dataType data;
        Tree *left, *right;
        Tree(dataType x) {
            data = x;
            left = NULL;
            right = NULL;
        }
    };
    
public:
    AVLTree();
    ~AVLTree();
    
    void Create(dataType data);
    void Insert(const dataType data);
    void Remove(dataType data);
    Tree* Search(dataType data);
    
    void PreOrder(Tree *p);
    void InOrder(Tree *p);
    void PostOrder(Tree *p);
    int Height(Tree *p);
    void Print();
    
    Tree * GetRoot() {
        return root;
    }
    
private:
    Tree *root;
    
    Tree* Insert(Tree* subRoot, dataType data) {
        if (NULL == subRoot) {
            subRoot = new Tree(data);
        } else if (data > subRoot->data) {
            subRoot->right = Insert(subRoot->right, data);
            subRoot = Balance(subRoot);
        } else if (data < subRoot->data) {
            subRoot->left = Insert(subRoot->left, data);
            subRoot = Balance(subRoot);
        }
        return subRoot;
    }
    
    Tree* TreeMax(Tree *p) {
        if (!p) {
            return NULL;
        }
        while (p->right) {
            p = p->right;
        }
        return p;
    }
    
    Tree* TreeMin(Tree *p) {
        if (!p) {
            return NULL;
        }
        while (p->left) {
            p = p->left;
        }
        return p;
    }
    
    int BalanceFactor(Tree *p) {
        return Height(p->left) - Height(p->right);
    }
    
    Tree * Balance(Tree * subRoot) {
        int bf = BalanceFactor(subRoot);
        if (bf > 1) {
            if (BalanceFactor(subRoot->left) > 0) {
                subRoot = LLRotation(subRoot);
            } else {
                subRoot = LRRotation(subRoot);
            }
        } else if (bf < -1) {
            if (BalanceFactor(subRoot->right) > 0) {
                subRoot = RLRotation(subRoot);
            } else {
                subRoot = RRRotation(subRoot);
            }
        }
        return subRoot;
    }
    
    Tree* LLRotation(Tree *subRoot) {
        Tree *p = subRoot->left;
        subRoot->left = p->right;
        p->right = subRoot;
        return p;
    }
    
    Tree* RRRotation(Tree *subRoot) {
        Tree *p = subRoot->right;
        subRoot->right = p->left;
        p->left = subRoot;
        return p;
    }
    
    Tree* RLRotation(Tree *subRoot) {
        subRoot->right = LLRotation(subRoot->right);
        return RRRotation(subRoot);
    }
    
    Tree* LRRotation(Tree *subRoot) {
        subRoot->left = RRRotation(subRoot->left);
        return LLRotation(subRoot);
    }
    
    Tree* Remove(Tree *subRoot, dataType data) {
        if (!Search(data)) {
            cout << "不存在结点: " << data << endl;
            return root;
        }
        if (!root) {
            return root;
        }
        return subRoot;
    }
    
    void Destroy(Tree *p);
    
};

#endif /* AVLTree_hpp */
  • AVLTree.cpp
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
//
//  AVLTree.cpp
//  Tree
//

#include "AVLTree.hpp"

AVLTree::AVLTree() {
    root = NULL;
}

AVLTree::~AVLTree() {
    if (root) {
        Destroy(root);
    }
}

void AVLTree::Destroy(Tree *p) {
    if (p) {
        Destroy(p->left);
        Destroy(p->right);
        delete p;
    }
}

void AVLTree::Create(dataType data) {
    Insert(data);
}

void AVLTree::Insert(const dataType data) {
    root = Insert(root, data);
}

AVLTree::Tree* AVLTree::Search(dataType data) {
    Tree *p = root;
    while (p) {
        if (p->data == data) {
            break;
        } else if (p->data < data) {
            p = p->right;
        } else {
            p = p->left;
        }
    }
    return p;
}

void AVLTree::Remove(dataType data) {
    root = Remove(root, data);
}

int AVLTree::Height(Tree *p) {
    if (NULL == p) {
        return 0;
    }
    int i = Height(p->left);
    int j = Height(p->right);
    return i > j ? i + 1 : j + 1;
}

void AVLTree::PreOrder(Tree *p) {
    if (NULL != p) {
        cout << p->data << " ";
        PreOrder(p->left);
        PreOrder(p->right);
    }
}

void AVLTree::InOrder(Tree *p) {
    if (NULL != p) {
        InOrder(p->left);
        cout << p->data << " ";
        InOrder(p->right);
    }
}

void AVLTree::PostOrder(Tree *p) {
    if (NULL != p) {
        PostOrder(p->left);
        PostOrder(p->right);
        cout << p->data << " ";
    }
}

void AVLTree::Print() {
    cout << "先序遍历为: ";
    PreOrder(root);
    cout << endl;
    
    cout << "中序遍历为: ";
    InOrder(root);
    cout << endl;
    
    cout << "后序遍历为: ";
    PostOrder(root);
    cout << endl;
}

5. 面试题

5.1 二叉树反转

  • 递归算法
    • 交换根节点的左右子树
    • 对左右子树分别执行递归反转
  • 非递归算法
    • 交换根节点的左右子节点
    • 交换第二层每个节点的左右子节点
1
2
3
4
5
6
7
8
TreeNode* invertTree(TreeNode* root) {
    if(root==NULL)
      	return NULL;
    TreeNode * ptmpNode = root->left;
    root->left = invertTree(root->right);
    root->right = invertTree(ptmpNode);
    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
TreeNode* invertTree2(TreeNode* root) {
    queue<TreeNode*> tree_queue;
    if (root == NULL)
      	return root;
    tree_queue.push(root);
    while(tree_queue.size() > 0) {
        TreeNode * pNode = tree_queue.front();
        tree_queue.pop();
        TreeNode * pLeft = pNode->left;
        pNode->left = pNode->right;
        pNode->right = pLeft;
        if (pNode->left)
          	tree_queue.push(pNode->left);
        if (pNode->right)
          	tree_queue.push(pNode->right);
    }
    return root;
}

5.2 深度优先遍历

  • 从根节点出发，沿着左子树方向进行纵向遍历，直到找到叶子节点为止。然后回溯到前一个节点，进行右子树节点的遍历，直到遍历完所有可达节点为止
  • 父节点入栈，父节点出栈，先右子节点入栈，后左子节点入栈。递归遍历全部节点即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void depthFirstSearch(Tree root){
    stack<Node *> nodeStack;
    nodeStack.push(root);
    Node *node;
    while(!nodeStack.empty()){
	    node = nodeStack.top();
		cout<<node->data;
        nodeStack.pop();
        if(node->rchild){
            nodeStack.push(node->rchild);
        }
        if(node->lchild){
            nodeStack.push(node->lchild);
        }
    }
}

5.3 广度优先遍历

  • 从根节点出发，在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次
  • 父节点入队，父节点出队列，先左子节点入队，后右子节点入队。递归遍历全部节点即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void breadthFirstSearch(Tree root){
    queue<Node *> nodeQueue;  //使用C++的STL标准模板库
    nodeQueue.push(root);
    Node *node;
    while(!nodeQueue.empty()){
        node = nodeQueue.front();
        nodeQueue.pop();
        cout<<node->data;//遍历根结点
        if(node->lchild){
            nodeQueue.push(node->lchild);  //先将左子树入队
        }
        if(node->rchild){
            nodeQueue.push(node->rchild);  //再将右子树入队
        }
    }
}