[Swift实际操作]八、实用进阶，10使用Swift创建一个二叉树BinaryTreeNode
1、二叉树的特点：
(1)、每个节点最多有两个子树
(2)、左子树和右子树是有顺序的，次序不能颠倒
(3)、即使某节点只有一个子树，也要区分左右子树
2、二叉查找树（Binary Search Tree）:（又：二叉搜索树，二叉排序树）
(1)、它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
(2)、二叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索,插入,删除的复杂度等于树高，O(log(n)).
1 class TreeNode
2 {
3 //节点数据
4 public var val:Int
5 //左节点
6 public var left: TreeNode?
7 //右节点
8 public var right: TreeNode?
9 //初始化方法
10 public init(_ val: Int) {
11 self.val = val
12 self.left = nil
13 self.right = nil
14 }
15
16 //获取指定节点的最大深度
17 func getMaxDepth(_ node:TreeNode?) -> Int
18 {
19 //假如指定的节点为空，则返回值为0
20 //节点为空时
21 if node == nil{return 0}
22 //使用递归方式获得左右节点的最大深度，返回两者较大值
23 return max(getMaxDepth(node!.left),getMaxDepth(node!.right)) + 1
24 }
25
26 //判断二叉搜索树
27 func isValidBST(_ root:TreeNode?) -> Bool
28 {
29 //节点为空时
30 if root == nil{return true}
31 //二叉搜索树的的特点是所有的右子节点，都必须大于根节点
32 //并且所有的左子节点，都必须小于根节点
33 return (IsSubtreeLessThan(root!.left, root!.val) && IsSubtreeMoreThan(root!.right, root!.val) && isValidBST(root!.left) && isValidBST(root!.right))
34 }
35
36 func IsSubtreeLessThan(_ node: TreeNode?,_ val:Int) -> Bool
37 {
38 //节点为空时
39 if node == nil{return true}
40 return (node!.val < val && IsSubtreeLessThan(node!.left, val) && IsSubtreeLessThan(node!.right, val))
41 }
42
43 func IsSubtreeMoreThan(_ node: TreeNode?,_ val:Int) -> Bool
44 {
45 //节点为空时
46 if node == nil{return true}
47 return (node!.val > val && IsSubtreeLessThan(node!.left, val) && IsSubtreeLessThan(node!.right, val))
48 }
49 }
50
51 //初始化三个节点
52 var tree = TreeNode(10)
53 var left = TreeNode(3)
54 var right = TreeNode(5)
55 //将后两个节点分别作为第一个节点的左节点和右节点
56 tree.left = left
57 tree.right = right
58 dump(tree)
59 //Print
60 /*
61 ▿ prog.TreeNode #0
62 - val: 10
63 ▿ left: Optional(prog.TreeNode)
64 ▿ some: prog.TreeNode #1
65 - val: 3
66 - left: nil
67 - right: nil
68 ▿ right: Optional(prog.TreeNode)
69 ▿ some: prog.TreeNode #2
70 - val: 5
71 - left: nil
72 - right: nil
73 */
74 //获取指定节点的最大深度
75 let depth = tree.getMaxDepth(tree)
76 print(depth)
77 //Print 2
78 //判断节点是否为二叉搜索树Binary Search Tree（BST）
79 let bst = tree.isValidBST(tree)
80 print(bst)
81 //Print false