二叉树
- 创建二叉查找树
- 前序 中序 后序 遍历（递归/非递归）
- 深度
- 判断是否为二叉平衡树
- 判断是否为二叉平衡树
- 判断是否为满二叉树
- 二叉树反转
class BTNode{
var isFirst:Bool
var treeNode:TreeNode
init(_ isFirst:Bool,_ treeNode:TreeNode) {
self.isFirst = isFirst
self.treeNode = treeNode
}
}
class TreeNode{
var val :Int
var letf:TreeNode?
var right:TreeNode?
init(_ val:Int) {
self.val = val
}
}
class CreateBTree{
var tree:TreeNode?
func insertVal(_ newItem:Int){
if tree == nil {
tree = TreeNode(newItem)
}else{
var a = tree
var b = tree
while a != nil {
if a!.val<newItem {
b = a
a = a?.right
}else{
b = a
a = a?.letf
}
}
let temp = TreeNode(newItem)
if b!.val > newItem {
b?.letf = temp
}else{
b?.right = temp
}
}
}
class func resursionInsert (_ val :Int , _ tree :TreeNode?) ->TreeNode? {
var myTree = tree
if myTree == nil {
myTree = TreeNode(val)
}else{
if myTree!.val < val {
myTree?.right = resursionInsert(val,myTree?.right)
}else{
myTree?.letf = resursionInsert(val,myTree?.letf)
}
}
return myTree
}
class func resurionPreOrder (_ tree:TreeNode? ,_ vals:inout [Int]) {
let root = tree
if root != nil {
vals.append(root!.val)
resurionPreOrder(root?.letf,&vals)
resurionPreOrder(root?.right,&vals)
}
}
class func resurionMidOrder (_ tree:TreeNode? ,_ vals:inout [Int]) {
let root = tree
if root != nil {
resurionMidOrder(root?.letf,&vals)
vals.append(root!.val)
resurionMidOrder(root?.right,&vals)
}
}
class func resurionPostOrder (_ tree:TreeNode? ,_ vals:inout [Int]) {
let root = tree
if root != nil {
resurionPostOrder(root?.letf,&vals)
resurionPostOrder(root?.right,&vals)
vals.append(root!.val)
}
}
class func printOutTree(_ tree:TreeNode?){
let myTree = tree
if tree != nil {
print(myTree!.val)
printOutTree(myTree?.letf)
printOutTree(myTree?.right)
}
}
class func preOrder(_ tree:TreeNode?) -> [Int]{
var vals = [Int]()
var roots = [TreeNode]()
var node = tree
while !roots.isEmpty || node != nil {
if node != nil {
vals.append(node!.val)
roots.append(node!)
node = node!.letf
}else{
node = roots.removeLast().right
}
}
return vals
}
class func midOrder(_ tree :TreeNode?) ->[Int]{
var vals = [Int]()
var roots = [TreeNode]()
var node = tree
while !roots.isEmpty || node != nil {
if node != nil {
roots.append(node!)
node = node?.letf
}else{
node = roots.removeLast()
vals.append(node!.val)
node = node?.right
}
}
return vals
}
class func postOrder(_ tree :TreeNode?) ->[Int]{
var vals = [Int]()
var btNodes = [BTNode]()
var node = tree
var temp :BTNode?
while !btNodes.isEmpty || node != nil {
while node != nil {
let btTree = BTNode(true,node!)
btNodes.append(btTree)
node = node?.letf
}
if !btNodes.isEmpty {
temp = btNodes.removeLast()
if temp!.isFirst == true{
temp?.isFirst = false
btNodes.append(temp!)
node = temp?.treeNode.right
}else{
vals.append(temp!.treeNode.val)
node = nil
}
}
}
return vals
}
class func depthMax(_ root :TreeNode?) -> Int{
guard let note = root else{
return 0
}
return max(depthMax(note.letf), depthMax(note.right)) + 1
}
class func numberOfLeafsInTree(_ root:TreeNode?) -> Int{
let node = root
if node == nil {
return 0
}
if (node?.letf == nil && node?.right == nil){
return 1
}
return numberOfLeafsInTree(node?.letf) + numberOfLeafsInTree(node?.right)
}
private func _helper (_ root :TreeNode? ,_ min:Int?, _ max:Int?) -> Bool{
guard let node = root else {
return true
}
if let min = min ,node.val <= min{
return false
}
if let max = max ,node.val >= max{
return false
}
return _helper(node.letf,min,node.val) && _helper(node.right,node.val,max)
}
func isValiBST (_ tree:TreeNode)->Bool{
return _helper(tree,nil,nil)
}
class func isCompleteBtree(_ tree:TreeNode?) ->Bool{
var root = tree
var isComplete = false
var queue = [TreeNode?]()
if root == nil {
return false
}
if root?.letf == nil && root?.right == nil{
return true
}
if root?.letf == nil && root?.right != nil{
return false
}
queue.append(root!)
while !queue.isEmpty {
root = queue.removeFirst()
if root?.letf == nil && root?.right != nil{
return false
}
if isComplete == true && (root?.letf != nil || root?.right != nil ){
return false
}
if root?.right == nil{
isComplete = true
}
if root?.letf != nil{
queue.append(root?.letf)
}
if root?.right != nil{
queue.append(root?.right)
}
}
return isComplete
}
class func isFullBtree (_ tree : TreeNode?) -> Bool{
let root = tree
if (root == nil)
{
return false
}
let depth = CreateBTree.depthMax(root)
let numLeaf = CreateBTree.numberOfLeafsInTree(root)
if Decimal(numLeaf) == pow(2, depth-1) {
return true
}
return false
}
class func invertBinaryTree (_ tree: TreeNode?) -> TreeNode?{
if tree == nil
{
return nil
}
if tree?.letf == nil && tree?.right == nil
{
return tree
}
invertBinaryTree(tree?.letf )
invertBinaryTree(tree?.right)
(tree!.letf,tree!.right) = (tree!.right,tree!.letf)
return tree
}
private class func isBalanceTreeOnce(rootNode:TreeNode?,depth:inout Int) -> Bool {
if rootNode == nil {
depth = 0
return true
}
var leftDepth:Int = 0
var rightDepth:Int = 0
if isBalanceTreeOnce(rootNode: rootNode?.letf, depth: &leftDepth) && isBalanceTreeOnce(rootNode: rootNode?.right, depth: &rightDepth) {
print("left:\(leftDepth)" )
print("right:\(rightDepth)")
print(rootNode!.val)
let diff:Int = leftDepth - rightDepth
if diff <= 1 && diff >= -1 {
depth = leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1
print(depth)
return true
}
}
return false
}
class func isAVLTree(rootNode:TreeNode?) -> Bool {
var depth:Int = 0
return isBalanceTreeOnce(rootNode: rootNode, depth: &depth)
}
}
var tree = CreateBTree()
[1,2,4,5,7,8,3,6 ].map {
tree.insertVal($0)
}
var node1 = TreeNode(1)
var node2 = TreeNode(2)
var node3 = TreeNode(3)
var node4 = TreeNode(4)
var node5 = TreeNode(5)
var node6 = TreeNode(6)
var node7 = TreeNode(7)
var node8 = TreeNode(8)
node1.letf = node2
node1.right = node3
node2.letf = node4
node2.right = node5
node5.letf = node7
node5.right = node8
node3.right = node6
var newTree = CreateBTree.resursionInsert(2, nil)
[1,5,6,7,8,9].map {
CreateBTree.resursionInsert($0, newTree)
}
print(CreateBTree.preOrder(node1))
print(CreateBTree.midOrder(node1))
print(CreateBTree.postOrder(node1))
var valsPre = [Int]()
CreateBTree.resurionPreOrder(node1, &valsPre)
print (valsPre)
var valsMid = [Int]()
CreateBTree.resurionMidOrder(node1, &valsMid)
print (valsMid)
var valsPost = [Int]()
CreateBTree.resurionPostOrder(node1, &valsPost)
print (valsPost)
print (CreateBTree.depthMax(node1))
print(tree.isValiBST(newTree!))
node1.letf = node2
node1.right = node3
node2.letf = node4
node2.right = nil
node3.letf = nil
node3.right = nil
print(CreateBTree.isCompleteBtree(node1))
print (CreateBTree.depthMax(node1))
print(CreateBTree.isFullBtree(node1))
print(CreateBTree.preOrder(node1))
var newTreenode = CreateBTree.invertBinaryTree(node1)
print(CreateBTree.preOrder(node1))
print(CreateBTree.isCompleteBtree(node1))
print(CreateBTree.isAVLTree(rootNode: node1))
//aaaf
//CreateBTree.printOutTree(tree.tree)
