1、二叉树类型
- 满二叉树:所有的叶子节点都在最后一层,节点数为2^n-1
- 完全二叉树:满足所有节点存在左右节点
2、二叉树遍历
- 前序遍历:先输出父节点,再遍历左子树和右子树;
- 中序遍历:先遍历左子树,再输出父节点,再遍历右子树;
- 后序遍历:先遍历左子树,再遍历右子树,再输出父节点
public class BinaryTreeDemo {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
HeroNode root = new HeroNode(1, "刘备");
HeroNode node2 = new HeroNode(2, "赵云");
HeroNode node3 = new HeroNode(3, "关羽");
HeroNode node4 = new HeroNode(4, "张飞");
HeroNode node5 = new HeroNode(5, "马超");
root.setLeftNode(node2);
root.setRightNode(node3);
node3.setRightNode(node4);
node3.setLeftNode(node5);
int no = 4;
//测试,前序遍历
System.out.println("前序遍历---------");
binaryTree.setRoot(root);
binaryTree.preOrder();
HeroNode heroNode = binaryTree.preOrder(no); //前序查找
System.out.println("查到no:"+no+"信息,"+"name="+heroNode.getName());
//测试,中序遍历
System.out.println("中序遍历---------");
binaryTree.setRoot(root);
binaryTree.infixOrder();
HeroNode heroNode1 = binaryTree.infixOrder(no); //中序查找
System.out.println("查到no:"+no+"信息,"+"name="+heroNode1.getName());
//测试,后序遍历
System.out.println("后序遍历---------");
binaryTree.setRoot(root);
binaryTree.backOrder();
HeroNode heroNode2 = binaryTree.backOrder(no);//后序查找
System.out.println("查到no:"+no+"信息,"+"name="+heroNode2.getName());
}
}
// 定义BinaryTree树
class BinaryTree{
private HeroNode root;
public void setRoot(HeroNode root){
this.root = root;
}
//前序遍历
public void preOrder(){
if (this.root!=null){
this.root.preOrder();
}else {
System.out.println("二叉树为空");
}
}
//前序查找
public HeroNode preOrder(int no){
HeroNode heroNode = null;
if (this.root!=null){
heroNode = this.root.preOrder(no);
}else {
System.out.println("没有查到额");
}
return heroNode;
}
//中序遍历
public void infixOrder(){
if (this.root!=null){
this.root.infixOrder();
}else {
System.out.println("二叉树为空");
}
}
//中序查找
public HeroNode infixOrder(int no){
HeroNode heroNode =null;
if (this.root!=null){
heroNode = this.root.infixOrder(no);
}else {
System.out.println("没有查到额");
}
return heroNode;
}
public void backOrder(){
if (this.root!=null){
this.root.backOrder();
}else {
System.out.println("二叉树为空");
}
}
// 后序查找
public HeroNode backOrder(int no){
HeroNode h = null;
if (this.root!=null){
h= this.root.backOrder(no);
}else {
System.out.println("没有查到额");
}
return h;
}
}
// 创建HeroNode 节点
class HeroNode{
private int no;
private String name;
private HeroNode leftNode;
private HeroNode rightNode;
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public HeroNode getLeftNode() {
return leftNode;
}
public void setLeftNode(HeroNode leftNode) {
this.leftNode = leftNode;
}
public HeroNode getRightNode() {
return rightNode;
}
public void setRightNode(HeroNode rightNode) {
this.rightNode = rightNode;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
'}';
}
// 编写前序遍历的方法
public void preOrder(){
System.out.println(this); //输出父节点
// 递归向左子树前序遍历
if (this.leftNode!=null){
this.leftNode.preOrder();
}
// 递归向右子树前序遍历
if (this.rightNode!=null){
this.rightNode.preOrder();
}
}
// 编写中序遍历的方法
public void infixOrder(){
if (this.leftNode!=null){
this.leftNode.infixOrder();
}
System.out.println(this);
if (this.rightNode!=null){
this.rightNode.infixOrder();
}
}
// 编写后序遍历的方法
public void backOrder(){
if (this.leftNode!=null){
this.leftNode.backOrder();
}
if (this.rightNode!=null){
this.rightNode.backOrder();
}
System.out.println(this);
}
// 前序遍历查找
public HeroNode preOrder(int no){
System.out.println("前序查询no");
if (this.no == no){
return this;
}
HeroNode resNode = null;
if (this.leftNode != null ){
resNode = this.leftNode.preOrder(no);
}
if (resNode !=null){
return resNode;
}
if (this.rightNode!=null){
resNode = this.rightNode.preOrder(no);
}
if (resNode !=null){
return resNode;
}
return resNode;
}
// 中序查找
public HeroNode infixOrder(int no){
HeroNode heroNode = null;
if (this.leftNode!=null){
heroNode = leftNode.infixOrder(no);
}
if (heroNode!=null){
return heroNode;
}
System.out.println("中序查找开始");
if (this.no == no){
return this;
}
if (this.rightNode!=null){
heroNode = this.rightNode.infixOrder(no);
}
if (heroNode!=null){
return heroNode;
}
return heroNode;
}
/* 后序查找
* */
public HeroNode backOrder(int no){
HeroNode heroNode = null;
if (this.leftNode!=null){
heroNode = this.leftNode.backOrder(no);
}
if (heroNode !=null){
return heroNode;
}
if (this.rightNode!= null){
heroNode = this.rightNode.backOrder(no);
}
if (heroNode !=null){
return heroNode;
}
System.out.println("开始后序查找");
if (this.no == no){
return this;
}
return heroNode;
}
}
持续更新中.................
评论区