树是有穷节点的组,其中有一个节点作为根,根下面的其余节点以层次化方式组织。引用其下节点的节点是父节点,类似,由上层节点引用的节点是孩子节点。没有孩子的节点是叶子节点。一个节点可能同时是父节点和子节点。
一个父节点可以引用所需的多个孩子节点。在很多情况下,父节点至多只能引用两个孩子节点,基于这种节点的树称为二叉树。
public class TestBinTree {
public List<Node> createBinTree(int[] array){
List<Node> nodeList = new LinkedList<Node>();
for (int i = 0; i < array.length; i++) {
nodeList.add(new Node(array[i]));
}
for (int i = 0; i < array.length/2-1; i++) {
nodeList.get(i).leftChild = nodeList.get(i*2+1);
nodeList.get(i).rightChild = nodeList.get(i*2+2);
}
int lastIndex = array.length/2-1;
nodeList.get(lastIndex).leftChild = nodeList.get(lastIndex*2+1);
if(array.length%2==1){
nodeList.get(lastIndex).rightChild = nodeList.get(lastIndex*2+2);
}
return nodeList;
}
public List<Node> insert(int obj,List<Node> nodeList){
Node node = new Node(obj);
if(nodeList.size()!=0){
int lastIndex = nodeList.size()/2-1;
if(lastIndex<0){
nodeList.get(0).leftChild = node;
}else{
Node rightChild = nodeList.get(lastIndex).rightChild;
if(rightChild==null){
nodeList.get(lastIndex).rightChild = node;
}else{
nodeList.get(lastIndex+1).leftChild = node;
}
}
}
nodeList.add(node);
return nodeList;
}
public void preOrder(Node node){
if(node==null)
return;
System.out.print(node.data+"\t");
preOrder(node.leftChild);
preOrder(node.rightChild);
}
public void inOrder(Node node){
if(node==null)
return;
inOrder(node.leftChild);
System.out.print(node.data+"\t");
inOrder(node.rightChild);
}
public void postOrder(Node node){
if(node==null)
return;
postOrder(node.leftChild);
postOrder(node.rightChild);
System.out.print(node.data+"\t");
}
public static void main(String[] args) {
TestBinTree testBinTree = new TestBinTree();
int[] array = {1,2,3,4,5,6,7,8,9};
List<Node> nodeList = new LinkedList<Node>();
for (int i = 0; i < array.length; i++) {
nodeList = testBinTree.insert(array[i],nodeList);
}
List<Node> binTree = testBinTree.createBinTree(array);
Node root = binTree.get(0);
// Node root = nodeList.get(0);
System.out.println("先序遍历:");
testBinTree.preOrder(root);
System.out.println();
System.out.println("中序遍历:");
testBinTree.inOrder(root);
System.out.println();
System.out.println("后序遍历:");
testBinTree.postOrder(root);
System.out.println();
}
}
class Node{
Node leftChild;
Node rightChild;
int data;
public Node(int data){
this.data = data;
}
}
分享到:
相关推荐
实现由先序、中序序列构造二叉树,由后序、中序序列构造二叉树,广度优先遍历以root为根结点的子树,中序遍历(递归,非递归)以root为根结点的子树
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
二叉树的构建及遍历操作,使用链表的形式构建二叉树并进行前序、中序、后序遍历操作
利用递归方式完成二叉树的简单创建以及遍历。
给出二叉树的中序遍历序列和后序遍历序列,编程还原该二叉树。 输入: 第1行为二叉树的中序遍历序列 第2行为二叉树的后序遍历序列 输出: 二叉树的按层遍历序列
如果给出了遍历二叉树的前序序列和中序序列,则可以构造出唯一的一棵二叉树。试编写实现上述功能的程序。 [基本要求] 已知一棵二叉树的前序和中序序列,试设计完成下列任务的一个算法: (1)构造一棵二叉树...
实现二叉树的遍历操作,属于数据结构基础算法,代码能够顺利运行,运行环境是ColdBlick。
线索化二叉树之先序,中序,后序线索建树,先序,后序,中序遍历
二叉树、二叉搜索树的构建,前序、中序、后序的 递归和非递归遍历;前序中序序列构建二叉树……
给定先序中序序列,递归建立二叉树,并遍历
线索二叉树 先序构建 中序线索化 中序遍历
二叉树深度 二叉树前序遍历 递归实现 二种非递归实现 二叉树中序遍历: 递归实现 非递归实现 二叉树后序遍历: 递归实现 非递归实现 二叉树层次遍历 二叉树层次创建,创建方法遵循卡特兰数 ...
1 定义二叉树类,封装构造二叉树操作、遍历操作 2 实现由先序、中序序列构造二叉树的算法 3 实现由后序、中序序列构造二叉树的算法 4 各类递归 5 判定是否为完全二叉树
由先根次序和中跟次序建立二叉树,以及各种遍历的递归、非递归算法
主要介绍了Python二叉树的遍历操作,结合实例形式分析了Python针对二叉树的前序遍历,中序遍历,后序遍历,层序遍历等相关操作实现技巧,需要的朋友可以参考下
#include #include typedef struct bnode {int data; struct bnode *left,*right; }btree; btree *levelcreate(btree *root,int data[],int len) {
本程序利用递归算法,构建一棵二叉树,然后调用一个修改过的中根遍历法进行遍历输出
通过本次实习加强了对二叉树的建立和各种遍历...它们分别完成了二叉树的建立,以及递归、非递归的先序遍历、中序遍历、后序遍历和层序遍历算法:其中先序中序后序的递归遍历算法是利用二叉树的链式存储结构进行的遍历。
简单的二叉树建立与遍历过程,遍历的方法有递归的也有非递归的,二叉树的建立是利用二叉链表的形式!