二叉树的创建与遍历

基本概念

image.png

二叉树是一种非线性的数据结构,由一个根节点以及下面的子节点构成。由于计算机本身是线形方式存储的,太过复杂的我们没法创造除来。因此一个节点下最大只能创建两个节点。

静态构造二叉树类

class Tree{
	public int value;
	public Tree lTree;
	public Tree rTree;
	
	Tree(int value){
		this.value = value;
	}
	public void setlTree(Tree lTree){
		this.lTree = lTree;
	}
	public void setrTree(Tree rTree){
		this.rTree = rTree;
	}
}	
}

创建二叉树

image.png

		Tree t1 = new Tree(10);
		Tree t2 = new Tree(1);
		Tree t3 = new Tree(5);
		Tree t4 = new Tree(7);
		Tree t5 = new Tree(1);
		Tree t6 = new Tree(8);
		
		t1.setlTree(t2);
		t1.setrTree(t3);
		t2.setrTree(t6);
		t3.setlTree(t4);
		t3.setrTree(t5);

遍历二叉树

如果子节点不为空就使用递归继续执行。

	public static void f(Tree t){
		boolean l = t.lTree==null?false:true;
		boolean r = t.rTree==null?false:true;
		System.out.println(t.value);
		if (!l && !r) return;
		if (l) f(t.lTree);		
		if (r) f(t.rTree);
	
	}