Java教程

日撸代码300行:第25天(二叉树深度遍历的栈实现 (中序))

本文主要是介绍日撸代码300行:第25天(二叉树深度遍历的栈实现 (中序)),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

代码来自闵老师”日撸 Java 三百行(21-30天)“,链接:https://blog.csdn.net/minfanphd/article/details/116975721

package datastructure.stack;

/**
 * 
 * Object stack.
 * 
 * @author WX873
 *
 */

public class ObjectStack {
	
	/**
	 * The depth.
	 */
	public static final int MAX_DEPTH = 10;
	
	/**
	 * The data.
	 */
	Object[] data;
	
	/**
	 * The actual depth. 
	 */
	int depth;
	
	/**
	 * construct an empty char stack.
	 */
	public ObjectStack() {
		// TODO Auto-generated constructor stub
		depth = 0;
	    data = new Object[MAX_DEPTH];
 	}//of the first constructor
	
	/**
	 * ***********************************************************
	 * Overrides the method claimed in Object, the superclass of any class.
	 * ***********************************************************
	 */
	public String toString() {
		String resultString = "";
		
		if (depth == 0) {
			System.out.println("The stack is empty!");
			return null;
		}//of if
		for (int i = 0; i < depth; i++) {
			resultString += data[i] + ", ";
		}//of for i
		return resultString;
	}//of toString
	
	/**
	 * **************************************************************
	 * Push an element.
	 * 
	 * @param paraObject  The given Object.
	 * @return Push success or not.
	 * **************************************************************
	 */
	public boolean push(Object paraObject) {
		if (depth == MAX_DEPTH) {
			System.out.println("Stack full.");
			return false;
		}//of if
		data[depth] = paraObject;
		depth++;
		
		return true;
	}//of push
	
	/**
	 * *************************************************************
	 * Pop an element.
	 * 
	 * @return The Object at the top of the stack.
	 * *************************************************************
	 */
	public Object pop() {
		if (depth == 0) {
			System.out.println("No element to pop!");
			return '\0';
		}//of if
		
		depth--;
		return data[depth];
	}//of pop
	
	/**
	 * ************************************************************
	 * Is the stack empty?
	 * 
	 * @return True, if empty.
	 * ************************************************************
	 */
	public boolean isEmpty() {
		if (depth == 0) {
			System.out.println("The stack is empty!");
			return true;
		}//of if
		return false;
	}//of isEmpty
	
	/**
	 * ************************************************************
	 * The entrance of the program.
	 * 
	 * @param args  Not used now.
	 * ************************************************************
	 */
	public static void main(String args[]) {
		ObjectStack tempStack = new ObjectStack();
		
		for (char ch = 'a'; ch < 'm'; ch++) {
			 tempStack.push(new Character(ch));
			System.out.println("The current stack is: " + tempStack.toString());
		}//of for ch
		
		char tempChar;
		for (int i = 0; i < 12; i++) {
			tempChar = ((Character)tempStack.pop()).charValue();
			System.out.println("Poped: " + tempChar);
			System.out.println("The current stack is: " + tempStack.toString());
		}//of for i
		
	}//of main

}//of ObjectStack

这里自己写代码的时候,将pop()中的if语句里的返回值写成了“return null;”,结果运行的时候就报错。网上查了一下,‘\0’表示空字符。相当于这里还是有返回值,只是返回值为空字符。
return null;方法的返回值必须不是原始数据类型(封装类除外)和void。return 就是跳出方法;return null也是跳出方法并返回null。不要认为null就是没有值,null就是值。
原始类型 | 封装类
boolean | Boolean
char | Character
byte | Byte
short | Short
int | Integer
long | Long
float | Float
double | Double
关于原始类型与原始封装类的介绍:https://www.cnblogs.com/wisdo/p/4915774.html

/**
	 * ******************************************************
	 * In-order visit with stack.
	 * ******************************************************
	 */
	public void inOrderVisitWithStack() {
		ObjectStack tempStack = new ObjectStack();
		BinaryCharTree tempNode = this;
		
		while (!tempStack.isEmpty() || tempNode != null) {
			if (tempNode != null) {
				tempStack.push(tempNode);
				tempNode = tempNode.leftChild;
			} else {
				tempNode = (BinaryCharTree) tempStack.pop();
				System.out.println("" + tempNode.value + "");
				tempNode = tempNode.rightChild;
			}
		}//of while
		
	}//of inOrderVisitWithStack
	
	/**
	 * *********************************************************
	 * The entrance of the program.
	 * 
	 * @param args  Not used now
	 * *********************************************************
	 */
	public static void main(String args[]) {
		BinaryCharTree tempTree = manualConstructTree();
		
		System.out.println("\r\nPre-order visit:");
		tempTree.preOrderVisit();
		
		System.out.println("\r\nIn-order visit:");
		tempTree.inOrderVisit();
		
		System.out.println("\r\nPost-order visit:");
		tempTree.postOrderVisit();
		
		int tempDepth = tempTree.getDepth();
		System.out.println("\nThe depth is: " + tempDepth);
		
		System.out.println("\rThe number of nodes for the binary tree is: " + tempTree.getNumNodes());
		
		tempTree.toDataArrays();
		System.out.println("The values are: " + Arrays.toString(tempTree.valueArray));
		System.out.println("The indices are: " + Arrays.toString(tempTree.indicesArray));
		
		tempTree.toDataArraysObjectQueue();
		System.out.println("Only object queue.");
	   	System.out.println("The values are: " + Arrays.toString(tempTree.valueArray));
	   	System.out.println("The indices are: " + Arrays.toString(tempTree.indicesArray));
	   	
		tempTree.toDataArrayGenericQueue();
		System.out.println("Generic queue.");
	   	System.out.println("The values are: " + Arrays.toString(tempTree.valueArray));
	   	System.out.println("The indices are: " + Arrays.toString(tempTree.indicesArray));
	   	
	   	//char[] tempCharArray = {'A','B','C','D','E','F'};
	   	//int[] tempIndicesArray = {0, 1, 2, 4, 5, 12};
	   	char[] tempCharArray = {'a','b','c','d','e','f','g'};
	   	int[] tempIndicesArray = {0, 1, 2, 4, 5, 9, 10};
	   	BinaryCharTree tempTree2 = new BinaryCharTree(tempCharArray, tempIndicesArray);
	   	
		System.out.println("\r\nPre-order visit:");
		tempTree2.preOrderVisit();	
		System.out.println("\r\nIn-order visit:");
		tempTree2.inOrderVisit();
		System.out.println("\r\nPost-order visit:");
		tempTree2.postOrderVisit();
		
		System.out.println("\r\nIn-order visit with stack:");
		tempTree2.inOrderVisitWithStack();

	}//of main

inOrderVisitWithStack()的设计思路相当巧妙,用一个while循环同时实现了入栈和出栈;入栈后指向左孩子节点,出栈后指向右孩子节点。

这篇关于日撸代码300行:第25天(二叉树深度遍历的栈实现 (中序))的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!