C# 广义表创建二叉树
本帖最后由 u010097981 于 2013-04-19 00:30:34 编辑 最近做毕业设计用广义表创建一颗二叉树，我写了一些代码总是创建失败，求帮忙~~
以下是我的代码,请高手指点，为什么创建失败，返回值总是空？
BiNode类：
public class BiNode
{
private char data; //数据域
private BiNode lChild; //左孩子
private BiNode rChild; //右孩子
//构造函数
public BiNode()
{
data = ' ';
lChild = null;
rChild = null;
}
//数据属性
public char Data
{
get
{
return data;
}
set
{
data = value;
}
}
//左孩子属性
public BiNode LChild
{
get
{
return lChild;
}
set
{
lChild = value;
}
}
//右孩子属性
public BiNode RChild
{
get
{
return rChild;
}
set
{
rChild = value;
}
}
}
BiTree类：
public class BiTree
{
private BiNode head; //头引用
//头引用属性
public BiNode Head
{
get
{
return head;
}
set
{
head = value;
}
}
//构造函数
public BiTree()
{
head = null;
}
//广义表创建二叉树
private void preCreatTree(BiNode node, char[] A, ref int i)
{
i++;
if (A[i]=='#')
{
node = null;
return;
}
node = new BiNode();
node.Data = A[i];
if (i==A.Length-1)
{
return;
}
else
if (A[i+1]=='(')
{
i++;
}
else
{
node.LChild = null;
node.RChild = null;
return;
}
preCreatTree(node.LChild, A, ref i);
i++;
preCreatTree(node.RChild, A, ref i);
i++;
}
public void CreatBiTree(BiTree T,char[] A)
{
int i = -1;
preCreatTree(T.Head, A, ref i);
}
}
PS：广义表a(b,c)用数组表示为A={'a','(','b',',','c',')'}; C# 二叉树
[解决办法]
本帖最后由 caozhy 于 2013-04-19 03:35:58 编辑
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Node<T>
{
public T Value { get; set; }
public Node<T> Left { get; set; }
public Node<T> Right { get; set; }
private Node() { }
public Node(T value) { Value = value; }
public Node(T value, Node<T> left, Node<T> right) : this(value)
{
Left = left;
Right = right;
}
public Node(T value, T left, T right) : this(value, new Node<T>(left), new Node<T>(right)) { }
public override string ToString()
{
if (Left == null && Right == null) return Value.ToString();
return string.Format("{0}({1},{2})", Value.ToString(), Left.ToString(), Right.ToString());
}
}
class BinaryTree<T>
{
public Node<T> Root { get; set; }
public BinaryTree(T value) : this(new Node<T>(value)) { }
public BinaryTree(Node<T> root) { Root = root; }
public override string ToString()
{
if (Root == null) return "";
return Root.ToString();
}
}
static class TreeParser
{
static Node<char> ParseNode(string expression)
{
if (expression == "") return null;
if (expression.Length == 1 && expression[0] >= 'a' && expression[0] <= 'z') return new Node<char>(expression[0]);
Stack<Node<char>> stack = new Stack<Node<char>>();
string expression1 = expression + "#";
for (int i = 0; i < expression.Length; i++)
{
if (expression1[i] >= 'a' && expression1[i] <= 'z')
{
if (expression1[i + 1] == '(')
{
stack.Push(new Node<char>(expression1[i]));
continue;
}
if (expression1[i + 1] == ',')
{
stack.Peek().Left = new Node<char>(expression[i]);
continue;
}
if (expression1[i + 1] == ')')
{
stack.Peek().Right = new Node<char>(expression[i]);
continue;
}
throw new ArgumentException();
}
if (expression1[i] == '(')
{
if (expression1[i + 1] >= 'a' && expression1[i + 1] <= 'z')
{
continue;
}
throw new ArgumentException();
}
if (expression1[i] == ')')
{
if (expression1[i + 1] == ',')
{
var nodeleft = stack.Pop();
stack.Peek().Left = nodeleft;
continue;
}
if (expression1[i + 1] == ')')
{
var noderight = stack.Pop();
stack.Peek().Right = noderight;
continue;
}
if (expression1[i + 1] == '#')
{
continue;
}
throw new ArgumentException();
}
if (expression1[i] == ',')
{
if (expression1[i + 1] >= 'a' && expression1[i + 1] <= 'z')
{
continue;
}
throw new ArgumentException();
}
}
return stack.Peek();
}
public static BinaryTree<char> Parse(string expression)
{
return new BinaryTree<char>(ParseNode(expression));
}
}
class Program
{
static void Main(string[] args)
{
var tree = TreeParser.Parse("a(b,c(d(e(h(j,k),i(l,m(n,o(p,q)))),f),g(r(t(v,w),u(x,y)),s)))");
Console.WriteLine(tree);
}
}
}
