二叉树的构造、非递归遍历、查找叶子节点【Java实现】

矫情吗；* 2022-05-14 13:59 168阅读 0赞

二叉树的构造方法不一，这里根据存储结点次序的数字关系来构造父节点和孩子结点的关系（parentIndex\*2+1==leftChildIndex，parentIndex\*2+2==leftRightIndex），关于二叉树非递归遍历的详细介绍请看 [二叉树的建立与遍历][Link 1]，下面程序还实现了查找叶子节点、查找某一元素是否存在的功能。

import java.util.LinkedList;
    import java.util.List;
    import java.util.Scanner;
    import java.util.Stack;
    
    public class TestBinaryTree {
    	private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    	private static List<Node> nodeList = null;
    
    	private static class Node {
    		int value;
    		Node leftChild;
    		Node rightChild;
    
    		public Node(int value) {
    			this.value = value;
    			leftChild = null;
    			rightChild = null;
    		}
    	}
    
    	/*
    	 * 将给定的数组元素作为节点赋值到链表nodeList， 然后按照 array.length/2-1 个父节点与其孩子节点在链表的下标关系，
    	 * 构造二叉树。注意最后一个父节点可能没有右孩子节点，需特殊处理。
    	 */
    	public Node createBinTree() {
    		nodeList = new LinkedList<Node>();
    		for (int i = 0; i < array.length; i++) {
    			nodeList.add(new Node(array[i]));
    		}
    		for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {
    			nodeList.get(parentIndex).leftChild = nodeList.get(parentIndex * 2 + 1);
    			nodeList.get(parentIndex).rightChild = nodeList.get(parentIndex * 2 + 2);
    		}
    
    		int lastParentIndex = array.length / 2 - 1;
    		nodeList.get(lastParentIndex).leftChild = nodeList.get(lastParentIndex * 2 + 1);
    		if (array.length % 2 == 1) {
    			nodeList.get(lastParentIndex).rightChild = nodeList.get(lastParentIndex * 2 + 2);
    		}
    		return nodeList.get(0);
    	}
    
    	/*
    	 * 0 对二叉树进行先根、中根和后根顺序深度地遍历并输出（非递归）, 这里借助栈来保存遍历过程中的节点
    	 */
    	public void preOderTraverse(Node root) {
    		if (root == null)
    			return;
    		Stack<Node> nodeStack = new Stack<>();
    		Node temp = root;
    		nodeStack.push(temp);
    		while (!nodeStack.isEmpty()) {
    			temp = nodeStack.pop();
    			if (temp != null) {
    				System.out.print(temp.value + " ");
    				nodeStack.push(temp.rightChild);
    				nodeStack.push(temp.leftChild);
    			}
    		}
    	}
    
    	public void inOderTraverse(Node root) {
    		if (root == null)
    			return;
    		Stack<Node> nodeStack = new Stack<>();
    		Node temp = root;
    		while ((temp != null) || (!nodeStack.empty())) {
    			while (temp != null) {
    				nodeStack.push(temp);
    				temp = temp.leftChild;
    			}
    			temp = nodeStack.pop();
    			System.out.print(temp.value + " ");
    			temp = temp.rightChild;
    		}
    	}
    
    	private void aftOderTraverse(Node root) {
    		if (root == null)
    			return;
    		Stack<Node> nodeStack = new Stack<>();
    		Node temp = root;
    		while ((temp != null) || (!nodeStack.empty())) {
    			while (temp != null) {
    				nodeStack.push(temp);
    				temp = temp.leftChild != null ? temp.leftChild : temp.rightChild;
    			}
    			temp = nodeStack.pop();
    			System.out.print(temp.value + " ");
    			if ((!nodeStack.empty()) && (temp == nodeStack.peek().leftChild)) {
    				temp = nodeStack.peek().rightChild;
    			} else {
    				temp = null;
    			}
    		}
    	}
    
    	/*
    	 * 统计二叉树的叶子节点个数并输出叶子节点的数据， 思路是递归地访问所有结点，判定其是否是叶子节点（有无孩子节点）
    	 */
    	public int findLeafNode(Node root) {
    		int count;
    		if (root == null)
    			count = 0;
    		else if ((root.leftChild == null) && (root.rightChild == null)) {
    			count = 1;
    			System.out.print(root.value + " ");
    		} else
    			count = findLeafNode(root.leftChild) + findLeafNode(root.rightChild);
    		return count;
    	}
    
    	/*
    	 * 查找某元素在二叉树中是否存在，是则输出1，否则输出0， 思路是按某种遍历顺序访问所有结点，查找是否存在给定元素
    	 */
    	public int findNode(Node root, int key) {
    		int flag = 0;
    		if (root == null)
    			return flag;
    		Stack<Node> nodeStack = new Stack<>();
    		Node temp = root;
    		nodeStack.push(temp);
    		while (!nodeStack.isEmpty()) {
    			temp = nodeStack.pop();
    			if (temp != null) {
    //				System.out.print(temp.value + " ");
    				if(temp.value==key) {
    					flag=1;
    					break;
    				}
    				nodeStack.push(temp.rightChild);
    				nodeStack.push(temp.leftChild);
    			}
    		}
    		return flag;
    	}
    
    	public static void main(String[] args) {
    		TestBinaryTree test = new TestBinaryTree();
    		Node root = test.createBinTree();
    		System.out.println("先根遍历：");
    		test.preOderTraverse(root);
    		System.out.println("\n中根遍历：");
    		test.inOderTraverse(root);
    		System.out.println("\n后根遍历：");
    		test.aftOderTraverse(root);
    		System.out.println("\n叶子节点：");
    		int count = test.findLeafNode(root);
    		System.out.println(" , 共有" + count + "个");
    		System.out.println("输入你要查找的元素：");
    		Scanner input=new Scanner(System.in);
    		int key=input.nextInt();
    		input.close();
    		System.out.println("结果："+test.findNode(root, key));
    	}
    }

二叉树样例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dub3NlZA_size_27_color_FFFFFF_t_70][]

运行截图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dub3NlZA_size_27_color_FFFFFF_t_70 1][]

[Link 1]: https://blog.csdn.net/gnosed/article/details/78462100
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dub3NlZA_size_27_color_FFFFFF_t_70]: /images/20220504/52c1bdced86846e6bc438658f0b27d2c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dub3NlZA_size_27_color_FFFFFF_t_70 1]: /images/20220504/ef8d0ef1d4f04d609906cde36606286e.png