1. 트리 구조
1.1 개념
트리는 n(n>=0)개의 제한된 노드로 구성된 계층적 관계의 집합인 비선형 데이터 구조입니다. 거꾸로 된 나무, 즉 뿌리가 위를 향하고 잎이 아래를 향하고 있기 때문에 나무라고 불립니다.
1.2 개념(중요)
a. 노드의 차수: 위와 같이 노드의 하위 트리 수: A의 차수는 6, J의 차수는 2
b입니다. 트리의 차수: 트리의 수, 가장 큰 노드의 차수는 위 그림에 표시된 대로 수의 차수입니다. 트리의 차수는 6
c입니다. 차수가 0인 노드(하위 트리가 없는 노드)
d. 부모 매듭 점/부모 노드: 위 그림과 같이: D는 H
의 부모 노드입니다. 자식 노드/자식 노드: 위 그림과 같습니다. : H는 D
e의 하위 노드입니다. 루트 노드: 위 그림과 같이 부모가 없는 노드: A
f. 노드의 수준: 루트 정의부터 시작합니다. 첫 번째 수준, 루트의 하위 노드는 두 번째 수준입니다.
g. 트리의 높이 또는 깊이: 위에 표시된 대로 트리의 최대 수준입니다. 4
2. 이진 트리(핵심)
2.1 개념
각 노드는 최대 2개의 하위 트리, 차수
2.2 이진 트리의 기본 형태
2.3 두 가지 유형 특수 이진 트리
a. 비자엽도는 2
b. 완전 이진 트리: 전체 이진 트리에 "오른쪽 하단 모서리"가 없습니다.
2.4 이진 트리의 속성
a. tree
1. 높이가 K이면 2^k-1개의 노드가 있습니다
2. 레벨이 K이면 레이어에 2^(k-1)개의 노드가 있습니다
3. 노드 수 - 1
4차수가 0인 n0과 2차가 있는 n2가 있으며, n0 = n2 + 1
b입니다. 올바른 자식이 있으면 반드시 있어야 합니다. 왼쪽 자식
2. 차수가 1인 노드는 하나만 있을 수 있습니다.2.5 이진 트리의 저장 이진 트리의 저장 구조는 연결 목록과 유사한 순차 저장과 연결 저장으로 나뉩니다. 순차 저장소: 완전한 이진 트리만 저장할 수 있습니다. 체인 저장소: 일반 이진 트리 이번에는 체인 저장소를 보여줍니다. 이진 트리의 체인 저장소는 노드별로 하나씩 참조됩니다. 삼항 표현,이 그림을 예로 들면, 세부 사항은 다음과 같습니다:
// 孩子表示法 private static class TreeNode{ char val; TreeNode left; TreeNode right; public TreeNode(char val) { this.val = val; } }초기화:
public static TreeNode build(){ TreeNode nodeA=new TreeNode('A'); TreeNode nodeB=new TreeNode('B'); TreeNode nodeC=new TreeNode('C'); TreeNode nodeD=new TreeNode('D'); TreeNode nodeE=new TreeNode('E'); TreeNode nodeF=new TreeNode('F'); TreeNode nodeG=new TreeNode('G'); TreeNode nodeH=new TreeNode('H'); nodeA.left=nodeB; nodeA.right=nodeC; nodeB.left=nodeD; nodeB.right=nodeE; nodeE.right=nodeH; nodeC.left=nodeF; nodeC.right=nodeG; return nodeA; }2.6 이진 트리의 기본 작업2.6.1 이진 트리 순회(재귀)1. NLR: 이전 선주문 탐색(선주문 탐색이라고도 함) - 루트 노드 ---> 루트의 왼쪽 하위 트리 ---> 루트의 오른쪽 하위 트리를 방문합니다.
//先序遍历 : 根左右 public static void preOrder(TreeNode root){ if(root==null){ return; } System.out.print(root.val+" "); preOrder(root.left); preOrder(root.right); }2. 중위 순회(Inorder Traversal)—> 루트의 왼쪽 하위 트리 ---> 루트의 오른쪽 하위 트리.
//中序遍历 public static void inOrder(TreeNode root){ if(root==null){ return; } preOrder(root.left); System.out.print(root.val+" "); preOrder(root.right); }3. 후위 순회 - 루트의 왼쪽 하위 트리 ---> 루트 노드의 오른쪽 하위 트리.
//后序遍历 public static void postOrder(TreeNode root){ if(root==null){ return; } preOrder(root.left); preOrder(root.right); System.out.print(root.val+" "); }2.6.2 이진 트리 순회(반복)1. 선순 순회
//方法2(迭代) //先序遍历 (迭代) public static void preOrderNonRecursion(TreeNode root){ if(root==null){ return ; } Deque<TreeNode> stack=new LinkedList<>(); stack.push(root); while (!stack.isEmpty()){ TreeNode cur=stack.pop(); System.out.print(cur.val+" "); if(cur.right!=null){ stack.push(cur.right); } if(cur.left!=null){ stack.push(cur.left); } } }2. 중순 순회
//方法2(迭代) //中序遍历 (迭代) public static void inorderTraversalNonRecursion(TreeNode root) { if(root==null){ return ; } Deque<TreeNode> stack=new LinkedList<>(); // 当前走到的节点 TreeNode cur=root; while (!stack.isEmpty() || cur!=null){ // 不管三七二十一,先一路向左走到根儿~ while (cur!=null){ stack.push(cur); cur=cur.left; } // 此时cur为空,说明走到了null,此时栈顶就存放了左树为空的节点 cur=stack.pop(); System.out.print(cur.val+" "); // 继续访问右子树 cur=cur.right; } }3. 이진 트리의 기본 연산1. 노드(재귀 및 반복)
//方法2(迭代) //后序遍历 (迭代) public static void postOrderNonRecursion(TreeNode root){ if(root==null){ return; } Deque<TreeNode> stack=new LinkedList<>(); TreeNode cur=root; TreeNode prev=null; while (!stack.isEmpty() || cur!=null){ while (cur!=null){ stack.push(cur); cur=cur.left; } cur=stack.pop(); if(cur.right==null || prev==cur.right){ System.out.print(cur.val+" "); prev=cur; cur=null; }else { stack.push(cur); cur=cur.right; } } }2 리프 노드 수 찾기(재귀 및 반복)
//方法1(递归) //传入一颗二叉树的根节点,就能统计出当前二叉树中一共有多少个节点,返回节点数 //此时的访问就不再是输出节点值,而是计数器 + 1操作 public static int getNodes(TreeNode root){ if(root==null){ return 0; } return 1+getNodes(root.left)+getNodes(root.right); } //方法2(迭代) //使用层序遍历来统计当前树中的节点个数 public static int getNodesNoRecursion(TreeNode root){ if(root==null){ return 0; } int size=0; Deque<TreeNode> queue=new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode cur = queue.poll(); size++; if (cur.left != null) { queue.offer(cur.left); } if (cur.right != null) { queue.offer(cur.right); } } return size; }3 k번째 레벨의 노드 수 찾기
//方法1(递归) //传入一颗二叉树的根节点,就能统计出当前二叉树的叶子结点个数 public static int getLeafNodes(TreeNode root){ if(root==null){ return 0; } if(root.left==null && root.right==null){ return 1; } return getLeafNodes(root.left)+getLeafNodes(root.right); } //方法2(迭代) //使用层序遍历来统计叶子结点的个数 public static int getLeafNodesNoRecursion(TreeNode root){ if(root==null){ return 0; } int size=0; Deque<TreeNode> queue=new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()){ TreeNode cur=queue.poll(); if(cur.left==null && cur.right==null){ size++; } if(cur.left!=null){ queue.offer(cur.left); } if(cur.right!=null){ queue.offer(cur.right); } } return size; }4. 5. 이진 트리 번호
//求出以root为根节点的二叉树第k层的节点个数 public static int getKLevelNodes(TreeNode root,int k){ if(root==null || k<=0){ return 0; } if(k==1){ return 1; } return getKLevelNodes(root.left,k-1)+getKLevelNodes(root.right,k-1); }2.7 이진 트리의 레벨 순서 탐색
//传入一个以root为根节点的二叉树,就能求出该树的高度 public static int height(TreeNode root){ if(root==null){ return 0; } return 1+ Math.max(height(root.left),height(root.right)); }에 값을 갖는 노드가 있는지 확인
위 내용은 Java의 이진 트리에 대한 기본 지식과 개념은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于结构化数据处理开源库SPL的相关问题,下面就一起来看一下java下理想的结构化数据处理类库,希望对大家有帮助。

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于PriorityQueue优先级队列的相关知识,Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,下面一起来看一下,希望对大家有帮助。

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于java锁的相关问题,包括了独占锁、悲观锁、乐观锁、共享锁等等内容,下面一起来看一下,希望对大家有帮助。

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于多线程的相关问题,包括了线程安装、线程加锁与线程不安全的原因、线程安全的标准类等等内容,希望对大家有帮助。

本篇文章给大家带来了关于Java的相关知识,其中主要介绍了关于关键字中this和super的相关问题,以及他们的一些区别,下面一起来看一下,希望对大家有帮助。

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于枚举的相关问题,包括了枚举的基本操作、集合类对枚举的支持等等内容,下面一起来看一下,希望对大家有帮助。

封装是一种信息隐藏技术,是指一种将抽象性函式接口的实现细节部分包装、隐藏起来的方法;封装可以被认为是一个保护屏障,防止指定类的代码和数据被外部类定义的代码随机访问。封装可以通过关键字private,protected和public实现。

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于设计模式的相关问题,主要将装饰器模式的相关内容,指在不改变现有对象结构的情况下,动态地给该对象增加一些职责的模式,希望对大家有帮助。


핫 AI 도구

Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

AI Hentai Generator
AI Hentai를 무료로 생성하십시오.

인기 기사

뜨거운 도구

에디트플러스 중국어 크랙 버전
작은 크기, 구문 강조, 코드 프롬프트 기능을 지원하지 않음

맨티스BT
Mantis는 제품 결함 추적을 돕기 위해 설계된 배포하기 쉬운 웹 기반 결함 추적 도구입니다. PHP, MySQL 및 웹 서버가 필요합니다. 데모 및 호스팅 서비스를 확인해 보세요.

안전한 시험 브라우저
안전한 시험 브라우저는 온라인 시험을 안전하게 치르기 위한 보안 브라우저 환경입니다. 이 소프트웨어는 모든 컴퓨터를 안전한 워크스테이션으로 바꿔줍니다. 이는 모든 유틸리티에 대한 액세스를 제어하고 학생들이 승인되지 않은 리소스를 사용하는 것을 방지합니다.

드림위버 CS6
시각적 웹 개발 도구

PhpStorm 맥 버전
최신(2018.2.1) 전문 PHP 통합 개발 도구
