我来联谊——以武会友(智解二叉树)

everyone · 发表于 2008-10-13 17:17:55

这是我几年上学时想到的问题。
二叉树的性质有很多，其中一个是对给定先中序的二叉树，其结构只能唯一。
我就不信，后来写了个程序还真是如此。
这题就是，将给定的遍历顺序的二叉树图打出来，以便查验。
前a,c,d
后c,a,d
 
 
我不把窍门说出来也许有人以为我胡侃。
1节点不定，一定用递归。
2不指定头节点的名称一定是a.可能是字串序列里的任一个。也就是说，确定头节点的是某名称在别的序列里的相对位置。
3推荐使用access数据库，在新机器上不用装。sql之类没必要。喜欢文件的也可以用文件。
 
我写这个2，3天。
来信请回 wangyingshi19850612@126.com 专用net c#

马大哈 · 发表于 2008-10-16 12:02:12

算法我是七窍通了六窍,呵呵~~~~

firendless · 发表于 2008-11-16 14:40:10

还没学...百度了一个，嘿嘿
 
<blockquote dir="ltr" style="MARGIN-RIGHT: 0px">
'二叉树的结点类 Option Explicit Private mNodeValue As String '结点值 Private mLeftNode As clsBiTreeNode '左结点 Private mRightNode As clsBiTreeNode '右结点 '得到结点的值 Public Property Get NodeValue() As String NodeValue = mNodeValue End Property '设置结点的值 Public Property Let NodeValue(ByVal pNodeValue As String) mNodeValue = pNodeValue End Property '得到左结点 Public Property Get LeftNode() As clsBiTreeNode Set LeftNode = mLeftNode End Property '设置左结点 Public Property Let LeftNode(ByVal pLeftNode As clsBiTreeNode) Set mLeftNode = pLeftNode End Property '得到右结点 Public Property Get RightNode() As clsBiTreeNode Set RightNode = mRightNode End Property '设置右结点 Public Property Let RightNode(ByVal pRightNode As clsBiTreeNode) Set mRightNode = pRightNode End Property －－－－－－－－－－－－－－－－－－－－－－－ '一个二叉树的类 Option Explicit Private mRoot As clsBiTreeNode '建立一棵二叉树，同时以strValue为值建立根结点 Public Sub CreateTree(strValue As String) Set mRoot = New clsBiTreeNode mRoot.NodeValue = strValue End Sub '求二叉树的根结点 Public Function Root() As clsBiTreeNode Set Root = mRoot End Function '求二叉树中值为strValue的结点的双亲 Public Function Parent(strValue As String) As clsBiTreeNode Dim NodeTemp As clsBiTreeNode FindNode mRoot, strValue, NodeTemp Set Parent = NodeTemp End Function '求二叉树T中值为strValue的结点的左孩子 Public Function LeftChild(strValue As String) As clsBiTreeNode Dim NodeTemp As clsBiTreeNode Set LeftChild = Nothing Set NodeTemp = FindNode(mRoot, strValue) If Not NodeTemp Is Nothing Then Set LeftChild = NodeTemp.LeftNode End Function '求二叉树T中值为strValue的结点的右孩子 Public Function RightChild(strValue As String) As clsBiTreeNode Dim NodeTemp As clsBiTreeNode Set RightChild = Nothing Set NodeTemp = FindNode(mRoot, strValue) If Not NodeTemp Is Nothing Then Set RightChild = NodeTemp.RightNode End Function '遍历二叉树：采用前序遍历******************* Public Sub TraverseF(ByRef Node As clsBiTreeNode) If Node Is Nothing Then Exit Sub Debug.Print Node.NodeValue & ":" Traverse Node.LeftNode Traverse Node.RightNode End Sub '遍历二叉树：采用中序遍历***************** Public Sub TraverseM(ByRef Node As clsBiTreeNode) If Node Is Nothing Then Exit Sub Traverse Node.LeftNode Debug.Print Node.NodeValue & ":" Traverse Node.RightNode End Sub '遍历二叉树：采用后序遍历*************** Public Sub TraverseB(ByRef Node As clsBiTreeNode) If Node Is Nothing Then Exit Sub Traverse Node.LeftNode Traverse Node.RightNode Debug.Print Node.NodeValue & ":" End Sub '查找值为strValue的(第一个)结点：采用前序遍历 '参数说明： 'Node为树的根结点 'strValue要查找的结点的值 'myParentNode为要查找的结点的双亲结点 'pParentNode为第一个参数Node结点的双亲结点，是为了保存双亲结点而设置 Private Function FindNode(ByRef Node As clsBiTreeNode, ByVal strValue As String, Optional ByRef myParentNode As clsBiTreeNode, Optional ByRef pParentNode As clsBiTreeNode) As clsBiTreeNode Dim NodeTemp As clsBiTreeNode Set FindNode = Nothing '如果为空则退出 If Node Is Nothing Then Exit Function End If If Node.NodeValue = strValue Then Set FindNode = Node Set myParentNode = pParentNode Exit Function Else Set NodeTemp = FindNode(Node.LeftNode, strValue, myParentNode, Node) If Not NodeTemp Is Nothing Then Set FindNode = NodeTemp Set pParentNode = Node Exit Function End If Set NodeTemp = FindNode(Node.RightNode, strValue, myParentNode, Node) If Not NodeTemp Is Nothing Then Set FindNode = NodeTemp Set pParentNode = Node Exit Function End If End If End Function '在二叉树中，将值为strChild的结点作为值为strParetn的结点的左孩子插入：返回""表示成功，否则返回错误信息 Public Function AddLeftChild(ByVal strParent As String, ByVal strChild As String) As String Dim NodeTemp As clsBiTreeNode AddLeftChild = "" Set NodeTemp = FindNode(mRoot, strParent) If NodeTemp Is Nothing Then AddLeftChild = "没有找到值为" & strParent & "的结点" End If If NodeTemp.LeftNode Is Nothing Then Dim NewNode As New clsBiTreeNode NewNode.NodeValue = strChild NodeTemp.LeftNode = NewNode Else AddLeftChild = "值为" & strParent & "的结点的左结点已经存在" End If End Function '在二叉树中，将值为strChild的结点作为值为strParetn的结点的右孩子插入：返回""表示成功，否则返回错误信息 Public Function AddRightChild(ByVal strParent As String, ByVal strChild As String) As String Dim NodeTemp As clsBiTreeNode AddRightChild = "" Set NodeTemp = FindNode(mRoot, strParent) If NodeTemp Is Nothing Then AddRightChild = "没有找到值为" & strParent & "的结点" End If If NodeTemp.RightNode Is Nothing Then Dim NewNode As New clsBiTreeNode NewNode.NodeValue = strChild NodeTemp.RightNode = NewNode Else AddRightChild = "值为" & strParent & "的结点的右结点已经存在" End If End Function '在二叉树中，删除值为strValue的结点的左孩子：返回""表示成功，否则返回错误信息 Public Function DelLeftChild(ByVal strValue As String) As String Dim NodeTemp As clsBiTreeNode DelLeftChild = "" Set NodeTemp = FindNode(mRoot, strValue) If NodeTemp Is Nothing Then DelLeftChild = "没有找到值为" & strValue & "的结点" End If If Not NodeTemp.LeftNode Is Nothing Then NodeTemp.LeftNode = Nothing End If End Function '在二叉树中，删除值为strValue的结点的右孩子：返回""表示成功，否则返回错误信息 Public Function DelRightChild(ByVal strValue As String) As String Dim NodeTemp As clsBiTreeNode DelRightChild = "" Set NodeTemp = FindNode(mRoot, strValue) If NodeTemp Is Nothing Then DelRightChild = "没有找到值为" & strValue & "的结点" End If If Not NodeTemp.RightNode Is Nothing Then NodeTemp.RightNode = Nothing End If End Function </blockquote>

BlackHatzw · 发表于 2010-5-5 19:01:32

帮你顶一下

账号		自动登录	找回密码
密码			加入我们

我来联谊——以武会友(智解二叉树)

论坛牛人

贡献奖

关注奖

最佳版主

进步奖

人气王

疯狂作品奖

精英奖

赞助论坛勋章

乐于助人勋章