链式存储的二叉树创建、遍历和查找
连式存储的二叉树结构图：
代码实现：
//-----------------------------------------创建二叉树以及添加根节点测试类-----------------------------------------------
package day0504;
/**
* @author Czw
* @Description 创建一棵链式二叉树
* @Date 2019/5/4 0004 上午 10:58
*/
public class TestBinaryTree {
public static void main ( String [] args){
//创建一棵二叉树
BinaryTree binTree=new BinaryTree();
//创建一个根节点
TreeNode root=new TreeNode(1);
//为根节点创建左节点
TreeNode leftNode=new TreeNode(2);
//为根节点创建右节点
TreeNode rightNode=new TreeNode(3);
//为根节点赋左右节点值
root.setLeftNode(leftNode);
root.setRightNode(rightNode);
//赋给树
binTree.setRoot(root);
}
}
//-------------------------------------链式存储的二叉树类-------------------------------------------------
package day0504;
/**
* @author Czw
* @Description 链式存储的二叉树
* @Date 2019/5/4 0004 上午 10:59
*/
public class BinaryTree {
//树的根节点
TreeNode root;
public void setRoot(TreeNode root) {
this.root = root;
}
}
//-----------------------------------------代表每个节点对象的类-----------------------------------------------
package day0504;
/**
* @author Czw
* @Description 链式存储二叉树的节点内容
* @Date 2019/5/4 0004 上午 11:05
*/
public class TreeNode {
//节点的权
int value;
//左儿子
TreeNode leftNode;
//右儿子
TreeNode rightNode;
public TreeNode(int value){
this.value=value;
}
public void setLeftNode(TreeNode leftNode) {
this.leftNode = leftNode;
}
public void setRightNode(TreeNode rightNode) {
this.rightNode = rightNode;
}
}
二叉树的遍历分为前、中、后三种遍历方式：
前序遍历：A B D E C F G（先取自己再去子节点，子节点若有节点同样如此）
中序遍历：D B E A F C G (先取左边子节点再自己然后右节点，若子节点有节点则同样如此）
后序遍历：D E B F G C A (先取左节点再取右节点再取自己，若有子节点则同样如此)
代码实现：
package day0504;
/**
* @author Czw
* @Description 测试创建一棵链式二叉树
* @Date 2019/5/4 0004 上午 10:58
*/
public class TestBinaryTree {
public static void main ( String [] args){
//创建一棵二叉树
BinaryTree binTree=new BinaryTree();
//创建一个根节点
TreeNode root=new TreeNode(1);
//赋给树
binTree.setRoot(root);
//为根节点创建左节点
TreeNode leftNode=new TreeNode(2);
//为根节点创建右节点
TreeNode rightNode=new TreeNode(3);
//为根节点赋左右节点值
root.setLeftNode(leftNode);
root.setRightNode(rightNode);
//为第二层左节点创建两个子节点
leftNode.setLeftNode(new TreeNode(4));
leftNode.setRightNode(new TreeNode(5));
//为第二层右节点创建两个子节点
rightNode.setLeftNode(new TreeNode(6));
rightNode.setRightNode(new TreeNode(7));
//前序遍历
binTree.frontShow();//结果：1 2 4 5 3 6 7
System.out.println("");
//中序遍历
binTree.middleShow();//结果：4 2 5 1 6 3 7
System.out.println("");
//后序遍历
binTree.afterShow();//结果：
}
}
------------------------------------------------------------------
package day0504;
/**
* @author Czw
* @Description 链式存储的二叉树
* @Date 2019/5/4 0004 上午 10:59
*/
public class BinaryTree {
//树的根节点
TreeNode root;
public void setRoot(TreeNode root) {
this.root = root;
}
public void frontShow() {
root.frontShow();
}
public void middleShow() {
root.middleShow();
}
public void afterShow() {
root.afterShow();
}
}
---------------------------------------------
package day0504;
/**
* @author Czw
* @Description 链式存储二叉树的节点内容
* @Date 2019/5/4 0004 上午 11:05
*/
public class TreeNode {
//节点的权
int value;
//左儿子
TreeNode leftNode;
//右儿子
TreeNode rightNode;
public TreeNode(int value){
this.value=value;
}
//前遍历
public void frontShow(){
System.out.print(value+" ");
if (leftNode!=null){
leftNode.frontShow();
}
if (rightNode!=null){
rightNode.frontShow();
}
}
public void setLeftNode(TreeNode leftNode) {
this.leftNode = leftNode;
}
public void setRightNode(TreeNode rightNode) {
this.rightNode = rightNode;
}
public void middleShow() {
if (leftNode!=null){
leftNode.middleShow();
}
System.out.print(value+" ");
if (rightNode!=null){
rightNode.middleShow();
}
}
public void afterShow() {
if (leftNode!=null){
leftNode.afterShow();
}
if (rightNode!=null){
rightNode.afterShow();
}
System.out.print(value +" ");
}
}
查找value值相同的节点：
实现代码：
package day0504;
/**
* @author Czw
* @Description 测试创建一棵链式二叉树
* @Date 2019/5/4 0004 上午 10:58
*/
public class TestBinaryTree {
public static void main ( String [] args){
//创建一棵二叉树
BinaryTree binTree=new BinaryTree();
//创建一个根节点
TreeNode root=new TreeNode(1);
//赋给树
binTree.setRoot(root);
//为根节点创建左节点
TreeNode leftNode=new TreeNode(2);
//为根节点创建右节点
TreeNode rightNode=new TreeNode(3);
//为根节点赋左右节点值
root.setLeftNode(leftNode);
root.setRightNode(rightNode);
//为第二层左节点创建两个子节点
leftNode.setLeftNode(new TreeNode(4));
leftNode.setRightNode(new TreeNode(5));
//为第二层右节点创建两个子节点
rightNode.setLeftNode(new TreeNode(6));
rightNode.setRightNode(new TreeNode(7));
//前序遍历
binTree.frontShow();//结果：1 2 4 5 3 6 7
System.out.println("");
//中序遍历
binTree.middleShow();//结果：4 2 5 1 6 3 7
System.out.println("");
//后序遍历
binTree.afterShow();//结果：4 5 2 6 7 3 1
System.out.println();
//查找指定元素
TreeNode result=binTree.frontSearch(5);
System.out.println(result);
}
}
-------------------------------------------------------------------------------------------
package day0504;
/**
* @author Czw
* @Description 链式存储的二叉树
* @Date 2019/5/4 0004 上午 10:59
*/
public class BinaryTree {
//树的根节点
TreeNode root;
public void setRoot(TreeNode root) {
this.root = root;
}
public void frontShow() {
root.frontShow();
}
public void middleShow() {
root.middleShow();
}
public void afterShow() {
root.afterShow();
}
public TreeNode frontSearch(int i) {
return root.frontSearch(i);
}
}
--------------------------------------------------------------------------------------
package day0504;
/**
* @author Czw
* @Description 链式存储的二叉树
* @Date 2019/5/4 0004 上午 10:59
*/
public class BinaryTree {
//树的根节点
TreeNode root;
public void setRoot(TreeNode root) {
this.root = root;
}
public void frontShow() {
root.frontShow();
}
public void middleShow() {
root.middleShow();
}
public void afterShow() {
root.afterShow();
}
public TreeNode frontSearch(int i) {
return root.frontSearch(i);
}
}