1.比较各种数据存储的方式
1) 数组存储方式分析
优点：通过下标的方式访问元素，速度快，对于有序数组，还可以使用二分查找提高检索速度。
缺点：如果要检索每个具体的值，或者插入之（按一定的顺序）会整体移动，效率低。
2）链式存储的方式分析：
优点：在一定程度上对数组的存储的方式有优化（例如：插入一个数值节点，只需要将插入节点，链接到链表中即可，删除效率也高）。
缺点：在进行检索时，效率仍然很低，（例如;要检索每个值时，需要从头开始遍历）。
3）数结构存储方式分析：
能提高数据存储、读取的效率。例如利用二叉排序树，既可以保证数据的检索速度，同时也可以保证数据的插入、删除、修改的速度。
2. 树结构示意图
数的常用术语：
1. 节点 2. 根节点 3 . 父节点 4. 子节点 5. 叶子节点 （没有子节点的节点） 6. 节点的权（节点的值）
7. 路径（从root 节点找到该节点的路径） 8 层 9 子树 10.数的高度 （最大层数） 11。森林：（多颗子树构成树林）
3.二叉树的概念
每个节点最多只能有两个子节点的一种形式称为二叉树。 二叉树的子节点分为左节点和右节点。
如果二叉树的所有叶子结点都在最后一层，并且节点总数=2^n -1, n为层数，则我们称为满二叉树。
如果二叉树的所有叶子节点都在最后一层，或者倒数第二层，而且最后一层的叶子结点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉数。
4. 二叉数遍历说明
使用前序、中序、后序对先下面的二叉数进行遍历
1） 前序遍历：先输出父节点，在遍历左子树和右子树。
2）中序遍历：先遍历左子树，在输出父节点，再遍历右子树。
3）后序遍历：先遍历左子树，在遍历右子树，最后输出父节点。
根据输出父节点的前后顺序，确定是前序、中序、后序
5 二叉树遍历应用实例（前序、中序、后序）思路分析。
6 代码实现
-
package BinaryTreeDemo;
-
-
public
class
BinaryTreeDemo {
-
public static void main(String[] args) {
-
//先需要创建一颗二叉树
-
BinaryTree binaryTree =
new BinaryTree();
-
//创建需要的节点
-
HeroNode root=
new HeroNode(
1,
"宋江");
-
HeroNode noed2=
new HeroNode(
2,
"吴用");
-
HeroNode noed3=
new HeroNode(
3,
"卢俊义");
-
HeroNode noed4=
new HeroNode(
4,
"林冲");
-
HeroNode noed5=
new HeroNode(
5,
"关胜");
-
-
//我们先手动创建二叉树
-
root.setLeft(noed2);
-
root.setRight(noed3);
-
noed3.setRight(noed4);
-
noed4.setLeft(noed5);
-
binaryTree.setRoot(root);
-
-
//测试
-
System.
out.println(
"前序遍历");
-
binaryTree.preOrder();
-
//测试
-
System.
out.println(
"中序遍历");
-
binaryTree.infixOrder();
-
//测试
-
System.
out.println(
"后序遍历");
-
binaryTree.postOrder();
-
}
-
}
-
-
//先创建HeroNode节点
-
class
HeroNode{
-
private
int no;
-
private String name;
-
private HeroNode left;
//默认 null
-
private HeroNode right;
//默认null
-
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 getLeft() {
-
return left;
-
}
-
-
public void setLeft(HeroNode left) {
-
this.left = left;
-
}
-
-
public HeroNode getRight() {
-
return right;
-
}
-
-
public void setRight(HeroNode right) {
-
this.right = right;
-
}
-
-
@
Override
-
public String
toString(
) {
-
return
"HeroNode{" +
-
"no=" + no +
-
", 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);
//先输出父节点
-
}
-
}
-
-
-
-
//定义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 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(
"二叉树为空，无法遍历");
-
}
-
}
-
}
-
-
-
转载：https://blog.csdn.net/weixin_45519487/article/details/106958826