二叉树排序树
左子树<根节点<右节点
链式存储
节点类
using System
;
using System
.Collections
.Generic
;
using System
.Linq
;
using System
.Text
;
using System
.Threading
.Tasks
;
namespace 二叉排序树
{
class BsNode
{
public BsNode Parents
;
public BsNode LeftChild
;
public BsNode RightChild
;
public int Data
{ get; set; }
public BsNode(int item
)
{
Data
= item
;
}
}
}
树类
using System
;
using System
.Collections
.Generic
;
using System
.Linq
;
using System
.Text
;
using System
.Threading
.Tasks
;
namespace 二叉排序树
{
class BsTree
{
private BsNode root
=null;
public void Add(int item
)
{
BsNode newNode
= new BsNode(item
);
if(root
==null)
{
root
= newNode
;
}
else
{
BsNode tempNode
= null;
tempNode
= root
;
while (true)
{
if(tempNode
.Data
<=newNode
.Data
)
{
if(tempNode
.RightChild
==null)
{
tempNode
.RightChild
= newNode
;
newNode
.Parents
= tempNode
;
break;
}
else
{
tempNode
= tempNode
.RightChild
;
}
}
else
{
if(tempNode
.LeftChild
==null)
{
tempNode
.LeftChild
= newNode
;
newNode
.Parents
= tempNode
;
break;
}
else
{
tempNode
= tempNode
.LeftChild
;
}
}
}
}
}
public void MiddleTravelSal()
{
MiddleTravelSal(root
);
}
private void MiddleTravelSal(BsNode node
)
{
if(node
==null)
{
return;
}
MiddleTravelSal(node
.LeftChild
);
Console
.Write(node
.Data
+" ");
MiddleTravelSal(node
.RightChild
);
}
public bool Find(int index
)
{
return Find(root
, index
);
}
public bool Find1(int index
)
{
return Find1(root
, index
);
}
private bool Find(BsNode node
,int index
)
{
if(node
==null)
{
return false;
}
if(node
.Data
==index
)
{
return true;
}
else
{
if(Find(node
.RightChild
, index
))
{
return true;
}
if (Find(node
.LeftChild
, index
))
{
return true;
}
}
return false;
}
private bool Find1(BsNode node
,int index
)
{
if(node
== null)
{
return false;
}
if(node
.Data
==index
)
{
return true;
}
else
{
if(index
<node
.Data
)
{
return Find1(node
.LeftChild
, index
);
}
else
{
return Find(node
.RightChild
, index
);
}
}
}
public bool Find3(int index
)
{
BsNode tempNode
= root
;
while(true)
{
if (tempNode
== null)
{
return false;
}
if (tempNode
.Data
==index
)
{
return true;
}
else
{
if(index
<tempNode
.Data
)
{
tempNode
= tempNode
.LeftChild
;
}
else
{
tempNode
= tempNode
.RightChild
;
}
}
}
}
public bool Delete(int index
)
{
BsNode tempNode
= root
;
while(true)
{
if(tempNode
==null)
{
return false;
}
if(tempNode
.Data
==index
)
{
Delete(tempNode
);
return true;
}
else
{
if (index
< tempNode
.Data
)
{
tempNode
= tempNode
.LeftChild
;
}
else
{
tempNode
= tempNode
.RightChild
;
}
}
}
}
private void Delete(BsNode node
)
{
if (node
.Parents
== null)
{
root
= null;
}
if (node
.RightChild
== null&&node
.LeftChild
==null)
{
if (node
.Parents
.LeftChild
==node
)
{
node
.Parents
.LeftChild
= null;
}
if(node
.Parents
.RightChild
==node
)
{
node
.Parents
.RightChild
= null;
}
return;
}
if(node
.RightChild
== null && node
.LeftChild
!= null)
{
node
.Data
= node
.LeftChild
.Data
;
if (node
==node
.Parents
.LeftChild
)
{
node
.Parents
.LeftChild
= node
.LeftChild
;
}
else if(node
== node
.Parents
.RightChild
)
{
node
.Parents
.RightChild
= node
.LeftChild
;
}
return;
}
if (node
.RightChild
!= null && node
.RightChild
== null)
{
node
.Data
= node
.RightChild
.Data
;
if(node
==node
.Parents
.LeftChild
)
{
node
.Parents
.LeftChild
= node
.RightChild
;
}
else if(node
==node
.Parents
.RightChild
)
{
node
.Parents
.RightChild
= node
.RightChild
;
}
return;
}
else
{
BsNode tempNode
= node
.RightChild
;
while(true)
{
if (tempNode
.LeftChild
!=null)
{
tempNode
= tempNode
.LeftChild
;
}
else
{
break;
}
}
node
.Data
= tempNode
.Data
;
Delete(tempNode
);
}
}
}
}
using System
;
using System
.Collections
.Generic
;
using System
.Linq
;
using System
.Text
;
using System
.Threading
.Tasks
;
namespace 二叉排序树
{
class Program
{
static void Main(string[] args
)
{
BsTree tree
= new BsTree();
int[] data
= new int[] { 62, 58, 88, 47, 73, 99, 35, 51, 93, 37,48 };
for(int i
=0;i
<data
.Length
;i
++)
{
tree
.Add(data
[i
]);
}
Console
.WriteLine(tree
.Find3(88));
Console
.WriteLine();
Console
.ReadKey();
}
}
}
转载请注明原文地址:https://blackberry.8miu.com/read-10632.html