网站推广与营销_怎么建立公众号微信_bing搜索 国内版_网站安全检测

树节点

先定义树节点结构，代码如下：

package tree;public class TreeNode {public int data;public TreeNode left;public TreeNode right;//数据的类型决定数据在内存中的存储形式,//这样可以接受本类型的数据public TreeNode(int data) {this.data=data;}public String toString() {return "TrreNode{"+"data="+data+",left"+left+",right="+right+"}";}}

注意！为什么left和right的类型为TreeNode？ 

        因为数据的类型决定数据在内存中的存储形式。left right示意为左右节点其类型也为TreeNode，用于接受后续一系列操作，保持了结构的一致性。

一、有序二叉树的构建

1、迭代法：

public void insert(int data) {//新建一个节点TreeNode newNode=new TreeNode(data);if(root==null) {root=newNode;return;}TreeNode currentNode=root;while(true) {if(newNode.data<currentNode.data) {if(currentNode.left!=null) {currentNode=currentNode.left;}else {currentNode.left=newNode;return;}}else {if(currentNode.right!=null) {currentNode=currentNode.right;}else {currentNode.right=newNode;return;}}}	}

2、递归法：

public void insertCircle(int value,TreeNode node) {//递归方式有序二叉树TreeNode temp=new TreeNode(value);if(root==null) {root=temp; return;}if(node.data<temp.data) {if(node.right==null) {node.right=temp;return;}insertCircle(value,node.right);}else {if(node.left==null) {node.left=temp;return;}insertCircle(value,node.left);}}

二、有序二叉树的遍历

我们采用递归的方式实现。这就要求我们找到递归规律和递归出口。

1、深度优先遍历——栈原理

先序遍历：

//先序遍历public void beforeOrder(TreeNode root) {if(root==null) {return;}System.out.println(" "+root.data);beforeOrder(root.left);beforeOrder(root.right);}

中序遍历：

//中序遍历public void inOrder(TreeNode root) {if(root==null) {return;}inOrder(root.left);System.out.println(" "+root.data);inOrder(root.right);}

 后序遍历:

//后序遍历
public void afterOrder(TreeNode root) {if(root==null) {return;}afterOrder(root.left);afterOrder(root.right);System.out.println(" "+root.data);}

2、广度优先遍历——队列原理

    public void levelOrder() {LinkedList<TreeNode> queue=new LinkedList<>();queue.add(root);while(!queue.isEmpty()) {root=queue.pop();System.out.println(root.data+" ");if(root.left!=null) {queue.add(root.left);}if(root.right!=null) {queue.add(root.right);}}}

 三、查询树中的某个值

//1.查询某个值public boolean search(TreeNode root,int value) {if (root == null) {return false; }if (root.data == value) {return true; } else if (value < root.data) {return search(root.left, value); // 在左子树中继续查找} else {return search(root.right, value); // 在右子树中继续查找}}

四、测试 

我们创建一个test类

package tree;public class test {public static void main(String[] args) {BinaryTree binaryTree=new BinaryTree();binaryTree.insert(5);binaryTree.insert(4);binaryTree.insert(2);binaryTree.insert(0);binaryTree.insert(3);binaryTree.insert(7);binaryTree.insert(6);System.out.println(binaryTree.root);System.out.println(binaryTree.search(binaryTree.root, 5));System.out.println(binaryTree.search(binaryTree.root, 9));BinaryTree binaryTree2=new BinaryTree();binaryTree2.insertCircle(5,binaryTree2.root);binaryTree2.insertCircle(4,binaryTree2.root);binaryTree2.insertCircle(2,binaryTree2.root);binaryTree2.insertCircle(0,binaryTree2.root);binaryTree2.insertCircle(3,binaryTree2.root);binaryTree2.insertCircle(7,binaryTree2.root);binaryTree2.insertCircle(6,binaryTree2.root);System.out.println(binaryTree2.root);}}

结果如下：