自定义节点二叉树怎么做
定义一个Pair类 包含pair.x pair.y 即(x,y)
对于任意两个pair (a,b) (c,d)来说，有三种情况
大于: 满足 a>=c, b>d 或者 a>c b>=d
小于：满足 a<=c b<d 或者 a<c b<=d
等于：满足a==c b==d
其他情况认为是不可比较的，comparable方法返回false
现在给出一个List包含n个pair来创建二叉树，其中根节点默认为(-1,-1)
满足以下条件
左和右两个子节点Pair均大于父节点Pair
左右两个子节点之间满足不可以比较
每个节点包含 value（即pair）， leftchild 和 rightchild
throw new ArgumentException("Could not constract BinaryTreeNode, small");
这里拼写错了
这里创建了3个节点
两个儿子节点是5,8 和8,4
根节点是1,2
当然你也可以创建更多层。
如果不符合你的条件，就无法创建，丢出异常。没有异常就是成功了。
至于打印输出之类的，你自己完善吧。
给你拿C#写了一个
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Q690317
{
class Pair : IComparable<Pair>
{
public int x { get; set; }
public int y { get; set; }
public Pair(int x, int y)
{
this.x = x;
this.y = y;
}
public bool Compareable(Pair other)
{
try
{
CompareTo(other);
}
catch
{
return false;
}
return true;
}
public int CompareTo(Pair other)
{
if ((x >= other.x && y > other.y) || (x > other.x && y >= other.y)) return 1;
if ((x <= other.x && y < other.y) || (x < other.x && y <= other.y)) return -1;
if (x == other.x && y == other.y) return 0;
throw new ArgumentException("Incompareable");
}
}
class BinaryTreeNode
{
public BinaryTreeNode leftchild { get; private set; }
public BinaryTreeNode rightchild { get; private set; }
public Pair value { get; private set; }
public BinaryTreeNode(int x, int y)
: this(new Pair(x, y))
{
}
public BinaryTreeNode(Pair value)
{
this.value = value;
}
public BinaryTreeNode(int x, int y, BinaryTreeNode left, BinaryTreeNode right)
: this(new Pair(x, y), left, right)
{
}
public BinaryTreeNode(Pair value, BinaryTreeNode left, BinaryTreeNode right)
{
this.value = value;
if (left.value.CompareTo(value) <= 0 || right.value.CompareTo(value) <= 0)
throw new ArgumentException("Could not constract BinaryTreeNode, samll");
if (left.value.Compareable(right.value))
throw new ArgumentException("Could not constract BinaryTreeNode, compareable");
leftchild = left;
rightchild = right;
}
}
class Program
{
static void Main(string[] args)
{
BinaryTreeNode left = new BinaryTreeNode(5, 8);
BinaryTreeNode right = new BinaryTreeNode(8, 4);
BinaryTreeNode root = new BinaryTreeNode(1, 2, left, right);
}
}
}
没有一个复杂的比较，做出来肯定不严谨。
String pairItemString1 = "(0,1);(1,2);(2,1)";
tree = readBinaryTree(null, parsePairString(pairItemString1));
printLevelOrder(tree);
String pairItemString2 = "(1,2);(2,1);(0,1)";
tree = readBinaryTree(null, parsePairString(pairItemString2));
printLevelOrder(tree);
String pairItemString3 = "(1,2);(0,1);(2,1)";
tree = readBinaryTree(null, parsePairString(pairItemString3));
printLevelOrder(tree);
输出：
(0,1)
(1,2) (2,1)
-- -- -- --
cannot add this pair:(2,1)
(0,1)
(1,2) --
-- --
(0,1)
(1,2) (2,1)
-- -- -- --
不同的次序，会输出不同，因为第2中顺序加入第2个没法构造满足条件的树，只好放弃。除非是可以插入一个特殊节点来做中介
（即别个都可以大于它，可以存在为一个非叶子节点）。
既然已经采纳别人了，我就不再继续了，也不会给代码。这个只是一个讨论。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Q690317
{
class Pair : IComparable<Pair>
{
public int x { get; private set; }
public int y { get; private set; }
public Pair(int x, int y)
{
this.x = x;
this.y = y;
}
public bool Compareable(Pair other)
{
try
{
CompareTo(other);
}
catch
{
return false;
}
return true;
}
public int CompareTo(Pair other)
{
if ((x >= other.x && y > other.y) || (x > other.x && y >= other.y)) return 1;
if ((x <= other.x && y < other.y) || (x < other.x && y <= other.y)) return -1;
if (x == other.x && y == other.y) return 0;
throw new ArgumentException("Incompareable");
}
public override string ToString()
{
return string.Format("({0},{1})", x, y);
}
}
class BinaryTreeNode
{
public BinaryTreeNode leftchild { get; set; }
public BinaryTreeNode rightchild { get; set; }
//public BinaryTreeNode leftchild { get; private set; }
//public BinaryTreeNode rightchild { get; private set; }
public Pair value { get; private set; }
public BinaryTreeNode(int x, int y)
: this(new Pair(x, y))
{
}
public BinaryTreeNode(Pair value)
{
this.value = value;
}
public BinaryTreeNode(int x, int y, BinaryTreeNode left, BinaryTreeNode right)
: this(new Pair(x, y), left, right)
{
}
public BinaryTreeNode(Pair value, BinaryTreeNode left, BinaryTreeNode right)
{
this.value = value;
//if (left.value.CompareTo(value) <= 0 || right.value.CompareTo(value) <= 0)
// throw new ArgumentException("Could not constract BinaryTreeNode, small");
//if (left.value.Compareable(right.value))
// throw new ArgumentException("Could not constract BinaryTreeNode, compareable");
leftchild = left;
rightchild = right;
}
public override string ToString()
{
string s = "";
if (leftchild == null)
s += "(null)";
else
s += "(" + leftchild + ")";
s += value;
if (rightchild == null)
s += "(null)";
else
s += "(" + rightchild + ")";
return s;
}
}
class Program
{
static bool TryInsertToTree(BinaryTreeNode root, Pair p)
{
if (p.Compareable(root.value) && p.CompareTo(root.value) <= 0) return false;
if (p.Compareable(root.value) && p.CompareTo(root.value) > 0)
{
if (root.leftchild == null)
{
root.leftchild = new BinaryTreeNode(p);
return true;
}
if (root.rightchild == null && !root.leftchild.value.Compareable(p))
{
root.rightchild = new BinaryTreeNode(p);
return true;
}
else
{
return TryInsertToTree(root.leftchild, p);
}
}
return false;
}
static void Main(string[] args)
{
List<Pair> list = new List<Pair>()
{
new Pair(0, 1),
new Pair(1, 0),
new Pair(2, 3),
new Pair(3, 3),
new Pair(3, 2),
new Pair(2, 1),
new Pair(1, 1)
};
var root = new BinaryTreeNode(-1, -1);
foreach (var item in list)
{
TryInsertToTree(root, item);
}
Console.WriteLine(root);
}
}
}
((((null)(3,3)(null))(2,3)(null))(0,1)((null)(3,2)(null)))(-1,-1)((null)(1,0)(null))
Press any key to continue . . .
你看下这样行不行。好像没法都加上。
这次7个数据都挂上了。
List<Pair> list = new List<Pair>()
{
new Pair(0,5),
new Pair(5,8),
new Pair(5,10),
new Pair(6,10),
new Pair(5,12),
new Pair(7,12),
new Pair(9,12)
};
结果
(((((((null)(9,12)(null))(7,12)(null))(6,10)(null))(5,10)((null)(5,12)(null)))(5,8)(null))(0,5)(null))(-1,-1)(null)
Press any key to continue . . .
都挂上了。
用开发工具看，比较直观。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Q690317
{
class Pair : IComparable<Pair>
{
public int x { get; private set; }
public int y { get; private set; }
public Pair(int x, int y)
{
this.x = x;
this.y = y;
}
public bool Compareable(Pair other)
{
try
{
CompareTo(other);
}
catch
{
return false;
}
return true;
}
public int CompareTo(Pair other)
{
if ((x >= other.x && y > other.y) || (x > other.x && y >= other.y)) return 1;
if ((x <= other.x && y < other.y) || (x < other.x && y <= other.y)) return -1;
if (x == other.x && y == other.y) return 0;
throw new ArgumentException("Incompareable");
}
public override string ToString()
{
return string.Format("({0},{1})", x, y);
}
}
class BinaryTreeNode
{
public BinaryTreeNode leftchild { get; set; }
public BinaryTreeNode rightchild { get; set; }
//public BinaryTreeNode leftchild { get; private set; }
//public BinaryTreeNode rightchild { get; private set; }
public Pair value { get; private set; }
public BinaryTreeNode(int x, int y)
: this(new Pair(x, y))
{
}
public BinaryTreeNode(Pair value)
{
this.value = value;
}
public BinaryTreeNode(int x, int y, BinaryTreeNode left, BinaryTreeNode right)
: this(new Pair(x, y), left, right)
{
}
public BinaryTreeNode(Pair value, BinaryTreeNode left, BinaryTreeNode right)
{
this.value = value;
//if (left.value.CompareTo(value) <= 0 || right.value.CompareTo(value) <= 0)
// throw new ArgumentException("Could not constract BinaryTreeNode, small");
//if (left.value.Compareable(right.value))
// throw new ArgumentException("Could not constract BinaryTreeNode, compareable");
leftchild = left;
rightchild = right;
}
public override string ToString()
{
string s = "";
if (leftchild == null)
s += "(null)";
else
s += "(" + leftchild + ")";
s += value;
if (rightchild == null)
s += "(null)";
else
s += "(" + rightchild + ")";
return s;
}
}
class Program
{
static bool TryInsertToTree(BinaryTreeNode root, Pair p)
{
if (root.rightchild != null)
{
if (TryInsertToTree(root.rightchild, p))
return true;
}
if (root.leftchild != null)
{
if (TryInsertToTree(root.leftchild, p))
return true;
}
if (p.Compareable(root.value) && p.CompareTo(root.value) > 0 && root.leftchild == null)
{
root.leftchild = new BinaryTreeNode(p);
return true;
}
if (p.Compareable(root.value) && p.CompareTo(root.value) > 0 && root.rightchild == null && !root.leftchild.value.Compareable(p))
{
root.rightchild = new BinaryTreeNode(p);
return true;
}
return false;
}
static void Main(string[] args)
{
List<Pair> list = new List<Pair>()
{
new Pair(5,8),
new Pair(7,2),
new Pair(9,5),
new Pair(5,10),
new Pair(10,10),
new Pair(12,5),
new Pair(6,10),
new Pair(12,11)
};
var root = new BinaryTreeNode(-1, -1);
foreach (var item in list)
{
TryInsertToTree(root, item);
}
Console.WriteLine(root);
}
}
}
((((null)(6,10)(null))(5,10)(null))(5,8)(null))(-1,-1)((((null)(10,10)(null))(9,5)(((null)(12,11)(null))(12,5)(null)))(7,2)(null))
Press any key to continue . . .
排序的也写好了
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Q690317
{
class Pair : IComparable<Pair>
{
public int x { get; private set; }
public int y { get; private set; }
public Pair(int x, int y)
{
this.x = x;
this.y = y;
}
public bool Compareable(Pair other)
{
try
{
CompareTo(other);
}
catch
{
return false;
}
return true;
}
public int CompareTo(Pair other)
{
if ((x >= other.x && y > other.y) || (x > other.x && y >= other.y)) return 1;
if ((x <= other.x && y < other.y) || (x < other.x && y <= other.y)) return -1;
if (x == other.x && y == other.y) return 0;
throw new ArgumentException("Incompareable");
}
public override string ToString()
{
return string.Format("({0},{1})", x, y);
}
}
class BinaryTreeNode
{
public BinaryTreeNode leftchild { get; set; }
public BinaryTreeNode rightchild { get; set; }
//public BinaryTreeNode leftchild { get; private set; }
//public BinaryTreeNode rightchild { get; private set; }
public Pair value { get; private set; }
public BinaryTreeNode(int x, int y)
: this(new Pair(x, y))
{
}
public BinaryTreeNode(Pair value)
{
this.value = value;
}
public BinaryTreeNode(int x, int y, BinaryTreeNode left, BinaryTreeNode right)
: this(new Pair(x, y), left, right)
{
}
public BinaryTreeNode(Pair value, BinaryTreeNode left, BinaryTreeNode right)
{
this.value = value;
//if (left.value.CompareTo(value) <= 0 || right.value.CompareTo(value) <= 0)
// throw new ArgumentException("Could not constract BinaryTreeNode, small");
//if (left.value.Compareable(right.value))
// throw new ArgumentException("Could not constract BinaryTreeNode, compareable");
leftchild = left;
rightchild = right;
}
public override string ToString()
{
string s = "";
if (leftchild == null)
s += "(null)";
else
s += "(" + leftchild + ")";
s += value;
if (rightchild == null)
s += "(null)";
else
s += "(" + rightchild + ")";
return s;
}
}
class Program
{
static bool TryInsertToTree(BinaryTreeNode root, Pair p)
{
if (root.rightchild != null)
{
if (TryInsertToTree(root.rightchild, p))
return true;
}
if (root.leftchild != null)
{
if (TryInsertToTree(root.leftchild, p))
return true;
}
if (p.Compareable(root.value) && p.CompareTo(root.value) > 0 && root.leftchild == null)
{
root.leftchild = new BinaryTreeNode(p);
return true;
}
if (p.Compareable(root.value) && p.CompareTo(root.value) > 0 && root.rightchild == null && !root.leftchild.value.Compareable(p))
{
root.rightchild = new BinaryTreeNode(p);
return true;
}
return false;
}
class MyComp : IComparer<Pair>
{
public int Compare(Pair x, Pair y)
{
if (x.Compareable(y)) return x.CompareTo(y);
return (x.x + x.y) - (y.x + y.y);
}
}
static void Main(string[] args)
{
List<Pair> list = new List<Pair>()
{
new Pair(0, 1),
new Pair(1, 0),
new Pair(2, 3),
new Pair(3, 3),
new Pair(3, 2),
new Pair(2, 1),
new Pair(1, 1)
};
list.Sort(new MyComp());
foreach (var item in list)
Console.WriteLine(item);
var root = new BinaryTreeNode(-1, -1);
foreach (var item in list)
{
TryInsertToTree(root, item);
}
Console.WriteLine(root);
}
}
}
排序规则，如果“可排序”按照你的规则排序
如果不可排序，按照x+y的和排序
(1,0)
(0,1)
(1,1)
(2,1)
(3,2)
(2,3)
(3,3) //这是排序的结果
((null)(1,0)(null))(-1,-1)(((((null)(3,2)(null))(2,1)(((null)(3,3)(null))(2,3)(null)))(1,1)(null))(0,1)(null))
Press any key to continue . . .