已知二叉树t,分别采用顺序存储结构、二叉链表存储结构实现求二叉树的深度,并对二叉树分别进行中序遍历。
时间: 2023-04-17 12:01:19 浏览: 197
顺序存储结构实现求二叉树的深度:
假设二叉树t的顺序存储结构为数组a,根节点为a[1],则可以通过以下公式计算二叉树的深度:
depth = log2(n+1)
其中,n为二叉树中节点的个数。具体实现可以参考以下代码:
int getDepthByArray(int[] a) {
int n = a.length - 1; // n为节点个数
int depth = (int) (Math.log(n + 1) / Math.log(2)); // 计算深度
return depth;
}
二叉链表存储结构实现求二叉树的深度:
假设二叉树t的二叉链表存储结构为节点类Node,根节点为root,则可以通过递归实现求二叉树的深度:
int getDepthByLinkedList(Node root) {
if (root == null) {
return ;
}
int leftDepth = getDepthByLinkedList(root.left); // 左子树深度
int rightDepth = getDepthByLinkedList(root.right); // 右子树深度
return Math.max(leftDepth, rightDepth) + 1; // 返回深度
}
二叉树的中序遍历:
假设二叉树t的二叉链表存储结构为节点类Node,根节点为root,则可以通过递归实现二叉树的中序遍历:
void inorderTraversal(Node root) {
if (root == null) {
return;
}
inorderTraversal(root.left); // 遍历左子树
System.out.print(root.val + " "); // 输出当前节点的值
inorderTraversal(root.right); // 遍历右子树
}
顺序存储结构的二叉树中序遍历需要转换为二叉链表存储结构后再进行遍历。
阅读全文