[算法]模式识别-Tree

Author Avatar
与狼同行 11月 25, 2016

Tree

树是一种能够分层存储数据的重要数据结构,树中的每一个元素称为树的节点,每个节点由若干个指针指向子节点,从节点的角度来看,树是由唯一节点引出来的集合。
树在面试中非常常见、尤其是二叉树、二叉搜索树等等。

基本概念:

  1. 高度:对于一棵树从,从根节点到某个节点的路径称为该节点的层数,根节点为第0层。

树形的概念

  1. 满二叉树:如果一颗二叉树的任何节点,或者是叶子节点,或者左右子树都存在,则这颗二叉树称作满二叉树。
  2. 完全二叉树:如果一颗二叉树最多只有最下面的两层节点度数可以小于2,并且最下面一层的节点都集中在该层最左边的连续位置上,则称为完全二叉树。

树的遍历

  1. 前序遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class TreeNode {
    var val: Int
    var leftNode: TreeNode?
    var rightNode: TreeNode?
    init(val: Int) {
    self.val = val
    }
    }
    //MARK:---- 遍历二叉树 -----
    func preOrderTraversal(root:TreeNode?){
    guard root != nil else{
    return
    }
    print(root!.val)
    preOrderTraversal(root: root?.leftNode)
    preOrderTraversal(root: root?.rightNode)
    }
  2. 中序遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    func inOrderTraversal(root:TreeNode?){
    guard root != nil else{
    return
    }
    preOrderTraversal(root: root?.leftNode)
    print(root!.val)
    preOrderTraversal(root: root?.rightNode)
    }
  3. 后序遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    func postOrderTraversal(root:TreeNode?){
    guard root != nil else{
    return
    }
    preOrderTraversal(root: root?.leftNode)
    preOrderTraversal(root: root?.rightNode)
    print(root!.val)
    }

字典树

字典树是一个26叉树,用于在一个集合中检索一个字符串,字典树的每一个节点有一个指针数组,其本质上是一个哈希表,因为子树所在的位置本身index,就代表了节点对应的字母。

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
const int Max = 26;
typedef struct Node{
bool isStr;
Node *next[Max];
}TrieNode;
class Trie {
private:
TrieNode *root;
public:
Trie(){
root = new TrieNode;
for (int i=0; i<Max; i++) {
root->next[i]=NULL;
root->isStr=false;
}
}
~Trie(){
delete(root);
root = nullptr;
}
void insert(const char *str){
if (str==NULL||*str=='\0') {
return;
}
TrieNode *p = root;
while (*str!='\0') {
if (p->next[*str-'a']==NULL) {
TrieNode *tmp = new TrieNode;
for (int i=0; i<Max; i++) {
tmp->next[i]=NULL;
}
tmp->isStr=false;
p->next[*str-'a']=tmp;
p=tmp;
}else{
p=p->next[*str-'a'];
}
str++;
}
p->isStr=true;
}
//查找某一个字符是否在字典树中存在
bool search(const char *str)
{
if(str==NULL||*str=='\0')
return false;
TrieNode *p=root;
while(p!=NULL && *str!='\0')
{
p=p->next[*str-'a'];
str++;
}
if(p!=NULL && p->isStr==true)
return true;
else
return false;
}
protected:
void del(TrieNode *root)
{
for(int i=0;i<Max;i++)
{
if(root->next[i]!=NULL)
{
del(root->next[i]);
}
}
delete root;
}
};

二叉搜索树

二叉搜索树是二叉树的一种特殊结构,对于二叉树搜索树的任何节点存储的值

  1. 节点值比左子树所有的节点的值都大
  2. 节点值比右子树所有的节点的值都小
    基于这个特性,二叉搜索树被经常用于维护有序的数据,事实上,对于二叉搜索树的操作相当于二分搜索,其效率与树的高度有关,检索数据的次数不会高于树的高度。
    二叉搜索树的高度应该越短越好,因为第L层最多存储2^n个节点,因此树的高度在log n的量级,因此二分搜索树的效率为O(log n)。
    当二分搜索树退化为链表时,搜索效率变为了O(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
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
145
146
147
148
149
150
151
152
153
154
155
class BTreeNode
{
public:
BTreeNode(int val):left(NULL),right(NULL),parent(NULL),val(val){}//初始化
int val;//值
BTreeNode* parent;
BTreeNode* left;//指向左儿子的坐标
BTreeNode* right;//指向右儿子的坐标
bool operator == (BTreeNode& bt){
return bt.val == val ? true : false;
}
};
//二叉查找树类的属性和方法声明
class BSortTree
{
public:
BSortTree():root(NULL),size(0){}
~BSortTree(){}
int length(){return size;}
void Insert(int val);
void Delete(int val);
BTreeNode* Search(int val);
private:
BTreeNode *root;
int size;
void insertTree(BTreeNode& node,int val);
void DeleteTree(BTreeNode* node,int val);
BTreeNode* SearchTreeMin(BTreeNode* node);
BTreeNode* SearchTreeMax(BTreeNode* node);
BTreeNode* SearchTree(BTreeNode* node,int val);
};
void BSortTree::Insert(int val){
if (root==NULL) {
BTreeNode *pNode = new BTreeNode(val);
root = pNode;
size++;
return;
}
}
void BSortTree::Delete(int val){
}
BTreeNode* BSortTree::Search(int val){
return SearchTree(root, val);
}
void BSortTree::DeleteTree(BTreeNode *node, int val){
BTreeNode *dNode = Search(val);
if (dNode == NULL) {
return;
}
if (dNode->left==NULL&&dNode->right==NULL) {
if (dNode->parent==NULL) {
size = 0;
root = NULL;
}else if (dNode->parent->left == dNode){
dNode->parent->left = NULL;
}else{
dNode->parent->right = NULL;
}
delete dNode;
size--;
return;
}
if (dNode->left!=NULL&&node->right==NULL) {
dNode->left->parent = dNode->parent;
if (dNode->parent == NULL) {
root = dNode->left;
}else if(dNode->parent->left==dNode){
dNode->parent->left = dNode->left;
}else{
dNode->parent->right = dNode->right;
}
delete dNode;
size--;
return;
}
if (dNode->left==NULL&&node->right!=NULL) {
dNode->right->parent = dNode->parent;
if (dNode->parent == NULL) {
root = dNode->right;
}else if(dNode->parent->left==dNode){
dNode->parent->left = dNode->left;
}else{
dNode->parent->right = dNode->right;
}
delete dNode;
size--;
return;
}
if (dNode->left!=NULL&&node->right!=NULL) {
BTreeNode *replaceNode = SearchTreeMin(node->right);
dNode->val = replaceNode->val;
DeleteTree(dNode, replaceNode->val);
}
}
BTreeNode* SearchTreeMin(BTreeNode* node){
if (node == NULL) {
return NULL;
}else if(node->left == NULL){
return node;
}else{
return SearchTreeMin(node->left);
}
}
BTreeNode* BSortTree::SearchTree(BTreeNode *node, int val){
if (node == NULL) {
return NULL;
}else if (val == node->val){
return node;
}else if (val < node->val){
return SearchTree(node->left, val);
}else{
return SearchTree(node->right, val);
}
}
void BSortTree::insertTree(BTreeNode& node,int val){
BTreeNode *pNode = new BTreeNode(val);
if (node.left==NULL && val < node.val) {
node.left = pNode;
pNode->parent = &node;
size++;
return;
}
if (pNode->right==NULL&& val >= node.val) {
node.right = pNode;
pNode->parent = &node;
size++;
return;
}
if (val < node.val) {
insertTree(*(node.left), val);
}else{
insertTree(*(node.right), val);
}
}

平衡二叉树

平衡二叉树左右两个子树的高度不会超过1。并且左右都是平衡二叉树,通过适当的构造与调整平衡二叉树能够保证每次插入删除之后都保持平衡性。
平衡二叉树的算法包括AVL算法和红黑树算法。平衡二叉树的实现一般较为复杂,所以面试官只会问一些概念性的问题。

树相关常见题目

  1. 反转二叉树
    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
    //非递归 O(n) 广度优先。从上往下,从左往右。到达一层,从左到右翻完这一层的节点,再翻下一层。通过数组的方式实现节点的保存。O(n)。
    func invertNonRecursive(root: TreeNode) {
    var nodes = [TreeNode]()
    nodes.append(root)
    while !nodes.isEmpty {
    if let node = nodes.first {
    nodes.removeFirst()
    let tempLeftTree = node.leftNode
    node.leftNode = node.rightNode
    node.rightNode = tempLeftTree
    if let leftTree = node.leftNode {
    nodes.append(leftTree)
    }
    if let rightTree = node.leftNode {
    nodes.append(rightTree)
    }
    }
    }
    }
    //递归 O(n) 深度优先。先翻一次,之后对左右子树递归翻转。O(n)。
    func invertWithRecursive(root:TreeNode){
    let tempLeftTree = root.leftNode
    root.leftNode = root.rightNode
    root.rightNode = tempLeftTree
    if let leftTree = root.leftNode {
    invertWithRecursive(root: leftTree)
    }
    if let rightTree = root.rightNode {
    invertWithRecursive(root: rightTree)
    }
    }