Netjava Lesson12 二叉树

2013.07.31

 

上课内容：二叉树

 

首先我们回顾一下上节课的内容，上节课我们讲的是链表。
我们知道了双链表每个节点是由一个三部分组成，一部分存储数据，另外两个部分分别存储上一个节点的地址和下一个节点的地址。那么我们今天要讲的二叉树其实与双链表里节点的组成是相同的，只不过除了存储数据部分外，另外两个分别存储以该节点作为根节点的左子树和右子树的地址。二叉树和链表的最大区别在于链表是一条链子，是特殊的二叉树，而二叉树更像一个树木，有根和叶子。

 

下面我们来具体地介绍一下二叉树：
首先二叉树有一个最顶端的节点，叫做根节点，然后在根节点下有很多的节点我们称之为叶子节点。每个节点都会存储数据和它的左右子树的地址，如果没有就为null。二叉树和树的最大区别在于二叉树每个节点只能开两个叉，而我们生活中的树可以开多个叉，又可以说二叉树是树的一个特例。

二叉树的遍历方式：前序遍历，中序遍历，后序遍历，深度优先遍历，广度优先遍历，层序遍历。我们这里介绍前三种比较基本的遍历方式：前序遍历，中序遍历和后序遍历。
前序遍历：先遍历根节点，然后遍历其左节点，最后遍历其右节点。若根节点下左节点还有子树的话，就要以它为根节点按同样规则遍历其子树。前序遍历可以用三个字来精辟地概括：根左右。同理我们也可以概括中序遍历：左根右，后序遍历：左右根。

 

理论总归是理论，实践才能出真知，下面我们开始一个二叉树：
首先我们还是构建一个节点类：

public class Node {
	private int data;// 节点的数据
	private Node left;// 左节点
	private Node right;// 右节点

	/**
	 * 构造方法
	 * 
	 * @param data要输入的数据
	 */
	public Node(int data) {
		this.data = data;
	}

	/**
	 * 构造方法
	 * 
	 * @param data要输入的数据
	 * @param left左节点
	 * @param right右节点
	 */
	public Node(int data, Node left, Node right) {
		this.data = data;
		this.left = left;
		this.right = right;
	}

	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	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 class NodeTree {

	private Node root;// 根节点

	/**
	 * 增加一个节点
	 * 
	 * @param node所要增加的节点
	 */
	public void add(Node node) {
		// 如果根节点为空
		if (root == null) {
			// 将node设置为根节点
			root = node;
		} else {
			// 否则调用方法进入节点
			querynode(root, node);
		}
	}

	/**
	 * 移除节点的的方法
	 * 
	 * @param root根节点
	 * @param node指定节点
	 * @return
	 */
	public boolean remove(Node root, Node node) {
		// 如果指定节点就是根节点
		if (root == node) {
			// 设置根节点为空
			root = null;
		} // 如果找到跟节点，返回true
		else if (findnode(root, node)) {
			return true;
		}
		// 如果没找到，返回false
		return false;
	}

	/**
	 * 找节点的方法
	 * 
	 * @param node1根节点
	 * @param node2要找的节点
	 * @return
	 */
	public boolean findnode(Node node1, Node node2) {
		// 如果左边的节点不为空
		if (node1.getLeft() != null) {
			// 如果左边就是要找的节点
			if (node1.getLeft() == node2) {
				// 设置其根节点的左边为空，并返回true
				node1.setLeft(null);
				return true;
			}// 否则，继续找它的左子叶
			else {
				findnode(node1.getLeft(), node2);
			}
		}
		// 如果右边的节点不为空
		if (node1.getRight() != null) {
			// 如果右边就是要找的节点
			if (node1.getRight() == node2) {
				// 设置其根节点的右边为空，并返回true
				node1.setRight(null);
				return true;
			}// 否则，继续找它的右子叶
			else {
				findnode(node1.getRight(), node2);
			}
		}
		return false;
	}

	/**
	 * 插入节点的方法
	 * 
	 * @param node1根节点
	 * @param node2要插入的节点
	 */
	public void querynode(Node node1, Node node2) {
		// 如果根节点小于子叶节点
		if (node1.getData() < node2.getData()) {
			// 判断其右子叶是否为空如果不为空，继续朝下遍历
			if (node1.getRight() != null) {
				querynode(node1.getRight(), node2);
			} else {
				// 若右子叶为空，将节点放在这里
				node1.setRight(node2);
			}
		} else {
			// 判断其左子叶是否为空如果不为空，继续朝下遍历
			if (node1.getLeft() != null) {
				querynode(node1.getLeft(), node2);
			} else {
				// 若左子叶为空，将节点放在这里
				node1.setLeft(node2);
			}
		}
	}

	/**
	 * 前序遍历
	 * 
	 * @param node根节点
	 */
	public void preorder(Node root) {
		// 如果输入的节点不为空
		if (root != null) {
			// 访问根节点
			visit(root);
			// 遍历其左子树
			preorder(root.getLeft());
			// 遍历右字数
			preorder(root.getRight());
		}
	}

	/**
	 * 中序遍历
	 * 
	 * @param root根节点
	 */
	public void inorder(Node root) {
		if (root != null) {
			// 如果左子树不为空
			if (root.getLeft() != null) {
				// 遍历其左子树
				inorder(root.getLeft());
			}
			// 访问根节点
			visit(root);
			// 如果右子树不为空
			if (root.getRight() != null) {
				// 遍历其右子树
				inorder(root.getRight());
			}
		}
	}

	/**
	 * 后序遍历
	 * 
	 * @param root根节点
	 */
	public void postorder(Node root) {
		if (root != null) {
			// 如果左子树不为空
			if (root.getLeft() != null) {
				// 遍历其左子树
				postorder(root.getLeft());
			}
			// 如果右子树不为空
			if (root.getRight() != null) {
				// 遍历其右子树
				postorder(root.getRight());
			}
			// 访问根节点
			visit(root);
		}
	}

	/**
	 * 得到根节点
	 * 
	 * @return 根节点
	 */
	public Node getRoot() {
		return root;
	}

	/**
	 * 访问节点
	 * 
	 * @param node要被访问的节点
	 */
	public void visit(Node node) {
		// 输出节点的data
		System.out.print(node.getData() + " ");
	}
}

 

这样二叉树就构建完成了，没学之前感觉挺复杂的，但是通过努力觉得其实没有想象中的那么难，不怕不会，就怕被问题给吓倒，同志们，努力吧！

评论

1 楼 Kslsi 2013-08-06  

还得去种树……