java的二叉树结构

约定不等于承诺〃 2022-05-22 04:29 151阅读 0赞

首先，我们先来介绍一下二叉树的概念

二叉树：二叉树是每个节点最多有两个子树的[树结构][Link 1]。通常子树被称作“左子树”和“右子树”。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^\{i-1\}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n\_0，度为2的结点数为n\_2，则n\_0=n\_2+1。

![70][]

上图就是一个比较常见得到二叉树。他是由【4,2,1,3,5,7,6,8】对应的二叉树，他的插入规则如下。

按顺序插入，根节点为第一个元素，之后的元素与原来的元素比较，如果大插入到右边，小则插入到左边。如图：

![70 1][]

接下来我们用java实现上面这一二叉树。代码如下：

public class TreeLink { int data; //节点内的元素 TreeLink leftNode; //左子树 TreeLink rightNode; //右子树 public TreeLink(int data,TreeLink leftNode,TreeLink rightNode) { this.data = data; this.leftNode = leftNode; this.rightNode = rightNode; } @Override public String toString() { return "TreeLink [data=" + data + ", leftNode=" + leftNode + ", rightNode=" + rightNode + "]"; } }

public class Test { public static void main(String[] args) { int num[] = {4,2,1,3,5,7,6,8}; TreeLink first = new TreeLink(num[0], null, null); for(int i=1; i<num.length ; i++) { TreeLink next = new TreeLink(num[i], null, null); add(next,first); } System.out.println(first); } public static void add(TreeLink next,TreeLink node) { if(next.data >= node.data) { if(node.rightNode == null) { node.rightNode = next; }else { add(next,node.rightNode); } }else { if(node.leftNode == null) { node.leftNode = next; }else { add(next,node.leftNode); } } } }

输出结果为：

TreeLink [data=4, leftNode=TreeLink [data=2, leftNode=TreeLink [data=1, leftNode=null, rightNode=null], rightNode=TreeLink [data=3, leftNode=null, rightNode=null]], rightNode=TreeLink [data=5, leftNode=null, rightNode=TreeLink [data=7, leftNode=TreeLink [data=6, leftNode=null, rightNode=null], rightNode=TreeLink [data=8, leftNode=null, rightNode=null]]]]

以上就是实现的简单的二叉树的插入操作。

[Link 1]: https://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=501687&ss_c=ssc.citiao.link
[70]: /images/20220522/1e5a92d1424241749456349b46f2fa3b.png
[70 1]: /images/20220522/e5b1615402fe4716896a7b1836c3f54c.png