完全二叉树的构建及三种遍历

论坛 期权论坛 编程之家     
选择匿名的用户   2021-6-2 20:56   2083   0

package cn.demo;
import java.util.LinkedList;
import java.util.List;

//二叉树的定义,孩子表示法
public class BinTreeTraverse2 {

//定义一个数字,将数组转换为完全二叉树
private int[] array={1,2,3,4,5,6,7,8,9};

//定义一个存放节点的list集合
private List<Node>nodeList=null;

//节点的定义
class Node{
Node leftChild;
Node rightChild;
int data;
Node(int newData){
leftChild=null;
rightChild=null;
data=newData;
}
}
public List<Node> getNodeList() {
return nodeList;
}
public void createBinTree(){
nodeList=new LinkedList<Node>();

    //将数组的值,转换成树中节点的值
for(int parentIndex=0;parentIndex < array.length;parentIndex++){
nodeList.add(new Node(array[parentIndex]));
}
for(int parentIndex=0;parentIndex<array.length/2-1;parentIndex++){
nodeList.get(parentIndex).leftChild=nodeList.get(parentIndex*2+1);
nodeList.get(parentIndex).rightChild=nodeList.get(parentIndex*2+2);
}
int lastParentIndex=array.length/2-1;
nodeList.get(lastParentIndex).leftChild=nodeList.get(lastParentIndex*2+1);
if(array.length%2==1){
nodeList.get(lastParentIndex).rightChild=nodeList.get(lastParentIndex*2+2);
}

}

//二叉树的前序遍历
public void preOrderTraverse(Node node){
if(node==null)
return;
System.out.print(node.data+" ");
preOrderTraverse(node.leftChild);
preOrderTraverse(node.rightChild);
}

//二叉树的中序遍历
public void preOrderTraverse(Node node){
if(node==null)
return;

preOrderTraverse(node.leftChild);

   System.out.print(node.data+" ");
preOrderTraverse(node.rightChild);
}

//二叉树的后序遍历
public void preOrderTraverse(Node node){
if(node==null)
return;

preOrderTraverse(node.leftChild);
preOrderTraverse(node.rightChild);

   System.out.print(node.data+" ");
}
}

转载于:https://www.cnblogs.com/2nao/p/6416738.html

分享到 :
0 人收藏
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:3875789
帖子:775174
精华:0
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP