[Swift4.2互动教程]八、实用进阶-(11)使用Swift创建一个二叉树BinaryTreeNode

概述1、二叉树的特点： (1)、每个节点最多有两个子树 (2)、左子树和右子树是有顺序的，次序不能颠倒 (3)、即使某节点只有一个子树，也要区分左右子树 2、二叉查找树（Binary Search Tree）:（又：二叉搜索树，二叉排序树） (1)、它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均

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 = val12         self.left = nil13         self.right = nil14     }15     16     //获取指定节点的最大深度17     func getMaxDepth(_ node:TreeNode?) -> Int18     {19        //假如指定的节点为空，则返回值为020         //节点为空时21         if node == nil{return 0}22        //使用递归方式获得左右节点的最大深度，返回两者较大值23        return max(getMaxDepth(node!.left),getMaxDepth(node!.right)) + 124     }25     26     //判断二叉搜索树27     func isValIDBST(_ root:TreeNode?) -> Bool28     {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) -> Bool37     {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) -> Bool44     {45         //节点为空时46         if node == nil{return true}47         return (node!.val > val && IsSubtreeLessthan(node!.left,val))48     }49  }50 51 //初始化三个节点52 var tree = TreeNode(10)53 var left = TreeNode(3)54 var right = TreeNode(5)55 //将后两个节点分别作为第一个节点的左节点和右节点56 tree.left = left57 tree.right = right58 dump(tree)59 //Print60 /*61 ? prog.TreeNode #062   - val: 1063   ? left: Optional(prog.TreeNode)64     ? some: prog.TreeNode #165       - val: 366       - left: nil67       - right: nil68   ? right: Optional(prog.TreeNode)69     ? some: prog.TreeNode #270       - val: 571       - left: nil72       - right: nil73 */74  //获取指定节点的最大深度75 let depth = tree.getMaxDepth(tree)76 print(depth)77 //Print 278 //判断节点是否为二叉搜索树Binary Search Tree（BST）79 let bst = tree.isValIDBST(tree)80 print(bst)81 //Print false

总结

以上是内存溢出为你收集整理的[Swift4.2互动教程]八、实用进阶-(11)使用Swift创建一个二叉树BinaryTreeNode全部内容，希望文章能够帮你解决[Swift4.2互动教程]八、实用进阶-(11)使用Swift创建一个二叉树BinaryTreeNode所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。