首页 > 代码库 > 二叉搜索树
二叉搜索树
- 树数据结构
树是一种二位数据结构，并且非常常见。树的元素，叶节点有两个“指针”和数据域。
- 二叉排序树
在一个子树中，根节点比左子节点要大，比右子节点要小。
- 树的遍历
先序遍历：先遍历子树的根节点，再遍历左子节点，最后遍历右子节点。
中序遍历：先遍历左子节点，再遍历根节点，最后遍历右子节点。
后序遍历：先遍历左子节点，再遍历右子节点，最后遍历根节点。
- 例子
添加节点的方法就是用两个节点，一个记录父节点，一个记录行进节点。
如果进入数据大于根节点，则进入右节点，如果小于根节点，则进入左节点。
package tree;/** * 二叉排序树 * @author MacBook * */public class tree1 { private treeNode root; public treeNode getRoot(){ return root; } public void insertNode(treeNode n){ treeNode parent = root; treeNode son = root; if(root == null){ root = n; return; } while(son != null){ parent = son; if(n.getData()>son.getData()) son = son.getRight(); else son = son.getLeft(); } if(parent.getData()>n.getData()) parent.setLeft(n); else parent.setRight(n); } //前序遍历 public void print1(treeNode n){ if(n!=null) { System.out.println(n.getData()); print1(n.getLeft()); print1(n.getRight()); } } //中序遍历 public void print2(treeNode n){ if(n!=null) { print2(n.getLeft()); System.out.println(n.getData()); print2(n.getRight()); } } //后序遍历 public void print3(treeNode n){ if(n!=null) { print3(n.getLeft()); print3(n.getRight()); System.out.println(n.getData()); } } public static void main(String[] args) { tree1 t = new tree1(); treeNode n1 = new treeNode(); n1.setData(7); treeNode n2 = new treeNode(); n2.setData(5); treeNode n3 = new treeNode(); n3.setData(9); treeNode n4 = new treeNode(); n4.setData(3); treeNode n5 = new treeNode(); n5.setData(6); treeNode n6 = new treeNode(); n6.setData(11); treeNode n7 = new treeNode(); n7.setData(8); t.insertNode(n1); t.insertNode(n2); t.insertNode(n3); t.insertNode(n4); t.insertNode(n5); t.insertNode(n6); t.insertNode(n7); t.print3(t.getRoot()); }}class treeNode{ private int data; private treeNode left; private treeNode right; public int getData() { return data; } public void setData(int data) { this.data =http://www.mamicode.com/ data; } public treeNode getLeft() { return left; } public void setLeft(treeNode left) { this.left = left; } public treeNode getRight() { return right; } public void setRight(treeNode right) { this.right = right; } }
先序遍历结果：7 5 3 6 9 8 11
中序遍历结果：3 5 6 7 8 9 11
后序遍历结果：3 6 5 8 11 9 7
二叉搜索树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。