关于此代码，如何将节点插入二叉树：
import util.Random
import collection.mutable.ArrayBuffer
import scala.collection.mutable.Queue
import scala.collection.mutable.Stack
case class Node[K](value:K, var left:Option[Node[K]],
var right:Option[Node[K]],var parent:Option[Node[K]]) {
def hasLeft:Boolean = if (left!=None) true else false
def hasRight:Boolean = if (right!=None) true else false
def hasParent:Boolean = if (parent!=None) true else false
def isLeaf:Boolean = !hasLeft && !hasRight
def isParent(n:Node[K]):Boolean = {
if (!isLeaf) {
val l = if (hasLeft) left.get else null
val r = if (hasRight) right.get else null
l==n || r==n
}
else false
}
}
abstract class BinaryTree[K] {
def add(value:K)
def remove(value:K):Boolean
def height:Int
def size:Int
}
class Tree[K](implicit ord:K=>Ordered[K]) extends BinaryTree[K] {
var root:Option[Node[K]] = None
private var count = 0
override def add(value:K) {
root match {
case None => root = Some(new Node[K](value,None,None,None))
case Some(node) => if(insert(node,value)) count+=1
}
}
def insert(node:Node[K],newVal:K):Boolean= {
if(newVal<node.value) {
node match{
case Node(_,None,_,_) => node.left =
Some(new Node[K](newVal,None,None,Some(node))); true
case Node(_,Some(left),_,_) => insert(left,newVal)
}
} else if(newVal>node.value) {
node match{
case Node(_,_,None,_) => node.right =
Some(new Node[K](newVal,None,None,Some(node))); true
case Node(_,_,Some(right),_) => insert(right,newVal)
}
} else false
}
override def remove(value:K):Boolean= {
root match {
case None => false
case Some(node) => {
binarySearch(value,node) match {
case None => false
case Some(node) => {
count-=1
delete(node)
true
}
}
}
}
}
def delete(node:Node[K]) {
node match {
case Node(value,None,None,Some(parent)) => updateParent(parent,value,None)
case Node(value,Some(child),None,Some(parent)) => {
updateParent(parent,value,Some(child))
child.parent = Some(parent)
}
case Node(value,None,Some(child),Some(parent)) => {
updateParent(parent,value,Some(child))
child.parent = Some(parent)
}
case Node(_,Some(child),None,None) => {
root = Some(child)
child.parent = None
}
case Node(_,None,Some(child),None) => {
root = Some(child)
child.parent = None
}
case Node(_,Some(left),Some(right),_) => {
var child = right
while(child.left!=None) {
child=child.left.get
}
node.parent match {
case Some(parent) => updateParent(parent,node.value,Some(child))
case None => root = Some(child)
}
child.left = node.left
child.right = node.right
left.parent = Some(child)
right.parent = Some(child)
if (child.hasParent && child.parent.get.hasLeft && child.parent.get.left.get == child)
child.parent.get.left=None
else child.parent.get.right=None
child.parent = node.parent
}
case _ =>
}
def updateParent(parent:Node[K],value:K,newChild:Option[Node[K]]) {
if(value<parent.value) parent.left = newChild
else parent.right = newChild
}
}
def binarySearch(value:K,node:Node[K]):Option[Node[K]]= {
if (value==node.value)
Some(node)
else if (value<=node.value) {
node match {
case Node(_,None,_,_) => None
case Node(_,Some(left),_,_) => binarySearch(value,left)
}
} else {
node match{
case Node(_,_,None,_) => None
case Node(_,_,Some(right),_) => binarySearch(value,right)
}
}
}
def inorder:Seq[K]= {
val nodes = new ArrayBuffer[K]()
val stack = new Stack[Node[K]]()
if (size!=0) {
var cur = root
while(!stack.isEmpty || cur!=None) {
cur match {
case Some(node) => {
stack.push(node)
cur = node.left
}
case None=> {
val tmp = stack.pop()
nodes += tmp.value
cur = tmp.right
}
}
}
}
nodes
}
def preorder:Seq[K]= {
val nodes = new ArrayBuffer[K]()
val stack = new Stack[Node[K]]()
if (size!=0) {
var cur = root
while(!stack.isEmpty || cur!=None) {
cur match {
case Some(node) => {
stack.push(node)
nodes += node.value
cur = node.left
}
case None=> {
val tmp = stack.pop()
cur = tmp.right
}
}
}
}
nodes
}
def postorder:Seq[K]= {
val nodes = new ArrayBuffer[K]()
val stack = new Stack[Node[K]]()
if (size!=0) {
var prev:Option[Node[K]] = None
stack.push(root.get)
while(!stack.isEmpty) {
val cur = stack.top
prev match {
case None=> if (cur.hasLeft) stack.push(cur.left.get) else if (cur.hasRight) stack.push(cur.right.get)
case Some(node)=>{
if(!cur.isParent(node) && cur.hasLeft) stack.push(cur.left.get)
else if (!cur.isParent(node) && cur.hasRight) stack.push(cur.right.get)
else if (cur.isParent(node) && cur.hasRight && cur.hasLeft && cur.left.get==node) stack.push(cur.right.get)
else {
stack.pop()
nodes+=cur.value
}
}
}
prev=Some(cur)
}
}
nodes
}
def postorder(node:Option[Node[K]]) {
node match{
case None=>
case Some(n)=>{
postorder(n.left)
postorder(n.right)
println(n.value)
}
}
}
override def toString:String= {
postorder.mkString(" : ")
}
override def height:Int= depth(root)
def depth(node:Option[Node[K]]):Int = {
node match {
case None => 0
case Some(n) => 1+ scala.math.max(depth(n.left),depth(n.right))
}
}
def prettyPrint(node:Option[Node[K]]):String= {
if (node == None) ""
else if(node.get.isLeaf) "\n\\t"+node.get.value.toString
else node.get.value.toString+"\n\\t"+prettyPrint(node.get.left)+"\n\\t"+prettyPrint(node.get.right)
}
def bfs {
val queue = new Queue[Option[Node[K]]]()
queue.enqueue(root)
while(!queue.isEmpty) {
queue.dequeue match {
case Some(node)=>{
println(node.value)
queue.enqueue(node.left)
queue.enqueue(node.right)
}
case None =>
}
}
}
def size = count
}
object App {
def main(args:Array[String]) {
val generator = new Random()
val tree = new Tree[Int]()
// (1 until 8).foreach(_=>tree.add(generator.nextInt(100)))
tree.add(6)
tree.add(3)
tree.add(8)
tree.add(2)
tree.add(4)
tree.add(8)
tree.add(7)
tree.add(9)
tree.add(1)
tree.add(5)
tree.postorder(tree.root)
println(tree)
tree.bfs
}
}
如果您真的想在“ main”中使用“ insert”方法，则可以这样进行：
tree.root match{
case None => tree.root = Some(new Node[Int](10,None,None,None))
case Some(node) => tree.insert(node,10)
}
此代码检查树是否具有根。如果存在根，则节点是插入点。如果没有根，则创建根。
但是你不应该这样做。您不应该直接调用此“插入”方法。此类Tree设计巧妙。它具有“添加”方法，该方法易于使用，并且当您要向树中添加值时，供您使用。“插入”方法仅是辅助方法。这是递归方法，由“ add”方法用于在适当的位置插入值。
因此，向此树添加内容的唯一正确方法是使用“ add”方法。尝试通过调用“插入”方法添加一些内容就像尝试在不使用钥匙的情况下启动汽车。您可以做到，但是为什么要把钥匙放在您的面前。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句