두 갈래 트리 차원, 선 루트, 후 루트, 인쇄 조작
6052 단어 알고리즘 학습
package pri.lr.java_tools.trees;
public class TreeNode {
private T value;
private TreeNode parent;
private TreeNode leftChild;
private TreeNode rightChild;
public TreeNode() {
}
public TreeNode(T value) {
this.value = value;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public TreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(TreeNode leftChild) {
this.leftChild = leftChild;
}
public TreeNode getRightChild() {
return rightChild;
}
public void setRightChild(TreeNode rightChild) {
this.rightChild = rightChild;
}
public void setInfo(T value, TreeNode leftChild, TreeNode rightChild){
this.value = value;
}
public void setChildren(T value, TreeNode leftChild, TreeNode rightChild){
this.leftChild = leftChild;
this.rightChild = rightChild;
}
}
두 갈래 트리 클래스 정의:
package pri.lr.java_tools.trees;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* ,
* @author 57721
*
*/
public class BinaryTree {
private TreeNode root = null;
private int treeNodeCount;
private Queue> notFullNodeQue = new LinkedList<>();
public BinaryTree(){}
/**
*
* @param value
* @return
*/
public boolean add(T value){
TreeNode oneNode = new TreeNode<>(value);
if(root == null) {
root = oneNode;
treeNodeCount++;
notFullNodeQue.add(root);
return true;
}
if(notFullNodeQue.peek().getLeftChild() == null) {
notFullNodeQue.peek().setLeftChild(oneNode);
notFullNodeQue.offer(oneNode);
treeNodeCount++;
return true;
}
if(notFullNodeQue.peek().getRightChild() == null) {
notFullNodeQue.peek().setRightChild(oneNode);
notFullNodeQue.offer(oneNode);
treeNodeCount++;
notFullNodeQue.poll();
}
return false;
}
public void printTreeByPreOrder(){
System.out.println(" :");
preOrder(root);
System.out.println();
}
public void printTreeByInOrder(){
System.out.println(" ");
InOrder(root);
System.out.println();
}
public void printTreeByPostOrder(){
System.out.println(" :");
postOrder(root);
System.out.println();
}
public void printTreeByLevel(){
System.out.println(" :");
if(root == null) {
return;
}
levelOrder();
System.out.println();
}
public void printTree(){
System.out.println(" ( ):");
printTree(root, 1);
System.out.println();
}
public void printTreeUpDown(){
System.out.println(" ( ):");
if(root == null) {
return;
}
int distance = (int) Math.pow(2, this.getHeight() -1) - 1;
List> list = new ArrayList<>();
list.add(root);
int pre = 0;// ,
int aft = 0;// ,
int idx = 0;
while(pre <= aft){
for(idx = pre, pre = aft + 1; idx < pre; idx++) {
printBlank(distance);
System.out.print(list.get(idx).getValue());
printBlank(distance);
System.out.print(" ");
if(list.get(idx).getLeftChild() != null) {
list.add(list.get(idx).getLeftChild());
aft++;
}
if(list.get(idx).getRightChild() != null) {
list.add(list.get(idx).getRightChild());
aft++;
}
}
System.out.println();
distance /= 2;
}
}
public int getNodeCount(){
return this.treeNodeCount;
}
public int getHeight(){
return (int) (Math.log(this.treeNodeCount)/Math.log(2) + 1);
}
private void printBlank(int k) {
for(int i = 0 ; i< k; i++) {
System.out.print(" ");
}
}
private void printTree(TreeNode root, int h){
if(root == null) return;
printTree(root.getRightChild(), h + 1);
for(int i = 0 ; i < h; i++) {
System.out.print(" ");
}
System.out.println(root.getValue());
printTree(root.getLeftChild(), h+1);
}
private void levelOrder() {
Queue> que = new LinkedList<>();
que.offer(root);
TreeNode current = null;
while(!que.isEmpty()){
current = que.poll();
System.out.print(current.getValue() + " ");
if(current.getLeftChild() != null) {
que.offer(current.getLeftChild());
}
if(current.getRightChild() != null) {
que.offer(current.getRightChild());
}
}
}
private void postOrder(TreeNode root2) {
if(root2 != null) {
postOrder(root2.getLeftChild());
postOrder(root2.getRightChild());
System.out.print(root2.getValue() + " ");
}
}
private void preOrder(TreeNode root1){
if(root1 != null) {
System.out.print(root1.getValue() + " ");
preOrder(root1.getLeftChild());
preOrder(root1.getRightChild());
}
}
private void InOrder(TreeNode root3){
if(root3 != null) {
InOrder(root3.getLeftChild());
System.out.print(root3.getValue() + " ");
InOrder(root3.getRightChild());
}
}
}
테스트 결과:
package pri.lr.java_tools.trees;
public class Demo {
public static void main(String[] args) {
BinaryTree oneTree = new BinaryTree<>();
oneTree.add("A");
oneTree.add("B");
oneTree.add("C");
oneTree.add("D");
oneTree.add("E");
oneTree.add("F");
oneTree.add("G");
oneTree.add("H");
oneTree.printTree();
oneTree.printTreeUpDown();
oneTree.printTreeByInOrder();
oneTree.printTreeByPreOrder();
oneTree.printTreeByPostOrder();
oneTree.printTreeByLevel();
}
}
결과:
( ):
G
C
F
A
E
B
D
H
( ):
A
B C
D E F G
H
H D B E A F C G
:
A B D H E C F G
:
H D E B F G C A
:
A B C D E F G H
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 매 결점의 왼쪽 아이와 오른쪽 아이를 교환하여 ~2020.8.13~ 학습노트두 갈래 체인 시계를 두 갈래 나무의 저장 구조로 삼아 두 갈래 나무의 각 결점의 왼쪽 아이와 오른쪽 아이를 교환한다. 두 갈래 나무의 순서를 입력하십시오.알림: 두 갈래 나무의 순서 서열은 문자열입니다. 문자가'#...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.