链式二叉树

  • 关于二叉树的基本性质和结构特征，在此不做详细说明，因为网上的文章非常多，可以查阅

  • 本文主要以泛型实现链式二叉树的基本方法，包括：

    1. 添加结点
    2. 查找结点
    3. 计算深度
    4. 清空子树
    5. 前序遍历
    6. 中序遍历
    7. 后序遍历

结构示意图

二叉树.png
结果.PNG

结点类 --- Node.java

package tree;

/**
 * Created by noonbiteun
 * Date: 2017/8/10
 */
public class Node<T> {
    private T data;             //数据
    private Node<T> left;       //左子树
    private Node<T> right;      //右子树
    private Node<T> parent;     //父结点

    public T getData() {
        return data;
    }

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

    public Node<T> getLeft() {
        return left;
    }

    public void setLeft(Node<T> left) {
        this.left = left;
    }

    public Node<T> getRight() {
        return right;
    }

    public void setRight(Node<T> right) {
        this.right = right;
    }

    public Node<T> getParent() {
        return parent;
    }

    public void setParent(Node<T> parent) {
        this.parent = parent;
    }

    //清空结点
    public void clear() {
        left = null;
        right = null;
        parent = null;
    }
}

初始化二叉树

 public Node<T> initTree(T data) {
        System.out.println("初始化树结构...数据类型为：" + data.getClass());
        rootNode = new Node<>();
        rootNode.setData(data);
        rootNode.setParent(null);
        rootNode.setLeft(null);
        rootNode.setRight(null);
        return rootNode;
    }

添加结点

   //明确父结点的情况
    public void addTreeNode(Node<T> parent, T data, boolean lr) {
        Node<T> node = new Node<>();
        node.setParent(parent);
        node.setData(data);
        node.setLeft(null);
        node.setRight(null);
        if (lr) {
            parent.setLeft(node);
        } else {
            parent.setRight(node);
        }
    }

    //不明确父结点的情况，只知道父结点的数据
    public void addTreeNode(T parentData, T data, boolean lr) {
        Node<T> parent = findTreeNode(rootNode, parentData);
        if (parent == null) {
            System.out.println("添加结点错误，无数据为 " + parentData + " 的父结点");
            return;
        }
        addTreeNode(parent, data, lr);
    }

查找结点

    //从treeNode结点开始查找数据为data的结点
    public Node<T> findTreeNode(Node<T> treeNode, T data) {
        if (treeNode == null || data == null) {
            return null;
        }
        Node<T> ptr;
        if (treeNode.getData().equals(data)) {
            return treeNode;
        } else {
            ptr = findTreeNode(treeNode.getLeft(), data);
            if (ptr != null) {
                return ptr;
            }
            ptr = findTreeNode(treeNode.getRight(), data);
            if (ptr != null) {
                return ptr;
            }
            return null;
        }
    }

计算深度

    //计算深度
    public int getTreeDepth(Node<T> treeNode) {
        int depLeft, depRight;
        if (treeNode == null) {
            return 0;
        } else {
            depLeft = getTreeDepth(treeNode.getLeft());
            depRight = getTreeDepth(treeNode.getRight());

            return depLeft > depRight ? depLeft+1 : depRight+1;
        }
    }

清空子树

    //清空treeNode的子树
    public void clearTree(Node<T> treeNode) {
        if (treeNode != null) {
            clearTree(treeNode.getLeft());
            clearTree(treeNode.getRight());
            treeNode.clear();
        }
    }

先序遍历、中序遍历、后序遍历

    //先序遍历
    public void DLRTree(Node<T> treeNode) {
        if (treeNode != null) {
            System.out.println(treeNode.getData());
            DLRTree(treeNode.getLeft());
            DLRTree(treeNode.getRight());
        }
    }

    //中序遍历
    public void LDRTree(Node<T> treeNode) {
        if (treeNode != null) {
            LDRTree(treeNode.getLeft());
            System.out.println(treeNode.getData());
            LDRTree(treeNode.getRight());
        }
    }

    //后序遍历
    public void LRDTree(Node<T> treeNode) {
        if (treeNode != null) {
            LRDTree(treeNode.getLeft());
            LRDTree(treeNode.getRight());
            System.out.println(treeNode.getData());
        }
    }

整合：LinkTree.java 链式二叉树类

package tree;

import java.util.Scanner;

/**
 * Created by noonbiteun
 * Date: 2017/8/10
 */
public class LinkTree<T> {

    private Node<T> rootNode;

    public Node<T> getRootNode() {
        return rootNode;
    }

    public Node<T> initTree(T data) {
        System.out.println("初始化树结构...数据类型为：" + data.getClass());
        rootNode = new Node<>();
        rootNode.setData(data);
        rootNode.setParent(null);
        rootNode.setLeft(null);
        rootNode.setRight(null);
        return rootNode;
    }

    //明确父结点的情况
    public void addTreeNode(Node<T> parent, T data, boolean lr) {
        Node<T> node = new Node<>();
        node.setParent(parent);
        node.setData(data);
        node.setLeft(null);
        node.setRight(null);
        if (lr) {
            parent.setLeft(node);
        } else {
            parent.setRight(node);
        }
    }

    //不明确父结点的情况，只知道父结点的数据
    public void addTreeNode(T parentData, T data, boolean lr) {
        Node<T> parent = findTreeNode(rootNode, parentData);
        if (parent == null) {
            System.out.println("添加结点错误，无数据为 " + parentData + " 的父结点");
            return;
        }
        addTreeNode(parent, data, lr);
    }

    //从treeNode结点开始查找数据为data的结点
    public Node<T> findTreeNode(Node<T> treeNode, T data) {
        if (treeNode == null || data == null) {
            return null;
        }
        Node<T> ptr;
        if (treeNode.getData().equals(data)) {
            return treeNode;
        } else {
            ptr = findTreeNode(treeNode.getLeft(), data);
            if (ptr != null) {
                return ptr;
            }
            ptr = findTreeNode(treeNode.getRight(), data);
            if (ptr != null) {
                return ptr;
            }
            return null;
        }
    }


    public Node<T> getLeftNode(Node<T> treeNode) {
        if (treeNode != null) {
            return treeNode.getLeft();
        } else {
            return null;
        }
    }

    public Node<T> getRightNode(Node<T> treeNode) {
        if (treeNode != null) {
            return treeNode.getRight();
        } else {
            return null;
        }
    }

    //计算深度
    public int getTreeDepth(Node<T> treeNode) {
        int depLeft, depRight;
        if (treeNode == null) {
            return 0;
        } else {
            depLeft = getTreeDepth(treeNode.getLeft());
            depRight = getTreeDepth(treeNode.getRight());

            return depLeft > depRight ? depLeft+1 : depRight+1;
        }
    }

    public boolean isEmptyTree() {
        return rootNode == null;
    }

    public void clearTree(Node<T> treeNode) {
        if (treeNode != null) {
            clearTree(treeNode.getLeft());
            clearTree(treeNode.getRight());
            treeNode.clear();
        }
    }

    //先序遍历
    public void DLRTree(Node<T> treeNode) {
        if (treeNode != null) {
            System.out.println(treeNode.getData());
            DLRTree(treeNode.getLeft());
            DLRTree(treeNode.getRight());
        }
    }

    //中序遍历
    public void LDRTree(Node<T> treeNode) {
        if (treeNode != null) {
            LDRTree(treeNode.getLeft());
            System.out.println(treeNode.getData());
            LDRTree(treeNode.getRight());
        }
    }

    //后序遍历
    public void LRDTree(Node<T> treeNode) {
        if (treeNode != null) {
            LRDTree(treeNode.getLeft());
            LRDTree(treeNode.getRight());
            System.out.println(treeNode.getData());
        }
    }
}

测试类： LinkTreeTest.java

package tree;

/**
 * Created by noonbiteun
 * Date: 2017/8/10
 */
public class LinkTreeTest {

    private static final boolean left = true;//添加到左子树
    private static final boolean right = false;//添加到右子树

    public static void main(String[] args) {

        LinkTree<String> linkTree = new LinkTree<>();
        linkTree.initTree("a");

        /*
        * 隐式添加结点，不用自己new Node出来，直接往已知结点后加
        * */
        linkTree.addTreeNode("a", "b", left);
        linkTree.addTreeNode("a", "c", right);

        linkTree.addTreeNode("b", "d", left);
        linkTree.addTreeNode("b", "e", right);

        linkTree.addTreeNode("e", "g", left);
        linkTree.addTreeNode("e", "h", right);

        linkTree.addTreeNode("c", "f", right);

        /*
        * 显式添加结点，自己链接各个node
        * */
        /*Node<String> b = new Node<>();
        b.setData("b");
        Node<String> c = new Node<>();
        c.setData("c");
        Node<String> d = new Node<>();
        d.setData("d");
        Node<String> e = new Node<>();
        e.setData("e");
        Node<String> f = new Node<>();
        f.setData("f");
        Node<String> g = new Node<>();
        g.setData("g");
        Node<String> h = new Node<>();
        h.setData("h");*/

        System.out.println();
        System.out.println("先序遍历：");
        linkTree.DLRTree(linkTree.getRootNode());
        System.out.println();
        System.out.println("中序遍历：");
        linkTree.LDRTree(linkTree.getRootNode());
        System.out.println();
        System.out.println("后序遍历：");
        linkTree.LRDTree(linkTree.getRootNode());
        System.out.println();
        System.out.println("二叉树深度："+ linkTree.getTreeDepth(linkTree.getRootNode()));
    }
}

运行结果：

运行结果
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 数据结构和算法--二叉树的实现
    数据结构和算法--二叉树的实现 几种二叉树 1、二叉树 和普通的树相比，二叉树有如下特点： 每个结点最多只有两棵子...
    sunhaiyu阅读 6,522评论 0赞 14
  • 四、树与二叉树
    四、树与二叉树 1. 二叉树的顺序存储结构 二叉树的顺序存储就是用数组存储二叉树。二叉树的每个结点在顺序存储中都有...
    MinoyJet阅读 1,585评论 0赞 7
  • 关于B树的一些总结(一)
    B树的定义 一棵m阶的B树满足下列条件： 树中每个结点至多有m个孩子。 除根结点和叶子结点外，其它每个结点至少有m...
    文档随手记阅读 13,337评论 0赞 25
  • 二叉树
    0. 什么是树 数据的基本单位是数据元素，在涉及到数据处理时数据元素之间的关系称之为结构，我们依据数据元素之间关系...
    安安zoe阅读 498评论 0赞 0
  • 数据结构与算法 —— 05 树
    1.树(Tree): 树是 n(n>=0) 个结点的有限集。当 n=0 时称为空树。在任意一颗非空树中：有且仅有一...
    ql2012jz阅读 1,045评论 0赞 3