数据结构与算法笔记 | 树

数据结构与算法 10 minutes read (About 1522 words)

树结构在数据结构中有着举足轻重的地位。

1. 二叉搜索树

二叉搜索树被誉为数据结构中的 “Hello World”，又被称为二叉排序树或二叉查找树。

二叉搜索树指的是树中结点的键按一定顺序排列的数据结构。它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
它的左、右子树也分别为二叉排序树。
它没有键值相等的节点。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低,均为O(log n)。
二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、multiset、关联数组等。

1.1 二叉搜索树的遍历

由于，左子树的所有节点值<根节点的值<右子树的所有节点值，所以二叉搜索树的遍历采用DFS较多
前序遍历：根节点->左子节点->右子节点
中序遍历：左子节点->根节点->右子节点
后序遍历：左子节点->右子节点->根节点

这里重点讲一下后序遍历，由于树都是从根到子树的顺序开始访问的，但是后续遍历需要将根节点放在最后访问。

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
import java.util.*;

public class Node {
    int val;
    Node left;
    Node right;
}

public class Main {
    
    // 左、右、根
    public void postTraverse(Node root) {
        if(root == null) {
            return ;
        }
        Stack<Node> path = new Stack<Node>();
        path.push(root);
        while(!path.isEmpty()) {
            Node node = path.pop();
            while(node.left != null) {
                path.push(node.left);
                node = node.left;
            }
            if(node == null && !path.isEmpty()) {
                node = path.pop();
            }
            if(node.right != null) {
                path.push(node.right);
                continue ;
            }
            print(node);
        }
        return ;
    }
    
    public static void main(String[] args) {
        //Scanner in = new Scanner(System.in);
        //int a = in.nextInt();
        //System.out.println(a);
        System.out.println("Hello World!");
    }
}

既然这里都已经用到栈结构了，如果改成不用非递归方式的访问呢？

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
import java.util.*;

public class Node {
    public int value;
    public Node left;
    public Node right;
}

public class Main {
    
    // 左、右、根
    public List<Integer> postTraverse(TreeNode root) {
		List<Integer> result = new LinkedList<>();
		if(root == null) {
			return result;
		}
		Stack<TreeNode> stack = new Stack<>();
		TreeNode currentNode = root;
		stack.push(currentNode);
		TreeNode previousNode = null;
		while(!stack.isEmpty()) {
			previousNode = currentNode;
			currentNode = stack.pop();
			/* 三种情况： 1. 左右子树均未访问；2.左子树访问完，右子树没访问；3. 左右子树均已访问
			对第1种情况，currentNode在下，previousNode在上
			对第2种情况，previousNode在下，为currentNode的左子树
			对第3种情况，previousNode在下，为currentNode的右子树
			 */
			if(currentNode.left != previousNode && currentNode.right != previousNode) {
				// 第1种情况，开始不断访问左子树，直至叶子节点
				while(currentNode.left != null) {
					stack.push(currentNode);
					previousNode = currentNode;
					currentNode = currentNode.left;
				}
				// 此时currentNode即左节点
			} else if (currentNode.right == previousNode){ // 第3种情况
				result.add(currentNode.val);
				continue;
			}
			/* 两种情况： 1.currentNode为左节点，存在还没访问的右子树； 2.左子树访问完，无右子树,currentNode均不在栈中
			对第1种情况，previousNode在上，currentNode在下，previousNode.left = currentNode
			对第2种情况，currentNode.left = previousNode
			 */
			if(currentNode.right != null && currentNode.right != previousNode) { // 右子树存在且还没访问
				stack.push(currentNode);
				// 右子树的根节点压栈
				stack.push(currentNode.right);
			} else { // 左右子树均已访问
				result.add(currentNode.val);
			}
		}
		return result;
	}
    
    public static void main(String[] args) {
		Integer[] input = {5, 4, 7, 0, 3, 6, null, null, null, 1, 2};
		TreeNode[] nodes = new TreeNode[input.length];
		for(int i = input.length-1; i >= 0; --i) {
			if(input[i] != null) {
				nodes[i] = new TreeNode(input[i]);
				if(2*i+1 < input.length) {
					nodes[i].left = nodes[2*i+1];
				}
				if(2*i+2 < input.length) {
					nodes[i].right = nodes[2*i+2];
				}
			}
		}
		TreeNodeTests test = new TreeNodeTests();
		List<Integer> result = test.postTraverse(nodes[0]);
		System.out.println(result.stream().map(Objects::toString).collect(Collectors.joining(",")));
	}
}

例题：Leetcode 98: Validate Binary Search Tree

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    Integer prev_val;

    public boolean isValidBST(TreeNode root) {
        if(root == null) {
            return true;
        }
        if (isValidBST(root.left) == false){
            return false;
        }
        if (prev_val != null && prev_val >= root.val) {
            return false;
        }
        prev_val = root.val;
        return isValidBST(root.right);
    }
}

例题：牛客网: 二叉搜索树的后序遍历序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0) return false; 
        if(sequence.length<=2) return true;
        boolean res = verify(sequence, 0, sequence.length-1);
        return res;
    }
    
    boolean verify(int[] s, int st, int end) {
        if(st >= end) return true;
        int i=st;
        while(s[i] < s[end])
            ++i;
        int pivot = i;
        for(; i<end; ++i) {
            if(s[i] < s[end])
                return false;
        }
        return verify(s, st, pivot-1) & verify(s, pivot+1, end);
    }
}

2. 平衡二叉树

B+树

MySQL中使用B+树建立索引。
B+树比红黑树层数更少，查找速度更快，所以适合用来作为数据库索引的数据结构。

AVL树（一种自平衡二叉树）

PAT 1066: Root of AVL Tree（25 分）

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.

示意图

Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the root of the resulting AVL tree in one line.

Sample Input 1:

1
2
5
88 70 61 96 120

Sample Output 1:

1
70

Sample Input 2:

1
2
7
88 70 61 96 120 90 65

Sample Output 2:

1
88

题目分析

这道题要求根据输入数据构造一个 AVL 树. 最后输出树的根所保存的元素. 没有什么技巧, 要求会 AVL 的建立过程才行. 难点在于插入数据后不满足平衡条件时树的旋转.

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<bits/stdc++.h>
using namespace std;

#define For(i,n) for(int i=0;i<n;i++)
struct Node{
    int value;
    Node *left, *right;
    Node(int v) : value(v) {
        left = right = NULL;
    }
};

int getHeight(Node *root){
    if (root == NULL) return 0;
    return max(getHeight(root->left), getHeight(root->right))+1;
}

Node *rotateLeft(Node *root){
    Node *t = root->right;
    root->right = t->left;
    t->left = root;
    return t;
}

Node *rotateRight(Node *root){
    Node *t = root->left;
    root->left = t->right;
    t->right = root;
    return t;
}

Node *rotateLeftRight(Node *root){
    root->left = rotateLeft(root->left);
    return rotateRight(root);
}

Node *rotateRightLeft(Node *root){
    root->right = rotateRight(root->right);
    return rotateLeft(root);
}

Node *insert(Node* root, int val){
    if (root == NULL){
        root = new Node(val);
    } else if (val < root->value){
        root->left = insert(root->left, val);
        if (getHeight(root->left)-getHeight(root->right) == 2){
            root = val < root->left->value ? rotateRight(root) : rotateLeftRight(root);
        }
    } else {
        root->right = insert(root->right, val);
        if (getHeight(root->right)-getHeight(root->left) == 2){
            root = val < root->right->value ? rotateRightLeft(root) : rotateLeft(root);
        }
    }
    return root;
}

int main()
{
    int N;
    scanf("%d", &N);
    Node *root = NULL;
    For(i,N){
        int val;
        scanf("%d", &val);
        root = insert(root, val);
    }
    printf("%d\n", root->value);
    return 0;
}

3. 无根树与有根树

来看一道无根树的题目.
Centroid (SGU 134), 链接:https://cn.vjudge.net/problem/SGU-134

这道题给了一个树的重心的定义. 将这棵树上删除掉重心的时候, 剩余子树的节点数最大值是最小的, 换个表述也就是说剩下的子树之间是平衡的.

我们使用 dfs 来找出各个子树的节点数和节点数最大的子树. 任意找一个节点作为根节点, 遍历一遍就可以. 接下来求解剩余子树的节点数最大值就可以转化为求在这种树的构造下, 以某个节点为父节点的所有子树中节点数的最大值和除去该节点和这些子树外剩余的所有节点的个数相比较的最大值, 即 value = max(val[i], n-size[i]).

#算法 #数据结构 #树 #DFS #PAT #MySQL
面向对象程序设计笔记整理-1 数据结构与算法笔记 | 字符串

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×