java如何創(chuàng)建普通二叉樹

更新時(shí)間：2021年07月17日 12:05:35 作者：居十四

這篇文章主要介紹了java如何創(chuàng)建普通二叉樹的操作，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教

java創(chuàng)建二叉樹

這段時(shí)間一直在復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)的知識。

從最基礎(chǔ)的開始，實(shí)現(xiàn)一個(gè)普通的二叉樹。但發(fā)現(xiàn)也不那么簡單。因?yàn)橹皩W(xué)數(shù)據(jù)結(jié)構(gòu)時(shí)是用C語言寫的。

指針用來對結(jié)構(gòu)體的值操作比較好理解。但java沒有指針。

而Node節(jié)點(diǎn)在方法中傳遞的是地址。

如果直接對形參進(jìn)行new操作是錯(cuò)誤的。無法改變實(shí)參的值的。這一點(diǎn)坑了我很久，然后一頓查資料。

時(shí)隔很久，終于填上這個(gè)坑了

下面是以遞歸創(chuàng)建的二叉樹.還有一些常見的遍歷和樹的高度與樹的最大寬度.

一個(gè)方法不能修改一個(gè)基本數(shù)據(jù)類型的參數(shù)
一個(gè)方法可以修改一個(gè)對象參數(shù)的狀態(tài)
一個(gè)方法不能實(shí)現(xiàn)讓對象參數(shù)引用一個(gè)新對象（這句話在這里尤為適用）

代碼中的二叉樹如下圖

二叉樹

下面是非常簡單的實(shí)現(xiàn)

這里為了，后面的輸出格式，使用了JDK的動態(tài)代理。并寫了一個(gè)接口

package test.tree; 
public interface AbstractBinaryTree {
 void printPostOder(); 
 void printPostOderByRecursion(); 
 void printPreOder(); 
 void printPreOderByRecursion(); 
 void printInOderByRecursion(); 
 void printInOder(); 
 void printHeight(); 
 void printMaxWidth(); 
 void printLevelOrder();
}

主要的代碼

package test.tree; 
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
 
/**
 * 為了方便展示,并沒有將Node屬性私有
 */
 
class Node { 
	public String data;
	public Node left = null;
	public Node right = null;
	public boolean flag;
 
	Node(String data) {
		this.data = data;
	}
 
	Node() {
	} 
	@Override
	public String toString() { 
		return this.data;
	} 
}
 
public class BinaryTree implements AbstractBinaryTree{ 
	private Node root = new Node(); 
	public Node getRoot() {
		return root;
	}
 
	public void printNode(Node node) {
 
		if (node.data == null) {
			System.out.print("");
		} else {
			System.out.print(node.data);
		}
	}
 
	public BinaryTree(String tree) {
		String[] treeNodes = tree.split(",");
		createTreeByRecursion(treeNodes);
	}
 
	private int createTreeByRecursion(Node node, String[] treeNodes, int n) { 
		if ("#".equals(treeNodes[n]))
			return n + 1; 
		node.data = treeNodes[n]; 
		node.left = new Node();
		int left = createTreeByRecursion(node.left, treeNodes, n + 1); 
		node.right = new Node();
		int right = createTreeByRecursion(node.right, treeNodes, left); 
		return right;
	}
 
	public void createTreeByRecursion(String[] treeNodes) {
		createTreeByRecursion(root, treeNodes, 0);
	}
 
	/**
	 * 先序非遞歸創(chuàng)建
	 */
	public void createTree(String[] treeNodes) { 
		Stack<Node> stack = new Stack<>(); 
		int index = 0; 
		Node node = root; 
		while (index < treeNodes.length) { 
			while (true) {
 
				if ("#".equals(treeNodes[index])) {
 
					node = stack.pop();
 
					if (node.flag == false) {
						node.left = null;
						node.flag = true;
						stack.push(node);
					} else {
						node.right = null;
					}
 
					// 記得加1
					index++;
					break;
				}
 
				if (node.flag == true) {
					node.right = new Node();
					node = node.right;
				}
 
				node.data = treeNodes[index];
				stack.push(node);
				node.left = new Node();
				node = node.left;
				index++;
			}
 
			if (node.flag == false) {
				stack.push(node);
				node.flag = true;
				node = node.right;
			} else {
				node = stack.peek();
				node.flag = true;
			} 
		} 
	}
 
	// 遞歸調(diào)用的方法,需要將root傳遞進(jìn)去
	private void printPreOderByRecursion(Node node) { 
		if (node == null)
			return; 
		printNode(node);
		printPreOderByRecursion(node.left);
		printPreOderByRecursion(node.right); 
	}
 
	public void printPreOderByRecursion() { 
		printPreOderByRecursion(root);
	}
 
	private void printInOderByRecursion(Node node) {
 
		if (node == null)
			return;
 
		printInOderByRecursion(node.left);
		printNode(node);
		printInOderByRecursion(node.right); 
	}
 
	public void printInOderByRecursion() {
		printInOderByRecursion(root);
	}
 
	private void printPostOderByRecursion(Node node) {
 
		if (node == null)
			return; 
		printPostOderByRecursion(node.left);
		printPostOderByRecursion(node.right);
		printNode(node); 
	}
 
	public void printPostOderByRecursion() { 
		printPostOderByRecursion(root);
	}
 
	// 非遞歸遍歷二叉樹
 
	// 先序遍歷
	public void printPreOder() { 
		Stack<Node> stack = new Stack<>(); 
		Node tempNode = root; 
		while (true) { 
			while (tempNode != null) {
				printNode(tempNode);
				stack.push(tempNode);
				tempNode = tempNode.left;
			}
 
			if (stack.isEmpty()) {
				break;
			} 
			tempNode = stack.pop();
			tempNode = tempNode.right; 
		} 
	}
 
	// 中序遍歷
	public void printInOder() { 
		Stack<Node> stack = new Stack<>(); 
		Node tempNode = root;
 		while (true) { 
			while (tempNode != null) {
				stack.push(tempNode);
				tempNode = tempNode.left;
			}
 
			if (stack.isEmpty()) {
				break;
			}
			tempNode = stack.pop();
			printNode(tempNode);
			tempNode = tempNode.right; 
		} 
	}
 
	// 后序遍歷
	public void printPostOder() { 
		Stack<Node> stack = new Stack<>(); 
		Node tempNode = root; 
		while (true) {
 
			while (tempNode != null) {
				if (tempNode.flag == true) {
					tempNode = tempNode.right;
				} else {
					stack.push(tempNode);
					tempNode = tempNode.left;
				} 
			}
 
			tempNode = stack.pop(); 
			if (tempNode.flag == false) {
				stack.push(tempNode);
				tempNode.flag = true;
				tempNode = tempNode.right;
			} else {
				printNode(tempNode);
				if (stack.isEmpty()) {
					break;
				}
				tempNode = stack.peek();
				tempNode.flag = true;
			} 
		} 
	}
 
	// 層序遍歷 利用隊(duì)列
	public void printLevelOrder() { 
		Queue<Node> queue = new LinkedList<>(); 
		Node tempNode = root; 
		queue.offer(tempNode); 
		while (!queue.isEmpty()) { 
			Node topNode = queue.poll(); 
			if (topNode == null)
				continue; 
			printNode(topNode);
			queue.offer(topNode.left);
			queue.offer(topNode.right); 
		} 
	}
 
	// 樹高 遞歸，分別求出左子樹的深度、右子樹的深度，兩個(gè)深度的較大值+1
	public int getHeightByRecursion(Node node) { 
		if (node == null) {
			return 0;
		}
		int left = getHeightByRecursion(node.left);
		int right = getHeightByRecursion(node.right);
		return 1 + Math.max(left, right); 
	}
 
	/**
	 * 為什么不直接寫成調(diào)用 root,而是另寫一個(gè)方法去調(diào)用呢 因?yàn)?這樣可以不再為root,單獨(dú)設(shè)置一個(gè)臨時(shí)變量去存貯
	 * 而且也固定外部調(diào)用的方法,而不用關(guān)心內(nèi)部的實(shí)現(xiàn)
	 */
 
	public void printHeight() { 
		int height = getHeightByRecursion(root); 
		System.out.print(height);
	}
 
	// 利用層序遍歷,得到樹的最大寬度
	public void printMaxWidth() { 
		Queue<Node> queue = new LinkedList<>();
		Queue<Node> queueTemp = new LinkedList<>();
 
		int maxWidth = 1; 
		Node tempNode = root; 
		queue.offer(tempNode); 
		while (!queue.isEmpty()) { 
			while (!queue.isEmpty()) { 
				Node topNode = queue.poll(); 
				if (topNode == null)
					continue; 
				if (topNode.left.data != null) { 
					queueTemp.offer(topNode.left);
				}
 
				if (topNode.right.data != null) { 
					queueTemp.offer(topNode.right);
				} 
			}
 
			maxWidth = Math.max(maxWidth, queueTemp.size());
			queue = queueTemp;
			queueTemp = new LinkedList<>();
		} 
		System.out.print(maxWidth);
	} 
}

下面是寫的測試類

package test.tree; 
import java.lang.reflect.Proxy; 
public class BinaryTreeTest {
 
	public static void main(String[] args) {
		String treeStr = "A,B,D,#,#,#,C,#,E,#,#";
		// String treeStr = "A,#,#";
		AbstractBinaryTree binaryTree =  BinaryTreeTest.proxyBinaryTree(treeStr); 
		binaryTree.printPostOder();
		binaryTree.printPostOderByRecursion();
		binaryTree.printPreOder();
		binaryTree.printPreOderByRecursion();
		binaryTree.printInOderByRecursion();
		binaryTree.printInOder();
		binaryTree.printLevelOrder();
		binaryTree.printHeight();
		binaryTree.printMaxWidth();
	}
 
	public static AbstractBinaryTree proxyBinaryTree(String treeStr) {		
		AbstractBinaryTree binaryTree = new BinaryTree(treeStr); 
		Object newProxyInstance = Proxy.newProxyInstance(binaryTree.getClass().getClassLoader(),
				binaryTree.getClass().getInterfaces(), (proxy, method, args) -> {
					System.out.println(method.getName());
					Object invoke = method.invoke(binaryTree, args);
					System.out.println();
					return invoke;
				});
		
		return (AbstractBinaryTree) newProxyInstance;
	} 
}

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: