二叉树遍历 实验报告.docx

二叉树遍历实验报告

完全二叉树：若设二叉树的深度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。

特点：1）所有的叶节点都出现在最后一层或倒数第二层

2）任一节点，其左子树的最大层数和右子树最大层数相同或比其大一层。

3）最后一个叶节点为节点长度/2（第一个节点记作0，所以向下取整，记作i），叶节点的左子树根节点为2*i+1,若存在右子树，则右子树根节点为2*i+2。

完全二叉树

代码：

创建节点类（Node）

package?NO1;

//创建节点类

public?class?Node?{

????private?String?value;

????private?Node?leftNode;

????private?Node?rightNode;

????public?Node(String?value)?{

????????this.value=value;

????}

????public?Node()?{}

????public?String?getValue()?{

????????return?value;

????}

????public?void?setValue(String?value)?{

????????this.value?=?value;

????}

????public?Node?getLeftNode()?{

????????return?leftNode;

????}

????public?void?setLeftNode(Node?leftNode)?{

????????this.leftNode?=?leftNode;

????}

????public?Node?getRightNode()?{

????????return?rightNode;

????}

????public?void?setRightNode(Node?rightNode)?{

????????this.rightNode?=?rightNode;

????}

}

创建二叉树类

package?NO1;

import?java.util.List;

import?java.util.ArrayList;

//完全二叉树类

public?class?BinaryTree?{

????private?Node?root;?//根节点

????public?BinaryTree(String?value)?{

????????Node?node=new?Node(value);

????????root=node;

????}

????public?BinaryTree()?{}

????public?Node?getRoot()?{

????????return?root;

????}

????public?void?setRoot(Node?root)?{

????????this.root?=?root;

????}

}

添加完全二叉树节点方法（addNodes）

public?void?addNodes(String?a[])?{

????????List<Node>?list=new?ArrayList<>();

????????for(int?i=0;i<a.length;i++)

????????{

????????????Node?node=new?Node(a[i]);

????????????list.add(node);

????????}

????????root=list.get(0);

????????for(int?i=0;i<a.length/2;i++)

????????{

????????????list.get(i).setLeftNode(list.get(2*i+1));

????????????if(2*i+2<=a.length-1)

????????????{

????????????????list.get(i).setRightNode(list.get(2*i+2));

????????????}

????????}

????}

添加遍历方法

public?void?preorder(Node?node,List<String>?list)?{??//前序排列

????????if(node!=null)

????????{

????????????list.add(node.getValue());

????????????preorder(node.getLeftNode(),