您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

二叉树(图文)

第十三双眼睛2023-10-19【数据结构与算法】人已围观

简介二叉树

二叉树

package com.xingchen.day008;
public class BinTreeDemo {
public static void main(String[] args) {
BinTree binTree = new BinTree();
HeroNode root = new HeroNode(1,"宋江");
HeroNode node2 = new HeroNode(2,"无用");
HeroNode node3 = new HeroNode(3,"卢俊义");
HeroNode node4 = new HeroNode(4,"林冲");
root.left=node2;
root.right=node3;
node3.right=node4;
binTree.setRoot(root);
//测试前序遍历
//binTree.preOrder();
//测试中序遍历
//binTree.infixOrder();
//测试后续遍历
binTree.postOrder();
}
}
class BinTree {
public 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 void infixOrder() {
if (this.root != null) {
this.root.infixOrder();
} else {
System.out.println("二叉树为空");
}
}
public void postOrder() {
if (this.root != null) {
this.root.postOrder();
} else {
System.out.println("二叉树为空");
}
}

}
class HeroNode {
public int no;
public String name;
public HeroNode left;
public HeroNode right;
public HeroNode(int no,String name) {
this.no = no;
this.name = name;
}
public void preOrder() {
System.out.println(this);
//递归左子树
if (this.left != null) {
this.left.preOrder();
}
//递归右子树
if (this.right != null) {
this.right.preOrder();
}
}
public void infixOrder() {
//先递归左子树
if (this.left!= null) {
this.left.infixOrder();
}
System.out.println(this);
//递归右子树
if (this.right != null) {
this.right.infixOrder();
}
}
public void postOrder() {
if (this.left != null) {
this.left.postOrder();
}
if (this.right != null) {
this.right.postOrder();
}
System.out.println(this);
}
@Override
public String toString() {
return "HeroNode{" +
"name='" + name + '\'' +
'}';
}
}

二叉树查找

package com.xingchen.day008;
public class BinTreeSearchDemo {
public static void main(String[] args) {
BinTree1 binTree = new BinTree1();
HeroNode1 root = new HeroNode1(1,"宋江");
HeroNode1 node2 = new HeroNode1(2,"无用");
HeroNode1 node3 = new HeroNode1(3,"卢俊义");
HeroNode1 node4 = new HeroNode1(4,"林冲");
root.left=node2;
root.right=node3;
node3.right=node4;
binTree.setRoot(root);
HeroNode1 heroNode1 = null;
//heroNode1 = binTree.preOrderSearch(3);
//heroNode1 = binTree.infixOrderSearch(3);
heroNode1 = binTree.postOrderSearch(31);
if (heroNode1 != null) {
System.out.println(heroNode1);
} else {
System.out.println("没有找到");
}
}
}
class BinTree1 {
public HeroNode1 root;
public void setRoot(HeroNode1 root) {
this.root = root;
}
public void preOrder () {
if (this.root != null) {
this.root.preOrder();
} else {
System.out.println("二叉树为空");
}
}
public void infixOrder() {
if (this.root != null) {
this.root.infixOrder();
} else {
System.out.println("二叉树为空");
}
}
public void postOrder() {
if (this.root != null) {
this.root.postOrder();
} else {
System.out.println("二叉树为空");
}
}
public HeroNode1 preOrderSearch(int no) {
if (root != null) {
return this.root.preOrderSearch(no);
}
return null;
}
public HeroNode1 infixOrderSearch(int no) {
if (root != null) {
return this.root.infixOrderSearch(no);
}
return null;
}
public HeroNode1 postOrderSearch(int no) {
if (root != null) {
return this.root.postOrderSearch(no);
}
return null;
}
}
class HeroNode1 {
public int no;
public String name;
public HeroNode1 left;
public HeroNode1 right;
public HeroNode1(int no,String name) {
this.no = no;
this.name = name;
}
public void preOrder() {
System.out.println(this);
//递归左子树
if (this.left != null) {
this.left.preOrder();
}
//递归右子树
if (this.right != null) {
this.right.preOrder();
}
}
public void infixOrder() {
//先递归左子树
if (this.left!= null) {
this.left.infixOrder();
}
System.out.println(this);
//递归右子树
if (this.right != null) {
this.right.infixOrder();
}
}
public void postOrder() {
if (this.left != null) {
this.left.postOrder();
}
if (this.right != null) {
this.right.postOrder();
}
System.out.println(this);
}
public HeroNode1 preOrderSearch(int no) {
if (this.no == no) {
return this;
}
HeroNode1 res = null;
if (this.left != null) {
res = this.left.preOrderSearch(no);
}
if (res != null) {
return res;
}
if (this.right != null) {
res = this.right.preOrderSearch(no);
}
return res;
}
public HeroNode1 infixOrderSearch(int no) {
HeroNode1 res = null;
if (this.left != null) {
res = this.left.infixOrderSearch(no);
}
if (res != null) {
return res;
}
if (this.no == no) {
return this;
}
if (this.right != null) {
res = this.right.infixOrderSearch(no);
}
return res;
}
public HeroNode1 postOrderSearch(int no) {
HeroNode1 res = null;
if (this.left != null) {
res = this.left.postOrderSearch(no);
}
if (res != null) {
return res;
}
if (this.right != null) {
res = this.right.postOrderSearch(no);
}
if (res != null) {
return res;
}
//如果左右子树都没有找到,就比较当前节点
if (this.no == no) {
return this;
}
return null;
}
@Override
public String toString() {
return "HeroNode{" +
"name='" + name + '\'' +
'}';
}
}

节点的删除

public void delNode(int no) {
   if (this.left != null && this.left.no == no) {
       this.left = null;
       return;
   }
   if (this.right != null && this.right.no == no) {
       this.right = null;
       return;
   }
   if (this.left != null) {
       this.left.delNode(no);
   }
   if (this.right != null) {
       this.right.delNode(no);
   }
}
public void delNode(int no) {
   if (root != null) {
       if (root.no == no) {
           root = null;
       } else {
           root.delNode(no);
       }
   } else {
       System.out.println("空树，无法删除");
   }
}

Tags：

很赞哦！ ()

上一篇：哈希表(图文)

下一篇：顺序存储二叉树(图文)