java 二叉树的深度优先遍历_java实现二叉树的排序树、深度优先遍历和广度优先遍历...

「爱情、让人受尽委屈。」 2022-11-02 11:44 227阅读 0赞

实现了二叉树的深度和广度优先遍历

深度优先遍历：

对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。而二叉树的深度优先遍历分为先序遍历，中序遍历和后续遍历。

先序遍历：先访问根，在访问左子树，最后访问右子树，总结就是“根左右”；

中序遍历：先访问左子树，再访问根，最后访问右子树，总结就是“左根右”；

后序遍历：先访问左子树，再访问右子树，最后访问根，总结就是“左右根”；

通常采用递归的方式实现遍历，非递归方式需要结合栈(后进先出)的特点实现。

广度优先遍历：

又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右(也可以从右往左)访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。

广度优先遍历的非递归的通用做法是采用队列(先入先出)。

![68bfdf3476ef0c6acd06a67b23f67ce1.gif][]

用该图来理解深度优先遍历和广度优先遍历：

深度优先遍历：该图为一个无向图，假设我们从A开始进行深度优先搜索，第二点可以是B、C、D中任意一个，假设访问的是B，那么路径为A - B - E，搜索完成后直接退回B，搜索其下一个子节点，完成B之后退到A，搜索C节点，以此类推，直到找出需要的解。

广度优先遍历：假设从A开始探索，第二点可以是B、C、D中任意一个，假设访问的是B，那么接下来再从C、D中选择一个，假设最终的路线是A-B-C-D，然后同理再去遍历B、C、D的子节点，直到所有的点都被遍历鼓过。

二叉排序树：

二叉排序树是一种特殊的二叉树，其树的根节点的左侧总是小于根节点，节点的右侧总是大于根节点。如下图所示。

图解两种遍历算法：

![68bfdf3476ef0c6acd06a67b23f67ce1.gif][]

该图为输入了：35 20 15 16 29 28 30 40 50 45 55之后生成的二叉排序树。

先序遍历(递归)：35 20 15 16 29 28 30 40 50 45 55

中序遍历(递归)：15 16 20 28 29 30 35 40 45 50 55

后序遍历(递归)：16 15 28 30 29 20 45 55 50 40 35

先序遍历(非递归)：35 20 15 16 29 28 30 40 50 45 55

中序遍历(非递归)：15 16 20 28 29 30 35 40 45 50 55

后序遍历(非递归)：16 15 28 30 29 20 45 55 50 40 35

广度优先遍历：35 20 40 15 29 50 16 28 30 45 55

程序实现(有注解，不懂的地方可以留言)：

/\*\*

\*实体类

\*/

public class Tree \{

Tree treeLeft;

Tree treeRight;//创建了树的两个分支，声明类型自己本身树，目的是每新建一个分支依旧为树的一个节点

int data;

Tree(int data)\{

this.data = data;//data在这里是树节点(或分支)的值

treeLeft = treeRight = null;

/\*\*

\*运行主程序

\*/

public class TreeMain \{

/\*\*

\* 二叉排序树；左边是小于等于，右边是大于根节点。

\* @param root

\* @param data

\* @return

\*/

public static Tree insert(Tree root, int data) \{

if (root == null) \{

return new Tree(data);//新建树节点

\}else \{

Tree cur;

if (data <= root.data) \{//小的放在左侧

cur = insert(root.treeLeft,data);//递归一直到root为空时，调用第一个IF实现新建树节点

root.treeLeft = cur;

\}else \{//大的放在右侧

cur = insert(root.treeRight,data);

root.treeRight = cur;

return root;

/\*\*

\* 深度优先遍历分为，先序、中序和后序遍历

\*/

/\*\*

\* 递归法实现先序遍历，并打印

\* @param root

\*/

public static void preOrder(Tree root)\{

if(root == null) return;

System.out.print(root.data + " ");

preOrder(root.treeLeft);

preOrder(root.treeRight);

/\*\*

\* 递归法实现中序遍历，并打印

\* @param root

\*/

public static void inOrder(Tree root)\{

if(root == null) return;

inOrder(root.treeLeft);//用递归的方法一直找到树的最左侧

System.out.print(root.data + " ");

inOrder(root.treeRight);

/\*\*

\* 递归方法实现后序遍历，并打印

\* @param root

\*/

public static void postOrder(Tree root)\{

if(root == null) return;

postOrder(root.treeLeft);

postOrder(root.treeRight);

System.out.print(root.data + " ");

/\*\*

\* 非递归方法实现先序遍历，并打印

\* @param root

\*/

public static void preOrder2(Tree root)\{

LinkedList stack = new LinkedList<>();

Tree currentRoot = null;

stack.push(root);

while (!stack.isEmpty())\{

currentRoot = stack.pop();

System.out.print(currentRoot.data + " ");

//栈是先入后出，需要先入栈右分支

if (currentRoot.treeRight != null)\{

stack.push(currentRoot.treeRight);

if (currentRoot.treeLeft != null)\{

stack.push(currentRoot.treeLeft);

/\*\*

\* 非递归方法实现中序遍历，并打印

\* @param root

\*/

public static void inOrder2(Tree root)\{

LinkedList stack = new LinkedList<>();

Tree currentRoot = root;

while (currentRoot !=null || !stack.isEmpty())\{

//遍历到二叉树的最左侧

while (currentRoot != null)\{

stack.push(currentRoot);

currentRoot = currentRoot.treeLeft;

currentRoot = stack.pop();

System.out.print(currentRoot.data + " ");

currentRoot = currentRoot.treeRight;

/\*\*

\* 非递归方法实现后序遍历，并打印

\* @param root

\*/

public static void postOrder2(Tree root)\{

LinkedList stack = new LinkedList<>();

Tree currentRoot = root;

Tree rightRoot = null;

while (currentRoot != null || !stack.isEmpty())\{

while (currentRoot != null)\{

stack.push(currentRoot);

currentRoot = currentRoot.treeLeft;

currentRoot = stack.pop();

//当前节点没有右节点或上一个结点(已经输出的结点)是当前结点的右结点，则输出当前结点

while (currentRoot.treeRight == null || currentRoot.treeRight == rightRoot)\{

System.out.print(currentRoot.data + " ");

rightRoot = currentRoot;

if (stack.isEmpty())\{

return;

currentRoot = stack.pop();

stack.push(currentRoot);//还有未遍历的右侧节点

currentRoot = currentRoot.treeRight;

/\*\*

\* 对列法实现二叉树广度优先遍历，队列遵循先进先出的规则，适合本方法

\* @param root

\*/

public static void levelOrer(Tree root)\{

Queue queue = new LinkedList();//新增队列

if(root != null)\{

queue.add(root);//将根节点加入队列

while (!queue.isEmpty())\{

Tree cur = queue.peek();//创建cur的目的是在while循环的时候逐层将树带入，如果直接用root,会导致只能输出一级树

System.out.print(cur.data + " ");

queue.remove();

if (cur.treeLeft != null)\{

queue.add(cur.treeLeft);//先将左分支加入队列，之后先输出

if(cur.treeRight != null)\{

queue.add(cur.treeRight);

/\*\*

\* main函数，输入输出，遍历

\* @param args

\*/

public static void main(String\[\] args) \{

Scanner sc = new Scanner(System.in);

System.out.println("请输入数字的个数：");

int T = sc.nextInt();

int\[\] t = new int\[T\];

System.out.println("请输入数字，以空格分隔：");

for (int i = 0; i < T; i++) \{

t\[i\] = sc.nextInt();

Tree root = null;

for (int i = 0; i < T; i++) \{

root = insert(root,t\[i\]);

System.out.println("递归先序遍历：");

preOrder(root);

System.out.println();

System.out.println("递归中序遍历：");

inOrder(root);

System.out.println();

System.out.println("递归后序遍历：");

postOrder(root);

System.out.println();

System.out.println("非递归先序遍历：");

preOrder2(root);

System.out.println();

System.out.println("非递归中序遍历：");

inOrder2(root);

System.out.println();

System.out.println("非递归后序遍历：");

postOrder2(root);

System.out.println();

System.out.println("广度优先遍历：");

levelOrer(root);

运行结果：

![68bfdf3476ef0c6acd06a67b23f67ce1.gif][]

[68bfdf3476ef0c6acd06a67b23f67ce1.gif]: /images/20221024/231ad1dee1de48eca9739f5df17477ad.png

java 二叉树的深度优先遍历_java实现二叉树的排序树、深度优先遍历和广度优先遍历...

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关完全二叉树的深度优先、广度优先遍历的实现

相关二叉树的深度优先遍历与广度优先遍历

相关 java 二叉树的深度优先遍历_java实现二叉树的排序树、深度优先遍历和广度优先遍历...

相关二叉树与深度优先遍历

相关树的遍历-深度优先遍历和广度优先遍历

相关二叉树遍历——深度优先遍历、广度优先遍历

相关二叉树的深度优先遍历

相关二叉树的深度优先遍历和广度优先遍历

相关二叉树的深度优先遍历和广度优先遍历

相关二叉树的深度优先和广度优先遍历