赞
踩
树可以转换为二叉树,二叉树还原为树。所以我们在解决树的问题时,可以通过实现二叉树来实现目的。
(1)顺序存储——数组存储(占用空间大,适合存完全二叉树(只要层数达到,并且除最后一层外全满))
(2)链式存储——二叉链表
感觉用数组实现树的真的特别少,所以这里我们通过二叉链表实现二叉树。
- package cn.datastruct.tree;
- /**
- * 二叉树
- * @author hydra
- *
- */
- public class BinaryTree {
-
- private Node root;//根结点
-
- class Node{ //内部类模仿树结构
-
- private int val;
- private Node lchild;//左孩子
- private Node rchild;//右孩子
-
-
- public Node(int val) {
- this.val = val;
- }
- }
-
- public void setRoot(int val) {
- this.root.val= val;
- }
- public Node getRoot() {
- return root;
- }
- public BinaryTree(int val) {
- Node node = new Node(val);
- this.root = node;
- }
-
- public BinaryTree() {
- this.root = null;
- }
-
- /**
- * 添加节点
- * @param val
- */
- public boolean add(int val){
- //创建新节点对象
- Node node = new Node(val);
- if(root==null) {//根结点不存在
- root = node;
- return true;
- }else {
- Node cur = root;
- while(true) {
- if(val < cur.val) {
- if(cur.lchild == null) {
- Node newNode = new Node(val);
- cur.lchild = newNode;
- return true;
- }
- cur = cur.lchild;
- }else if(val > cur.val){
- if(val > cur.val) {
- if(cur.rchild == null) {
- Node newNode = new Node(val);
- cur.rchild = newNode;
- return true;
- }
- cur = cur.rchild;
- }
- }else {
- return false;//不允许重复
- }
-
- }
- }
- }
-
- /**
- * 查找树中是否含有某值
- * @param val
- * @return
- */
- public Object find(int val) {
- Node cur = root;//记录当前结点的对象
- while(true) {
- if(cur.val == val)
- {
- return cur.val;
- }else if(cur.val > val){
- cur = cur.lchild;
- if(cur==null) {
- return null;
- }
- }else if(cur.val < val){
- cur = cur.rchild;
- if(cur==null) {
- return null;
- }
- }
-
- }
- }
-
- /**
- * 先序遍历
- * @param node
- */
- public static void preOrder(Node node) {
- if(node == null) {
- return ;
- }
- System.out.println(node.val);
- preOrder(node.lchild);
- preOrder(node.rchild);
- }
- /**
- * 中序遍历
- * @param node
- */
- public void inOrder(Node node) {
- if(node == null) {
- return ;
- }
-
- inOrder(node.lchild);
- System.out.println(node.val);
- inOrder(node.rchild);
- }
- /**
- * 后序遍历
- * @param node
- */
- public void froOrder(Node node) {
- if(node == null) {
- return ;
- }
- froOrder(node.lchild);
- froOrder(node.rchild);
- System.out.println(node.val);
-
- }
- public static void main(String[] args) {
- BinaryTree tree = new BinaryTree();
- int[] a = new int[] {3,1,0,2,7,5,8,9};
- for (int i : a) {
- tree.add(i);
- }
- // tree.setRoot(3);
- System.out.println("前序遍历");
- tree.preOrder(tree.getRoot());
- System.out.println("中序遍历");
- tree.inOrder(tree.getRoot());
- System.out.println("后序遍历");
- tree.froOrder(tree.getRoot());
-
- }
- }
-
-
-
其中中序输出是有序。
*************************************************************如有错误,欢迎指正**********************************************************
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。