二叉树浅解_JAVA_编程开发_程序员俱乐部

hashu.html" target="_blank">二叉树
1、定义：树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构。
二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”和“右子树”。
链表是一种特殊的树。

2、构建规则：左子树<右子树

3、组成元素：根节点 、边、左（右）子树


二叉树的遍历方式
1、前序 、先序   :根节点 -->左-->右 访问根结点的操作发生在遍历其左右子树之前。
2、中序 :左 -->根节点-->右 访问根结点的操作发生在遍历其左右子树之中（间）。
3、后序 :左 -->右-->根节点 访问根结点的操作发生在遍历其左右子树之后。
4、层次
5、
6、广度

1．中序遍历的递归算法定义：
若二叉树非空，则依次执行如下操作：
⑴遍历左子树；
⑵访问根结点；
⑶遍历右子树。

2．先序遍历的递归算法定义：
若二叉树非空，则依次执行如下操作：
⑴ 访问根结点；
⑵ 遍历左子树；
⑶ 遍历右子树。
3．后序遍历得递归算法定义：
若二叉树非空，则依次执行如下操作：
⑴遍历左子树；
⑵遍历右子树；
⑶访问根结点。

练习：
1、构建树结构
2、分别实现 前、中、后序的遍历

结点类：

class="java" name="code">
public class Node {
//	节点存储的数据
	private Object date;
//	左节点的地址
	private Node left;
//	右节点的地址
	private Node right;
	
//	返回节点处的数据	
	public Object getDate() {
		return date;
	}
//	设置节点处的数据
	public void setDate(Object date) {
		this.date = date;
	}
//	返回左节点
	public Node getLeft() {
		return left;
	}
//	设置左节点
	public void setLeft(Node left) {
		this.left = left;
	}
//	返回右节点
	public Node getRight() {
		return right;
	}
//	设置右节点
	public void setRight(Node right) {
		this.right = right;
	}

	
//	构造函数	
	public Node() {
		super();
	}
//	构造函数
	public Node(Object date) {
		super();
		this.date = date;
	}
//  构造函数
	public Node(Object date, Node left, Node right) {
		this.date = date;
		this.left = left;
		this.right = right;
	}

}

树类：

public class NodeTree {
	
//	定义一个根节点
	private Node root;
	
	/**
	 * 添加节点 的方法
	 * @param node 要添加的代码
	 */
	public void add(Node node){
		if(root==null){
			root = node;
		}
		else{
			querynode1(root,node);
		}
	}
	
	/**
	 * 查找节点添加位置并添加的方法
	 * @param node1  根节点
	 * @param node2 要添加的节点
	 */
	public void querynode1(Node node1,Node node2){
		if((int)node2.getDate()<(int)node1.getDate()){
			if(node1.getLeft()==null){
				node1.setLeft(node2);
			}
			else{
				querynode1(node1.getLeft(),node2);
			}
		}
		else{
			if(node1.getLeft()==null){
				node1.setLeft(node2);
			}
			else if(node1.getRight()==null){
				node1.setRight(node2);
			}
			else{
				querynode1(node1.getRight(),node2);
			}
		}
		
	}

	/**
	 * 前序遍历
	 * @param node 根节点
	 */
	public void NLR(Node node){
//		访问根节点
		System.out.print(node.getDate()+"\t");
		
//		访问左子树
		if(node.getLeft()!=null){//左子树不为空
				NLR(node.getLeft());
		}
//		访问右子树
		if(node.getRight()!=null){//右子树不为空
			NLR(node.getRight());
		}
		
	}
	
	/**
	 * 中序遍历
	 * @param node 根节点
	 */
	public void LNR(Node node){
//		遍历左子树
		if(node.getLeft()==null){
			System.out.print(node.getDate()+"\t");
		}
		else{
			LNR(node.getLeft());
		}
//		遍历根节点
		if(node.getLeft()!=null){
			System.out.print(node.getDate()+"\t");
		}
//		遍历右子树
		if(node.getRight()!=null){
			LNR(node.getRight());
		}
	}
	
	/**
	 * 后序遍历
	 * @param node   根节点
	 */
	public void LRN(Node node){
//		遍历左树
		if(node.getLeft()==null){
			System.out.print(node.getDate()+"\t");
		}
		else{
			LRN(node.getLeft());
		}
//		遍历右树
		if(node.getRight()!=null){
			LRN(node.getRight());
		}
//		遍历根节点
		if(node.getLeft()!=null){
			System.out.print(node.getDate()+"\t");
		}
		
	}
	
	public void delete(Node node){
//		遍历查找
//		访问根节点
		System.out.print(node.getDate()+"\t");
		
//		访问左子树
		if(node.getLeft()!=null){//左子树不为空
				NLR(node.getLeft());
		}
//		访问右子树
		if(node.getRight()!=null){//右子树不为空
			NLR(node.getRight());
		}
	}	
	
}

主函数：

public class Manager {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		NodeTree nt = new NodeTree();
		Node[] node = new Node[8];
		node[0] = new Node(100);
		node[1] = new Node(90);
		node[2] = new Node(120);
		node[3] = new Node(80);
		node[4] = new Node(95);
		node[5] = new Node(110);
		node[6] = new Node(125);
		node[7] = new Node(85);
		for(int i =0; i<node.length;i++){
			nt.add(node[i]);
		}
//		前序遍历
		System.out.println("前序遍历输出~~~~~~~~~~~");
		nt.NLR(node[0]);
		System.out.println();
		
//		中序遍历
//		System.out.println("中序遍历输出~~~~~~~~~~~");
//		nt.LNR(node[0]);
//		System.out.println();
		
//		后序遍历
//		System.out.println("后序遍历输出~~~~~~~~~~~");
//		nt.LRN(node[0]);
//		System.out.println();
		
//		nt.delete(node[3]);
	}

}