用java语言。该问题是关于树的存储和操作实现。
使用孩⼦兄弟表⽰法作为树的存储结构，输入树中的顶点值及对应的关系创建树后，求树中结点的个数、求树的深度、求结点的children个数、实现树的先根、后根和层次遍历。
1、求树中结点的个数：
可以使用递归来求树中结点的个数。具体来说，可以递归遍历整棵树，对于每一个遍历到的结点，都将结果加1：
public int getNodeCount(CSBTreeNode root) {
if (root == null) {
return 0;
}
int count = 1;
CSBTreeNode child = root.firstChild;
while (child != null) {
count += getNodeCount(child);
child = child.nextSibling;
}
return count;
}
2、
求树的深度可以使用递归来实现。具体来说，对于一棵树的根结点，可以递归地求出它的每一个子结点的深度，然后取最大值加1作为当前结点的深度：
public int getDepth(CSBTreeNode root) {
if (root == null) {
return 0;
}
int depth = 1;
CSBTreeNode child = root.firstChild;
while (child != null) {
depth = Math.max(depth, getDepth(child) + 1);
child = child.nextSibling;
}
return depth;
}
3、
求结点的children个数：
可以使用递归来求结点的children个数。具体来说，可以递归遍历结点的每一个子结点，对于每一个遍历到的子结点，都将结果加1：
public int getChildCount(CSBTreeNode node) {
if (node == null || node.firstChild == null) {
return 0;
}
int count = 1;
CSBTreeNode child = node.firstChild.nextSibling;
while (child != null) {
count++;
child = child.nextSibling;
}
return count;
}
4、
实现树的先根遍历：
先根遍历是指先遍历根结点，然后递归遍历每一个子结点。可以使用递归来实现先根遍历：
public void preOrderTraversal(CSBTreeNode root) {
if (root == null) {
return;
}
System.out.println(root.val);
CSBTreeNode child = root.firstChild;
while (child != null) {
preOrderTraversal(child);
child = child.nextSibling;
}
}
5、
实现树的后根遍历：
后根遍历是指先递归遍历每一个子结点，然后遍历根结点。可以使用递归来实现后根遍历：
public void postOrderTraversal(CSBTreeNode root) {
if (root == null) {
return;
}
CSBTreeNode child = root.firstChild;
while (child != null) {
postOrderTraversal(child);
child = child.nextSibling;
}
System.out.println(root.val);
}
6、
实现树的层次遍历：
层次遍历是指按照树的层次依次遍历每一个结点。可以使用队列来实现层次遍历。首先将根结点入队，然后只要队列不为空，就依次取出队列中的结点，并将它的子结点入队：
public void levelOrderTraversal(CSBTreeNode root) {
if (root == null) {
return;
}
Queue<CSBTreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
CSBTreeNode node = queue.poll();
System.out.println(node.val);
CSBTreeNode child = node.firstChild;
while (child != null) {
queue.offer(child);
child = child.nextSibling;
}
}
}
仅供参考，望采纳，谢谢。
我写了一段使用孩子兄弟表示法存储树并实现上述操作的 Java 代码，你试试看：
class Node {
int val;
Node firstChild;
Node nextSibling;
public Node(int val) {
this.val = val;
firstChild = null;
nextSibling = null;
}
}
class Tree {
Node root;
public Tree(Node root) {
this.root = root;
}
// 计算树中结点的个数
public int countNodes() {
return countNodes(root);
}
private int countNodes(Node node) {
if (node == null)
return 0;
int count = 1;
Node child = node.firstChild;
while (child != null) {
count += countNodes(child);
child = child.nextSibling;
}
return count;
}
// 计算树的深度
public int getDepth() {
return getDepth(root);
}
private int getDepth(Node node) {
if (node == null)
return 0;
int depth = 0;
Node child = node.firstChild;
while (child != null) {
depth = Math.max(depth, getDepth(child));
child = child.nextSibling;
}
return depth + 1;
}
// 计算结点的 children 个数
public int countChildren(Node node) {
int count = 0;
Node child = node.firstChild;
while (child != null) {
count++;
child = child.nextSibling;
}
return count;
}
// 实现树的先根遍历
public void preOrderTraversal() {
preOrderTraversal(root);
}
private void preOrderTraversal(Node node) {
if (node == null)
return;
System.out.print(node.val + " ");
Node child = node.firstChild;
while (child != null) {
preOrderTraversal(child);
child = child.nextSibling;
}
}
// 实现树的后根遍历
public void postOrderTraversal() {
postOrderTraversal(root);
}
private void postOrderTraversal(Node node) {
if (node == null)
return;
Node child = node.firstChild;
while (child != null) {
postOrderTraversal(child);
child = child.nextSibling;
}
System.out.print(node.val + " ");
}
// 实现树的层次遍历
public void levelOrderTraversal() {
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
System.out.print(node.val + " ");
Node child = node.firstChild;
while (child != null) {
queue.offer(child);
child = child.nextSibling;
}
}
}
}
public class Main {
public static void main(String[] args) {
// 创建树
Node a = new Node('A');
Node b = new Node('B');
Node c = new Node('C');
Node d = new Node('D');
Node e = new Node('E');
Node f = new Node('F');
Node g = new Node('G');
a.firstChild = b;
b.nextSibling = c;
b.firstChild = d;
d.nextSibling = e;
c.firstChild = f;
f.nextSibling = g;
Tree tree = new Tree(a);
// 测试
System.out.println("结点个数：" + tree.countNodes());
System.out.println("树的深度：" + tree.getDepth());
System.out.println("D 结点的 children 个数：" + tree.countChildren(d));
System.out.print("先根遍历：");
tree.preOrderTraversal();
System.out.println();
System.out.print("后根遍历：");
tree.postOrderTraversal();
System.out.println();
System.out.print("层次遍历：");
tree.levelOrderTraversal();
}
计算树中结点的个数
首先定义一个计数器count，初始值为0。然后遍历树中所有的结点，每遍历到一个结点，就将count加1。最终得到的count即为树中结点的个数。
计算树的深度
首先定义一个计数器depth，初始值为0。然后遍历树中所有的结点，每遍历到一个结点，就将该结点的深度与depth进行比较，取较大值并赋值给depth。最终得到的depth即为树的深度。
计算结点的children个数
首先定义一个计数器children，初始值为0。然后遍历树中所有的结点，每遍历到一个结点，就将该结点的children个数加到children上。最终得到的children即为树中所有结点的children个数之和。
实现树的先根遍历
先根遍历需要使用栈进行实现。首先将根结点压入栈中，然后取出栈顶结点并访问。接着将该结点的所有子结点从左到右压入栈中，再取出栈顶结点并访问，直到栈为空。
实现树的后根遍历
后根遍历需要使用栈进行实现。首先将根结点压入栈中，然后取出栈顶结点的所有子结点从左到右压入栈中，直到栈为空。每次从栈中取出结点时，都将该结点的值记录到结果数组中，最后将结果数组倒序输出即为后根遍历的结果。
实现树的层次遍历
层次遍历需要使用队列进行实现。首先将根结点入队，然后每次从队列中取出一个结点并访问。接着将该结点的所有子结点从左到右依次入队，直到队列为空。
所有子结点从左到右压入栈中，直到栈为空。每次从栈中取出结点时，都将该结点的值记录到结果数组中，最后将结果数组倒序输出即为后根遍历的结果。
实现树的层次遍历
层次遍历需要使用队列进行实现。首先将根结点入队，然后每次从队列中取出一个结点并访问。接着将该结点的所有子结点从左到右依次入队，直到队列为空。
下面是一个例子，展示了如何使用孩子兄弟表示法来实现树的存储和操作：
class TreeNode {
int val;
TreeNode parent;
TreeNode firstChild;
TreeNode nextSibling;
public TreeNode(int val) {
this.val = val;
this.parent = null;
this.firstChild = null;
this.nextSibling = null;
}
}
class Tree {
TreeNode root;
public Tree(int val) {
this.root = new TreeNode(val);
}
// 返回树中节点的个数
public int getNodeCount() {
return getNodeCount(root);
}
private int getNodeCount(TreeNode node) {
if (node == null) {
return 0;
}
int count = 1;
TreeNode child = node.firstChild;
while (child != null) {
count += getNodeCount(child);
child = child.nextSibling;
}
return count;
}
// 返回树的深度
public int getDepth() {
return getDepth(root);
}
private int getDepth(TreeNode node) {
if (node == null) {
return 0;
}
int depth = 0;
TreeNode child = node.firstChild;
while (child != null) {
depth = Math.max(depth, getDepth(child));
child = child.nextSibling;
}
return depth + 1;
}
// 返回结点的 children 个数
public int getChildCount(TreeNode node) {
if (node == null || node.firstChild == null) {
return 0;
}
int count = 1;
TreeNode child = node.firstChild.nextSibling;
while (child != null) {
count++;
child = child.nextSibling;
}
return count;
}
// 先根遍历
public void preOrder(TreeNode node) {
if (node == null) {
return;
}
System.out.println(node.val);
TreeNode child = node.firstChild;
while (child != null) {
preOrder(child);
child = child.nextSibling;
}
}
// 后根遍历
public void postOrder(TreeNode node) {
if (node == null) {
return;
}
TreeNode child = node.firstChild;
while (child != null) {
postOrder(child);
child = child.nextSibling;
}
System.out.println(node.val);
}
// 层次遍历
public void levelOrder() {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.println(node.val);
TreeNode child = node.firstChild;
while (child != null) {
queue.offer(child);
child = child.nextSibling;
}
}
}
}
为了使用孩子兄弟表示法来存储树，您需要定义一个结构体或类来表示每个结点。该结构体应该包含以下几个字段：
下面是一个示例实现：
public class TreeNode {
int value;
TreeNode firstChild;
TreeNode nextSibling;
public TreeNode(int value) {
this.value = value;
}
}
下面是如何实现上述操作的一些提示：
求树中结点的个数：您可以使用递归来遍历树中的所有结点，并统计结点的数量。
求树的深度：您可以递归地遍历树的所有子树，并求出每个子树的深度。然后，取所有子树的最大深度并将其加 1（用于计算当前结点的深度）。
求结点的 children 个数：您可以使用递归来遍历该结点的所有孩子，并统计孩子的数量。
实现树的先根、后根和层次遍历：您可以使用递归来实现先根遍历和后根遍历。对于层次遍历，您可以使用队列来存储每层的结点，然后依次遍历每层的结点。
下面是一个示例实现，该实现使用孩子兄弟表示法存储树，并实现了计算树中结点的个数、求树的深度、求结点的 children 个数、实现树的先根、后根和层次遍历的功能。
import java.util.LinkedList;
import java.util.Queue;
public class Tree {
private TreeNode root;
public Tree(int value) {
root = new TreeNode(value);
}
// 计算树中结点的个数
public int countNodes() {
return countNodes(root);
}
private int countNodes(TreeNode node) {
if (node == null) {
return 0;
}
int count = 1;
for (TreeNode child = node.firstChild; child != null; child = child.nextSibling) {
count += countNodes(child);
}
return count;
}
// 求树的深度
public int getDepth() {
return getDepth(root);
}
private int getDepth(TreeNode node) {
if (node == null) {
return 0;
}
int maxDepth = 0;
for (TreeNode child = node.firstChild; child != null; child = child.nextSibling) {
int depth = getDepth(child);
if (depth > maxDepth) {
maxDepth = depth;
}
}
return maxDepth + 1;
}
// 求结点的 children 个数
public int countChildren(int value) {
TreeNode node = findNode(value, root);
if (node == null) {
return 0;
}
int count = 0;
for (TreeNode child = node.firstChild; child != null; child = child.nextSibling) {
count++;
}
return count;
}
// 实现树的先根遍历
public void preOrderTraversal() {
preOrderTraversal(root);
}
private void preOrderTraversal(TreeNode node) {
if (node == null) {
return;
}
System.out.print(node.value + " ");
for (TreeNode child = node.firstChild; child != null; child = child.nextSibling) {
preOrderTraversal(child);
}
}
// 实现树的后根遍历
public void postOrderTraversal() {
postOrderTraversal(root);
}
private void postOrderTraversal(TreeNode node) {
if (node == null) {
return;
}
for (TreeNode child = node.firstChild; child != null; child = child.nextSibling) {
postOrderTraversal(child);
}
System.out.print(node.value + " ");
}
// 实现树的层次遍历
public void levelOrderTraversal() {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.value + " ");
for (TreeNode child = node.firstChild; child != null; child = child.nextSibling) {
queue.add(child);
}
}
}
private TreeNode findNode(int value, TreeNode node) {
if (node == null || node.value == value) {
return node;
}
for (TreeNode child = node.firstChild; child != null; child = child.nextSibling) {
TreeNode found = findNode(value, child);
if (found != null) {
return found;
}
}
return null;
}
}
可以使用以下步骤：
定义一个类来表示树中的节点，该类应包含节点的值、父节点的引用、左儿子的引用和右哥哥的引用。这样就可以使用孩子兄弟表示法来存储树。
实现一个方法，该方法接受节点的值和父节点的引用，并创建一个新节点。
实现一个方法，该方法实现一个方法，该方法可以计算树中节点的个数。可以使用递归的方法来实现，先求出当前节点的子树中节点的个数，然后加上1（当前节点本身）即为树中节点的总数。
实现一个方法，该方法可以计算树的深度。可以使用递归的方法来实现，对于当前节点的每个子节点，递归调用该方法求出它们的子树的深度，然后取最大值加1即为当前节点的子树的深度。
实现一个方法，该方法可以计算节点的子节点个数。可以使用递归的方法来实现，对于当前节点的每个子节点，递归调用该方法求出它们的子节点个数，然后累加起来即为当前节点的子节点个数。
实现树的先根遍历，可以使用递归的方法，先访问当前节点，然后依次访问它的左儿子和右儿子。
实现树的后根遍历，可以使用递归的方法，先依次访问当前先依次访问当前节点的左儿子和右儿子，然后访问当前节点。
实现树的层次遍历，可以使用队列实现树的层次遍历，可以使用队列来实现。首先将根节点入队，然后进行如下操作：从队头取出一个节点，访问该节点，然后将它的左儿子和右儿子依次入队。重复这个过程，直到队列为空。
参考下我的写的：如果对你有所帮助，还请采纳。
//创建HeroNode结点
@Data
class HeroNode{
private int no;
private String name;
private HeroNode left;//默认为null
private HeroNode right;//默认为null
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + "]";
}
//前序遍历
public void preOrder(){
System.out.println(this);//先输出父结点(谁调用这个方法，谁就是this)
//递归向左子树前序遍历
if(this.left!=null){
this.left.preOrder();
}
//递归向右子树前序遍历
if(this.right!=null){
this.right.preOrder();
}
}
//中序遍历
public void infixOrder(){
//递归向左子树中序遍历
if(this.left!=null){
this.left.infixOrder();
}
//输出父结点
System.out.println(this);
//递归向右子树中序遍历
if(this.right!=null){
this.right.infixOrder();
}
}
//后序遍历
public void postOrder(){
//递归向左子树后序遍历
if(this.left!=null){
this.left.postOrder();
}
//递归向右子树后序遍历
if(this.right!=null){
this.right.postOrder();
}
//输出父结点
System.out.println(this);
}
}
写个main函数测试：
public static void main(String[] args) {
//先需要创建一颗二叉树
BinaryTree binaryTree=new BinaryTree();
//创建需要的结点
HeroNode root=new HeroNode(1,"宋江");
HeroNode node2=new HeroNode(2,"吴用");
HeroNode node3=new HeroNode(3,"卢俊义");
HeroNode node4=new HeroNode(4,"林冲");
HeroNode node5=new HeroNode(5,"武松");
HeroNode node6=new HeroNode(6,"鲁智深");
HeroNode node7=new HeroNode(7,"杨志");
//说明，我们先手动创建该二叉树，后面我们学习递归的方式创建而常数
root.setLeft(node2);
root.setRight(node3);
node2.setLeft(node4);
node2.setRight(node5);
node3.setLeft(node6);
node3.setRight(node7);
binaryTree.setRoot(root);
//测试：
System.out.println("前序遍历");//1,2,4,5,3,6,7
binaryTree.preOrder();
System.out.println("中序遍历");//4,2,5,1,6,3,7
binaryTree.infixOrder();
System.out.println("后序遍历");//4,5,2,6,7,3,1
binaryTree.postOrder();
}
参考该实例【java实现二叉树的（查找），（树的深度），（叶的个数），（结点个数）】，链接：https://blog.csdn.net/asfsaf21/article/details/112545816