首先,是关于二叉树的定义,我在这阐述一下,避免还有些朋友不知道
二叉树是N个结点的有限集合,该集合或者为空集,或者由一个根节点跟两棵互不相交的、分别称为根节点的左子树或者右子树的二叉树组成,
二叉树有以下几个特点
1:每个结点最多有两个子树
2:左子树跟右子树是有序的
3:及时树中某个结点只有一棵子树,也要区分是左子树还是右子树
二叉树有以下几个形态:
1:空二叉树
2:只有一个根结点
3:根结点只有左子树
4:根结点只有右子树
5:根结点既有左子树,又有右子树
以上,是摘自 大话数据结构对二叉树的描述,
------------------------------------我是分割线----------------------------------
以下是二叉树的常见结构,只大概列举一下,二叉树的逻辑关系
说完二叉树的逻辑关系,下面我们说下,二叉树的存储结构,下面我们只介绍二叉链表存储
因为二叉树的每个结点最多有两个孩子,所以我们为它设计一个数据域跟两个指针域,两个指针域分别表示左结点跟右节点,下面是结构示意图
结构图有了,剩下的,我们就是将结构图转换为代码
public class BinaryTree { //根结点,默认为null private Node root = null; public Node getRoot() { return root; } //通过内部类,构建结点 private class Node{ //左节点 private Node left; //数据域 private int data; //右节点 private Node right; public Node(int data) { this.data = data; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public int getData() { return data; } public void setData(int data) { this.data = data; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } } /** * 创建人:贺小五 * 创建时间:2017-09-16 00:54:52 * 描述: * 构建二叉树 * Node 为结点, * data 为数据 */ private void buildBiTree(Node node,int data){ //如果根结点是空,那么设置根结点,并且设置数据域 if(root == null){ root = new Node(data); }else{ /** * 根结点不为空,那么判断数据是否小于当前结点的数据 */ if(data
以上就是构建一个普通二叉树的代码,根结点的左叶子结点会小于根结点,右叶子结点反之,
然后我们上一段测试代码,往该树插入数据,
public static void main(String[] args) { int[] datas = {72,37,29,55,51,80}; BinaryTree biTree = BinaryTree.createBiTree(datas); }
执行测试代码后,结构应该是如下图(测试的同学可以debug 看树的结构)
以上就是构建一个二叉树的代码,很简单,下篇分享一下二叉树的遍历
到这,文章就结束了!
以上,均为本人个人理解,比较简单的理解,或许跟各位看官理解的有出入,欢迎指正交流
欢迎转载,请注明出处跟作者,谢谢!