请用c#语言生成一棵树(二叉链表)。 并判断该树是否为对称二叉树。(提示:判断二叉树是否对称事实上是其左右子树是否对称同构的判断。而对左右子树是否对称同构的判断又依赖于左子树的左右子树分别和右子树的右左子树是否对称的判断。可先设计一个算法用来判断两个二叉树是否同构对称。可用递归法。
时间: 2023-11-06 15:30:48 浏览: 77
以下是使用C#语言生成二叉链表并判断是否为对称二叉树的示例代码:
```csharp
using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class BinaryTree {
private TreeNode root;
public BinaryTree(int val) {
root = new TreeNode(val);
}
public void AddNode(int val) {
TreeNode node = new TreeNode(val);
if (root == null) {
root = node;
return;
}
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Count != 0) {
TreeNode current = queue.Dequeue();
if (current.left == null) {
current.left = node;
return;
} else {
queue.Enqueue(current.left);
}
if (current.right == null) {
current.right = node;
return;
} else {
queue.Enqueue(current.right);
}
}
}
public bool IsSymmetric() {
return IsSymmetric(root, root);
}
private bool IsSymmetric(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null) {
return false;
}
return left.val == right.val && IsSymmetric(left.left, right.right) && IsSymmetric(left.right, right.left);
}
}
public class Program {
public static void Main() {
BinaryTree tree = new BinaryTree(1);
tree.AddNode(2);
tree.AddNode(2);
tree.AddNode(3);
tree.AddNode(4);
tree.AddNode(4);
tree.AddNode(3);
Console.WriteLine(tree.IsSymmetric()); // Output: True
}
}
```
上面代码中,我们首先定义一个二叉树的数据结构`TreeNode`,然后定义一个`BinaryTree`类来实现二叉树的生成和判断是否对称。在`BinaryTree`类中,我们实现了`AddNode`方法来向二叉树中添加节点,使用了队列来实现二叉树的广度优先遍历。
在判断是否对称的方法`IsSymmetric`中,我们定义了一个递归函数`IsSymmetric`来判断左右子树是否对称同构。如果左右子树都为空,则它们对称;如果只有一个为空,则它们不对称;如果两个都不为空,则需要判断它们的值是否相等,并递归判断左子树的左子树和右子树的右子树,以及左子树的右子树和右子树的左子树是否对称同构。
最后我们在`Main`方法中生成一个二叉树并测试它是否对称,输出结果为`True`。
阅读全文