이진 트리 란 무엇입니까? 여기서 소개하지 않겠습니다. 바이두어 : 바이너리 트리를 사용할 수 있습니다. 여기서 Java를 사용하여 "발현 바이너리 트리"를 구현하십시오.
표현식 바이너리 트리의 정의
첫 번째 단계는 표현 바이너리 트리가 무엇인지 이해하는 것입니다. 예를 들어, 표현 : (a+b × (cd)) -E/F. 잎 노드에 숫자를 넣고 분기 노드에 연산자가 이진 트리를 형성합니다. 표현을 저장하기 때문에 "발현 바이너리 트리"라고합니다.
어린이 부츠는 이것이 어떻게 지어 졌는지 궁금할까요? 예를 들어 45+23*56/2-5를 가져갑니다. 먼저 첫 번째 숫자 45를 꺼내 잎 노드에 넣으십시오. "+"를 만나면 분기 노드에 넣으십시오.
그런 다음 "23", "*", "56", "/"및 "2"를 순서대로 넣습니다.
마지막으로 "-"-"5",
그것은 대략적으로입니다. (나는이 사진들을 직접 그렸다. 못 생겼어
표현식 바이너리 트리를 만들기위한 단계
1. 노드 객체를 만듭니다.
2. 연산자와 데이터를 구별하고 해당 목록 (대기열)에 저장하십시오.
3. 새 번호 노드를 형성하기 위해 처음 두 숫자와 연산자를 꺼내십시오.
4. 연산자가 완료 될 때까지 3 단계를 반복하십시오.
5. 루트 노드를 마지막 노드와 동일하게하십시오.
발현 바이너리 트리 구현
먼저 데이터, 왼쪽 하위 트리, 오른쪽 하위 트리 및 여러 세트를 포함하여 노드 객체 클래스를 빌드하고 메소드를 얻으십시오.
패키지 tets0714;/** * 노드 객체 클래스 * @author yuxiu * */public class node {// 데이터 개인 문자열 데이터; // 왼쪽 하위 트리 개인 노드 lchild; // 오른쪽 하위 트리 개인 노드 rchild; node () {} 노드 (문자열 data) {this.data = data; } 노드 (문자열 데이터, 노드 lchild, 노드 rchild) {super (); this.data = 데이터; this.lchild = lchild; this.rchild = rchild; } public String getData () {return data; } public node getLchild () {return lchild; } public node getRchild () {return rchild; }}그런 다음 표현 바이너리 트리를 만듭니다.
패키지 tets0714; import java.util.arraylist;/** * 표현식 이진 트리 클래스 * @author yuxiu * */public class formaluetree {private string s = ""; 개인 노드 루트; // 루트 노드/*** 표현식 바이너리 트리 만들기* @param str expression*/public void creattree (string str) {// 배열 목록을 선언, 저장 연산자, 추가, 빼기, 곱셈 및 부서, ArrayList <String> OperatorList = new ArrayList <string> (); // 배열 목록, 노드 데이터 저장, ArrayList <Node> numlist = new ArrayList <Node> (); // 먼저 연산자와 데이터를 구별하고 (int i = 0; i <str.length (); i ++)에 해당 목록에 저장하십시오. {char ch = str.charat (i); // (ch> = '0'&& ch <= '9') {s+= ch; } else {numlist.add (새 노드 (S)); s = ""; OperatorList.add (ch+""); }} // 마지막 숫자를 숫자 노드 numlist.add에 추가합니다 (새 노드 (s)); while (operlist.size ()> 0) {// 3 단계, 연산자가 완료 될 때까지 두 번째 단계를 반복하고, 두 번째 숫자와 연산자를 꺼내 새 번호 노드 노드 왼쪽 = numlist.remove (0)를 형성합니다. 노드 오른쪽 = numlist.remove (0); 문자열 연산자 = OperatorList.remove (0); 노드 노드 = 새 노드 (조작, 왼쪽, 오른쪽); numlist.add (0, 노드); // 새 노드를 첫 번째 노드로 선호하고 index = 0 인 이전 노드가 index = 1}으로 변경됩니다. 4 단계, 루트 노드가 마지막 노드 root = numlist.get (0)와 동일하게하십시오. } / *** 출력 노드 데이터* / public void output () {output (root); // 루트 노드에서 트래버스를 중지}/*** 출력 노드 데이터* @param node*/public void output (node node) {if (node.getLchild ()! = null) {// 리프 노드 인 경우 출력 (node.getLchild ()); } system.out.print (node.getData ()); // 트랜잭션은 선주문 트래버스 (루트 왼쪽 및 오른쪽), 인 주문형 트래버스 (왼쪽 루트 오른쪽) 및 우편 주문형 트래버스 (왼쪽 루트 오른쪽) if (node.getRchild ()! = null) {output (node.getRchild ()); }} public static void main (string [] args) {formaluetree tree = new formaluetree (); tree.creattree ( "45+23*56/2-5"); // 표현식 트리의 이진 트리를 만듭니다. output (); // 출력 verification}} 마지막으로 콘솔에서 "45+23*56/2-5"를 출력 할 수 있습니다. 여기에 사용 된 중간 주문 트래버스에서 친구들은 선주문 트래버스 및 우편 주문형 트래버스를 사용하는 효과가 무엇인지 시도 할 수 있습니다. Traversal은 나중에 그것에 대해 이야기 할 것입니다.
위는이 기사의 모든 내용입니다. 모든 사람의 학습에 도움이되기를 바랍니다. 모든 사람이 wulin.com을 더 지원하기를 바랍니다.