树二叉树总结

 

一、数的相关

 

节点：  节点是树的基本组成单位，它由数据域和指向其他节点的指针

 

度：  节点拥有子节点的个数称为该节点的度。

 

叶子节点：叶子节点是树的终端节点，其度为0。

 

高度：    树种节点的最大层次称为树的高对（或者叫深度）。

 

根节点：  

 

二叉树：  二叉树是树的一种，其特点是每个节点至多只有两颗子树（即

 

于2的节点），并且二叉树的子树有左右之分，其次序不能随意颠倒。

 

二叉树的遍历：二叉树有四种遍历次序，先序遍历，终须遍历，后序遍历

 

例如，一下面的树为例

 

先序遍历：

 

步骤：

 

若二叉树不为空，则

 

访问根节点；

 

先序遍历左子树；

 

先序遍历右子树；

 

则下面的树的先序遍历顺序为：ABDECFG

 

中序遍历：

 

步骤：

 

若二叉树不为空，则

 

中序遍历左子树；

 

访问根节点；

 

中序遍历右子树；

 

则下面的树的中序遍历为：DBEAFCG

 

  后序遍历：

 

步骤：

 

若二叉树不为空，则

 

后序遍历左子树；

 

后序遍历右子树；

 

访问根节点；

 

则下面的树的后序遍历为：DEBFGCA

 

 

A

      /   \

    B     C

   /\     /\

          D  E   F  G

例如，在上面的树，A是根节点（root），D,E,F,G则是叶子节点B,C是A的子节点，是D,E,F,G

 

的父节点，D,E,F,G则是兄弟节点。我们在定义树的节点之间的关系时与链表相似，同样是用类封装。

 

 

public class BinaryTree {

	private BinaryTree root;// 二叉树的根

	private BinaryTree lchild;// 定义二叉树的左子树

	private BinaryTree rchild;// 定义二叉树的右子树

	private BinaryTree parent;// 定义二叉树的父节点

	private Object data;// 传入的数据类型

	/**

	 * 

	 * data:传入的初始数据类型

	 */

	public BinaryTree(String data) {

		this.data = data;

	}

	/**

	 * 返回数据

	 */

	public Object getData() {

		return data;

	}

	/**

	 * 设置根节点

	 */

	public void setRoot(BinaryTree root) {

		this.root = root;

	}

	/**

	 * 返回根节点

	 */

	public BinaryTree getRoot() {

		return root;

	}

	/**

	 * 设置父节点

	 */

	public void setParent(BinaryTree parent) {

		this.parent = parent;

	}

	/**

	 * 返回父节点

	 */

	public BinaryTree getParent() {

		return parent;

	}

	/**

	 * 设置左子节点

	 */

	public void setLChild(BinaryTree lchild) {

		this.lchild = lchild;

	}

	/**

	 * 返回左子节点

	 */

	public BinaryTree getLChild() {

		return lchild;

	}

	/**

	 * 设置右子节点

	 */

	public void setRChild(BinaryTree rchild) {

		this.rchild = rchild;

	}

	/**

	 * 返回右子节点

	 */

	public BinaryTree getRChild() {

		return rchild;

	}

}

 

 

定义好以后我们就可以创建一颗二叉树了我们使用表达式2*10-8/(2+2)

 

/**

	 * 创建二叉树

	 */

	public void creatTree() {

		BinaryTree biNode_1 = new BinaryTree("-");

		BinaryTree biNode_2 = new BinaryTree("*");

		BinaryTree biNode_3 = new BinaryTree("/");

		BinaryTree biNode_4 = new BinaryTree("2");

		BinaryTree biNode_5 = new BinaryTree("10");

		BinaryTree biNode_6 = new BinaryTree("8");

		BinaryTree biNode_7 = new BinaryTree("+");

		BinaryTree biNode_8 = new BinaryTree("2");

		BinaryTree biNode_9 = new BinaryTree("2");

		root = biNode_1;// 根节点

		// 根节点的左右子树

		biNode_1.setLChild(biNode_2);

		biNode_1.setRChild(biNode_3);

		biNode_2.setLChild(biNode_4);

		biNode_2.setRChild(biNode_5);

		biNode_4.setLChild(null);

		biNode_4.setRChild(null);

		biNode_5.setLChild(null);

		biNode_5.setRChild(null);

		biNode_3.setLChild(biNode_6);

		biNode_3.setRChild(biNode_7);

		biNode_6.setLChild(null);

		biNode_6.setRChild(null);

		biNode_7.setLChild(biNode_8);

		biNode_7.setRChild(biNode_9);

		biNode_8.setLChild(null);

		biNode_8.setRChild(null);

}

 

 

设置好所有的左右子树，接下来我们遍历我们建立的这颗二叉树

 

 

/**

 *中序遍历二叉树

 */

public void inorderTraversal(BinaryTree r) {

		if (null != r) {

			traverse_1(r.getLChild());

			System.out.print(r.getData());

			traverse_1(r.getRChild());

		}

}

 

则打印出来的结果将会是2*10-8/2+2，如果还想算出结果的话，我们首先判断该节点是否有子节点，如果没有那我们确定该节点是数字，我们String类型强转成int行返回，再进行判断如果有子节点，那我们遍历左子树，遍历右子树，获取返回值，根据该节点的运算符号对获取的左右子树进行运算，然后返回结果。那么我们递归到最后就能得到表达式的结果

 

 **

 * 计算表达式结果

 */

	public int inorder(BinaryTree t) {

		// 判断是否是叶子节点

		if (null == t.getLChild() && null == 

t.getRChild()) {

			return Integer.parseInt((String) 

t.getData());

		} else {

			inorder(t.getLChild());

			// System.out.print(t.getData());

			inorder(t.getRChild());

			// 获取返回的节点值

			int a = inorder(t.getLChild());

			int b = inorder(t.getRChild());

			if (t.getData().equals("*")) {

				return a * b;

			} else if (t.getData().equals("+")) {

				return a + b;

			} else if (t.getData().equals("-")) {

				return a - b;

			} else if (t.getData().equals("/")) {

				return a / b;

			}

		}

		return 0;

	}