项目合作网站,宽带营销策略,比较好的外贸网站,网站快照优化公司概述
图1: 图2: 上图帮大家温习完全二叉树的概念#xff0c;本文讲的是完全顺序二叉树的初始化
华为的员工、考过华为OD的员工、参加过其他类似大厂的考试的员工一般做过二叉树的初始化#xff0c;甚至有些还碰到过手撕代码时面试官要求做二叉树遍历#xff0c;看完本文的…概述
图1: 图2: 上图帮大家温习完全二叉树的概念本文讲的是完全顺序二叉树的初始化
华为的员工、考过华为OD的员工、参加过其他类似大厂的考试的员工一般做过二叉树的初始化甚至有些还碰到过手撕代码时面试官要求做二叉树遍历看完本文的读者我相信一定能拿到比较高的评分尽管手撕的时候面试官一般不会要你关心二叉树的动态构造只要写初始化一个固定的树跑过测试就行。
对华为或华为OD感兴趣的同学可以参看文章
华为OD入门级、工作级、专业级技术技能知识点要求及职级薪资表
Java初始化顺序二叉树
百度AI初始化顺序二叉树 百度AI生成的代码分析
1、buildTree方法明显逻辑错误
理由左节点如果是index*21那么根节点就应该是0而实际root又是用1初始化的。
其他的我就不详细分析了核心逻辑都错了结果一定也是错的
读者可以亲自在百度上试验。并在本地用其代码验证。 作者初始化顺序二叉树
在这之前先给大家看一下我们传奇人物塔子哥的题库中的这一道题
完全二叉树非叶子部分后序遍历(100分) - Problem Detail - CodeFun2000
可能需要付费不过没关系作者截图出来 额作者代码注释中也有原题下面看作者代码实现
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;/*** Description: #P2988. 完全二叉树非叶子部分后序遍历(100分*
给定一个以顺序储存结构存储整数值的完全二叉树序列最多1000个整数请找出此完全二叉树的所有非叶子节点部分然后采用后序遍历方式将此部分树不包含叶子输出。
只有一个节点的树此节点认定为根节点非叶子。
此完全二叉树并非满二叉树可能存在倒数第二层出现叶子或者无右叶子的情况
其他说明二叉树的后序遍历是基于根来说的遍历顺序为左-右-根输入描述
一个通过空格分割的整数序列字符串
输出描述
非叶子部分树结构。备注输出数字以空格分隔样例1
输入
1 2 3 4 5 6 7
输出
2 3 1
说明
找到非叶子部分树结构然后采用后序遍历输出。1/ \2 3/ \ / \4 5 6 7/ \ / \ / \ / \8 9 10 11 12 13 14 15* Author: Dand* CreateDate: 2025/6/22 22:06* Version: 1.0*/
public class Main {public static void main(String args[]){Scanner sc new Scanner(System.in);int[] arr Arrays.stream(sc.nextLine().split(\\ )).mapToInt(Integer::parseInt).toArray();Node root new Root(arr);// 后序遍历StackNode stack new StackNode();while (true){if (root ! null){stack.push(root);root root.getLeft();} else {if (stack.isEmpty())return;if (null stack.peek().getRight()) {// 叶子root stack.pop();
// System.out.print(root.getData() ); // 不打叶子while (root stack.peek().getRight()) {root stack.pop();System.out.print(root.getData() ); // 只打非叶子if (stack.isEmpty()) {break;}}}if (!stack.isEmpty())root stack.peek().getRight();elseroot null;}}}
}class NodeT {public T data;public NodeT left;public NodeT right;Node(T e){data e;}public T getData() {return data;}public void setData(T data) {this.data data;}public NodeT getLeft() {return left;}public NodeT getRight() {return right;}public void setLeft(NodeT node){this.left node;}public void setRight(NodeT node){this.right node;}
}class Root extends Node {public Integer data;public NodeInteger left;public NodeInteger right;Root(int[] arr){// size 一定要大于0super(arr[0]);int size arr.length;if (size 0) {data arr[0]; // 根节点是数组第一个值buildTree( this, 1, size , arr);}}/**** param node* param index 从1开始* param size* param arr*/private void buildTree(Node node, int index, int size, int[] arr) {if ( index * 2 size ) {node.left new Node(arr[index * 2-1] ); // 左子节点值是 2*index 1buildTree( node.left, index * 2, size, arr ); // 递归构建左子树if (index * 2 1 size) { // 如果有右子节点node.right new Node(arr[index * 2] ); // 右子节点值是2*index 2buildTree( node.right, index * 2 1, size, arr ); // 递归构建右子树}}}
}
代码走读
1、作者将用户输入读入int[]中
2、实际输入不一定是连续的数字
3、如果是连续数字这行用值 index*2初始化即可
node.left new Node(arr[index * 2-1] );
因数组索引是0开始所以以第1个左子节点为例第2个节点值在整型数组中的索引就是1遵循AI开始的逻辑构建ROOT的子树时传的index为1所以上面 index * 2-1刚好是1输入的数组中第二个数arr[index * 2-1]
4、作者树采用先创建了一个能用的父类不用场景可实现不同的子类
5、本题中data只是个简单的整型值解决实际问题如saas平台健康度的决策树因然健康度一般为多叉树逻辑有些不一样也差不了多少时读者可以把子类中的data换成数据对象
6、本题要求后序遍历所以作者使用栈实现了后序遍历
7、相比递归栈占用更少的cpu和内存。
8、本题要求不打印叶子所以只要注释掉内部while循环前的那边打印语句 if (null stack.peek().getRight()) {// 叶子root stack.pop();
// System.out.print(root.getData() ); // 不打叶子while (root stack.peek().getRight()) {root stack.pop();System.out.print(root.getData() ); // 只打非叶子if (stack.isEmpty()) {break;}}}
递归
简单
先序 /*** 递归先序遍历* param root*/private void priOrderWithRecursion(BinaryTreeNode root) {if (null ! root) {System.out.print(root.getValue() \t);priOrderWithRecursion(root.getLeftChild());priOrderWithRecursion(root.getRightChild());}}
后序 /*** 递归后序遍历* param root*/private void postOrderWithRecursion(BinaryTreeNode root) {if (null ! root) {postOrderWithRecursion(root.getLeftChild());postOrderWithRecursion(root.getRightChild());System.out.print(root.getValue() \t);}}
中序 /*** 递归中序遍历* param root*/private void inOrderWithRecursion(BinaryTreeNode root) {if (null ! root) {inOrderWithRecursion(root.getLeftChild());System.out.print(root.getValue() \t);inOrderWithRecursion(root.getRightChild());}}
栈非递归
占更少的计算资源更好的性能
先序 /*** 非递归先序遍历虽然是采用栈的方式但是并未完全应用栈的思想采取循环过程中输出的方式来遍历* param root*/private void preOrder(BinaryTreeNode root) {StackBinaryTreeNode stack new Stack();while (null ! root || !stack.isEmpty()) {while (null ! root) {System.out.print(root.getValue() \t);stack.push(root);root root.getLeftChild();}if (!stack.isEmpty()) {root stack.pop();root root.getRightChild();}}} 后序 见上面 作者初始化顺序二叉树 章节的代码包含了后序遍历。
中序 /*** 非递归中序遍历* param root*/private void inOrder(BinaryTreeNode root) {StackBinaryTreeNode stack new Stack();while (null ! root || !stack.isEmpty()) {while (null ! root) {stack.push(root);root root.getLeftChild();}if (!stack.isEmpty()) {root stack.pop();System.out.print(root.getValue() \t);root root.getRightChild();}}} 二叉树的概念
二叉树是一种每个节点最多有两个子树的树结构广泛应用于计算机科学领域是数据结构中最基本且重要的非线性存储形式之一。其核心特征包括递归定义、有序性和节点度限制不超过2。
基本定义
二叉树Binary Tree是由节点构成的有限集合该集合要么为空要么由一个根节点及其两棵互不相交的子树组成分别称为左子树和右子树。这两棵子树同样遵循二叉树的定义形成递归结构。
关键特性
节点度限制每个节点的子节点数不超过2区别于普通树结构。有序性即使节点数量相同左右子树的顺序不同也会被视为不同的二叉树。递归定义子树本身也是二叉树允许通过递归算法高效处理。
常见类型
满二叉树所有非叶子节点均有左右子树且所有叶子节点在同一层。完全二叉树除最后一层外其他层节点数达到最大值且最后一层节点从左向右连续排列。
