Question

任何二叉树都可以采用顺序存储结构

Answer 1

问：任何二叉树都可以采用顺序存储结构

答：您好亲亲，不是所有的二叉树都可以采用顺序存储结构。

答：顺序存储结构是指将数据元素按照线性顺序存储在一段连续的存储空间中。对于二叉树而言，它的节点包含两个子节点，因此无论是采用数组还是链表存储，都需要额外的空间来存储它的左右子节点。如果采用数组存储，需要在数组中占用两个位置来存储它的左右子节点，如果某个节点没有子节点，那么这个位置就会浪费掉，因此对于稀疏的二叉树而言，采用顺序存储结构会造成空间的浪费；而对于非完全二叉树而言，采用顺序存储结构则无法准确地表示出二叉树的结构，因此不太适合使用。

答：相对于顺序存储结构，链式存储结构则可以更好地表示出二叉树的结构，因为每个节点都包含两个指针指向它的左右子节点，不会浪费存储空间，也可以表示出任意结构的二叉树。因此，链式存储结构是更为常用的二叉树存储方式。

问：5设二叉树的二叉链表结点类Node定义如下:public class Node {public Object data;public Node Ichild,rchild;public Node() { data = null; child=rchild=null; }其中data、lchild、rchild分别为数据域、左孩子链接域、右孩子链接域。二叉链表类BTree定义如下:public class BTree {private Node root;public BTree0 {root=null;}}编写BTree类中的countD0方法，统计二叉树中叶子结点个数。(10.0分)

问：4 设树采用孩子兄弟表示法，其结点类Node定义如下: public class Node {public Object data;public Node firstChild,nextSibling;public Node() { data = null; firstChild = nextSibling = null; }其中data、firstChild、nextSibling分别为数据域、第一个孩子链接域、下一个兄弟链接域树的类Tree定义如下:public class Tree {private Node root;public Tree(){root =null;}}编写Tree类中的postOrder方法，实现树的后根遍历，其中的访问操作调用visit(data)。(10.0分)

答：亲亲，countD0方法的实现步骤如下：判断根节点是否为空，如果为空，则返回0。如果根节点的左右孩子链接域都为空，说明根节点是叶子结点，返回1。递归地对左子树和右子树进行countD0操作，并将结果相加。返回总叶子结点个数。

问：都要编程过程

答：5 public class BTree { private Node root; public BTree() { root = null; }// 定义一个方法，计算二叉树中叶子结点的个数public int countD0(Node node) { if (node == null) { // 如果节点为空，则返回0 return 0; } else if (node.lchild == null && node.rchild == null) { // 如果节点是叶子结点，则返回1 return 1; } else { // 否则递归计算该节点的左右子节点的叶子结点个数之和 return countD0(node.lchild) + countD0(node.rchild); }}

答：4. public void postOrder(Node node) { if (node != null) { postOrder(node.firstChild); postOrder(node.nextSibling); visit(node.data); }}public void postOrderTraversal() { postOrder(root);}private void visit(Object data) { System.out.print(data + " ");}

答：//假设我们有一棵树，根结点为A，它有两个孩子结点B和C//B又有两个孩子结点D和E，C有一个孩子结点F//那么采用孩子兄弟表示法存储这棵树的结构如下：//A->B->D->E->C->F//其中“->”表示链接，即A的第一个孩子结点是B，B的第一个孩子结点是D，B的下一个兄弟结点是E，依此类推//如果我们对这棵树进行后根遍历，应该输出的结果为D E B F C A，即先遍历B的孩子结点D和E，再遍历B本身，然后遍历C的孩子结点F，最后遍历A//可以通过调用postOrderTraversal()方法实现这个遍历操作。

问：1设二叉树的二叉链表结点类Node定义如下:public class Node {public Object data;public Node Ichild, rchild;public Node() { data = null; Ichild = rchild = null; }}其中data、lchild、rchild分别为数据域、左孩子链接域、右孩子链接域。二叉链表类BTree定义如下:public class BTree {private Node root;public BTree(){ root=null}编写BTree类中的levelOrder方法，实现二叉树的按层次遍历，其中的访问操作调用visit(data)可直接使用队列类Queue，其入队和出队操作分别用in和out方法，判断队列为空用isEmpty方法。(10.0分)

问：2 设二叉树的二叉链表结点类Node定义如下: public class Node {public Object data;public Node lchild, rchild;public Node(){ data = null; Ichild =rchild =null;}}其中data、Ichild、rchild分别为数据域、左孩子链接域、右孩子链接域。二叉链表类BTree定义如下:public class BTree {private Node root;public BTree(){ root = null;}编写BTree类中的countD1方法，统计二叉树中度为1的结点个数(10.0分)

问：4 设二叉树的二叉链表结点类Node定义如下: public class Node {public Object data;public Node lchild, rchild;public Node() { data = null; lchild = rchild = null; }}其中data、lchild、rchild分别为数据域、左孩子链接域、右孩子链接域。二叉链表类BTree定义如下:public class BTree {private Node root;public BTree(){root =null;}编写BTree类中的swap方法，将每一个结点的左孩子、右孩子交换位置。(10.0分)

答：public void levelOrder() { if (root == null) { return; } Queue queue = new Queue>(); queue.in(root); while (!queue.isEmpty()) { Node node = queue.out(); visit(node.data); if (node.lchild != null) { queue.in(node.lchild); } if (node.rchild != null) { queue.in(node.rchild); } }} 其中，队列queue用来存放待遍历的结点。首先把根结点root入队，然后在循环中不断出队结点，访问它的数据域，如果它有左右孩子，则把左右孩子分别入队。这样就可以按层次遍历结点了。

答：统计二叉树中度为1的结点个数 */public int countD1() { return countD1(root);}private int countD1(Node node) { if (node == null) { // 判断当前结点是否为空 return 0; }if (node.lchild == null && node.rchild == null) { // 判断是否为叶子结点 return 0;}int count = 0;if (node.lchild != null && node.rchild == null) { // 判断是否只有左孩子 count = 1;} else if (node.lchild == null && node.rchild != null) { // 判断是否只有右孩子 count = 1;}// 递归遍历左右子树return count + countD1(node.lchild) + countD1(node.rchild);}

答：4. public void swap() { swap(root);}private void swap(Node node) { if (node == null) { return; } // 交换左右子树 Node temp = node.lchild; node.lchild = node.rchild; node.rchild = temp; // 递归交换左右子树 swap(node.lchild); swap(node.rchild);}

答：亲亲，要是还有问题需要咨询我可以购买以下这个套餐，我已经打了折去掉了10块钱啦，只需要9.9元就可以继续向我咨询哈