二叉树遍历 实验报告

二叉树遍历实验报告完全二叉树：若设二叉树的深度为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(),

list);

preorder(node.getRightNode(),

list);

}

}

public

void

midorder(Node

node,List<String>

list)

{

//中序

if(node!=null)

{

midorder(node.getLeftNode(),

list);

list.add(node.getValue());

midorder(node.getRightNode()

,

list);

}

}

public

void

postorder(Node

node,List<String>

list)

{

//后序

if(node!=null)

{

postorder(node.getLeftNode(),

list);

postorder(node.getRightNode(),

list);

list.add(node.getValue());

}

}创建测试类（Test）package

NO1;

import

java.util.List;

import

java.util.ArrayList;

public

class

Test

{

public

static

void

main(String[]

args)

{

//

TODO

Auto-generated

method

stub

String

a[]=

{"A","B","C","D","E","F","G","H","I","J"};

BinaryTree

tree1=new

BinaryTree();

tree1.addNodes(a);

List<String>

list1=new

ArrayList<>();

List<String>

list2=new

ArrayList<>();

List<String>

list3=new

ArrayList<>();

tree1.preorder(tree1.getRoot(),

list1);

tree1.midorder(tree1.getRoot(),

list2);

tree1.postorder(tree1.getRoot(),

list3);

System.out.println("