9-二叉树-Scala实现
构建二叉树;实现前序、中序、后序遍历;两种删除节点的原则
package com.atguigu.datastructures.binarytree object BinaryTreeDemo { def main(args: Array[String]): Unit = { //先使用比较简单的方法,直接关联 val root = new HeroNode(1,"宋江") val hero2 = new HeroNode(2,"吴用") val hero3 = new HeroNode(3,"卢俊义") val hero4 = new HeroNode(4,"林冲") val hero5 = new HeroNode(5,"关胜") root.left = hero2 root.right = hero3 hero3.left = hero5 hero3.right = hero4 val binaryTree = new BinaryTree binaryTree.root = root // binaryTree.preOrder() // binaryTree.infixOrder() // binaryTree.postOrder() // val resNode: HeroNode = binaryTree.preOrderSearch(5) // if (resNode!=null){ // printf("找到,编号=%d name=%s",resNode.no,resNode.name) // }else{ // printf("没有找到") // } // val resNode: HeroNode = binaryTree.postOrderSearch(5) // if (resNode!=null){ // printf("找到,编号=%d name=%s",resNode.no,resNode.name) // }else{ // printf("没有找到") // } binaryTree.delNode2(3) binaryTree.preOrder() } } //定义节点 class HeroNode(hNo:Int,hName:String){ val no= hNo var name = hName var left:HeroNode = null var right:HeroNode = null //前序查找 def preOrderSearch(no:Int):HeroNode={ if (no == this.no){ return this } //向左递归查找 var resNode:HeroNode = null if (this.left != null){ resNode=this.left.preOrderSearch(no) } if (resNode != null){ return resNode } //向右边递归查找 if (this.right != null){ resNode = this.right.preOrderSearch(no) } return resNode } //前序遍历 def preOrder(): Unit ={ //先输出当前节点值 printf("节点信息 no=%d name=%s\n",no,name) //向左递归输出左子树 if (this.left != null){ this.left.preOrder() } if (this.right != null){ this.right.preOrder() } } //中序查找 def infixOrderSearch(no:Int):HeroNode={ var resNode:HeroNode = null //先向左递归查找 if (this.left !=null){ resNode=this.left.infixOrderSearch(no) } if (resNode != null){ return resNode } if (no == this.no){ return this } //向右递归查找 if(this.right != null){ resNode = this.right.infixOrderSearch(no) } return resNode } def infixOrder(): Unit ={ if (this.left != null){ this.left.infixOrder() } printf("节点信息 no=%d name=%s\n",no,name) if (this.right != null){ this.right.infixOrder() } } //后序查找 def postOrderSearch(no:Int):HeroNode={ var resNode:HeroNode = null if (this.left !=null){ resNode=this.left.postOrderSearch(no) } if (resNode != null){ return resNode } if (this.right != null){ resNode = this.right.postOrderSearch(no) } if (resNode != null){ return resNode } if (no == this.no){ return this } resNode } def postOrder(): Unit ={ if (this.left != null){ this.left.postOrder() } if (this.right != null){ this.right.postOrder() } printf("节点信息 no=%d name=%s\n",no,name) } //删除节点 //规则:如果是叶子节点,直接删除这个节点;非叶子节点,直接删除该子树 def delNode(no:Int): Unit ={ //首先比较当前节点的左子节点是否为要删除的节点 if (this.left != null && this.left.no == no) { this.left = null return } //比较当前节点的右子节点是否为要删除的节点 if (this.right != null && this.right.no == no){ this.right = null return } //向左递归 if (this.left != null){ this.left.delNode(no) } if (this.right != null){ this.right.delNode(no) } } /** * 另一种删除规则 * @param no */ def delNode2(no:Int): Unit ={ if (this.left != null && this.left.no == no) { if (this.left.left != null && this.left.right != null){ val temp=this.left.right this.left = this.left.left this.left.left = temp return } if (this.left.left != null && this.left.right == null){ val temp= this.left.left this.left = temp return } this.left = null return } //比较当前节点的右子节点是否为要删除的节点 if (this.right != null && this.right.no == no){ if (this.right.left != null && this.right.right != null){ val temp=this.right.right this.right = this.right.left this.right.left = temp return } if (this.right.left != null && this.right.right == null){ val temp= this.right.left this.right = temp return } this.right = null return } //向左递归 if (this.left != null){ this.left.delNode(no) } if (this.right != null){ this.right.delNode(no) } } } class BinaryTree{ var root:HeroNode = null //前序查找 def preOrderSearch(no:Int):HeroNode={ if (root !=null){ return root.preOrderSearch(no) }else{ return null } } //前序遍历 def preOrder(): Unit ={ if (root != null){ root.preOrder() }else{ println("当前树为空") } } //中序遍历查找 def infixOrderSearch(no:Int):HeroNode={ if (root != null){ root.infixOrderSearch(no) }else{ null } } def infixOrder(): Unit ={ if (root != null){ root.infixOrder() }else{ println("当前树为空") } } //后序遍历查找 def postOrderSearch(no:Int):HeroNode={ if (root != null){ root.postOrderSearch(no) }else{ null } } def postOrder(): Unit ={ if (root != null){ root.postOrder() }else{ println("当前树为空") } } //删除指定节点 def delNode(no:Int): Unit ={ if (root != null){ if (root.no == no){ root=null }else { root.delNode(no) } } } def delNode2(no:Int): Unit ={ if (root != null){ if (root.no == no){ root=null }else { root.delNode2(no) } } } }