用java语言。 使用二叉树表示法作为树的存储结构,输入树中的顶点值及对应的关系创建树后,求树中结点的个数、求树的深度、求结点的孩 个数、实现树的先根、后根和层次遍历。
时间: 2023-02-09 17:09:08 浏览: 62
求树中结点的个数
可以使用递归的方式遍历整棵树,在遍历的过程中统计结点的个数。例如:
```
public int getSize(Node root) {
if (root == null) {
return 0;
}
return 1 + getSize(root.left) + getSize(root.right);
}
```
求树的深度
同样可以使用递归的方式遍历整棵树,在遍历的过程中统计树的深度。例如:
```
public int getDepth(Node root) {
if (root == null) {
return 0;
}
int leftDepth = getDepth(root.left);
int rightDepth = getDepth(root.right);
return 1 + Math.max(leftDepth, rightDepth);
}
```
求结点的孩子个数
可以在二叉树的结点类中增加一个字段,用来记录当前结点的孩子个数。例如:
```
class Node {
int val;
Node left;
Node right;
int childrenCount; // 新增的字段,用来记录孩子个数
}
```
在创建树的过程中,每次添加一个孩子结点时,将当前结点的孩子个数加 1 即可。
实现树的先根遍历
树的先根遍历也叫先序遍历,顾名思义就是先访问根结点,再访问左子树,最后访问右子树。可以使用递归的方式实现。例如:
```
public void preOrder(Node root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
```
实现树的后根遍历
树