侧边栏壁纸
博主头像
孔子说JAVA博主等级

成功只是一只沦落在鸡窝里的鹰,成功永远属于自信且有毅力的人!

  • 累计撰写 285 篇文章
  • 累计创建 125 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

二叉排序树实例讲解

孔子说JAVA
2019-11-04 / 0 评论 / 0 点赞 / 73 阅读 / 15,005 字 / 正在检测是否收录...

1、二叉排序树性质

二叉排序树也是一棵二叉树,所谓二叉树,就是“任何节点最多只允许两个子节点”,这两个子节点称为左右子节点。如下便是一个二叉树。

image-1649580788678

  • 1、若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  • 2、若它的右子树不空,则右子树上所有节点的值均大于其根节点的值。
  • 3、换句话说就是:任何节点的键值一定大于其左子树中的每一个节点的键值,并小于其右子树中的每一个节点的键值。

如下便是一颗二叉排序树:

image-1649580836832

2、二叉树排序的基本原理

使用第一个元素作为根节点,如果之后的元素比第一个小,则放到左子树,否则放到右子树,之后按中序遍历。

二叉树的遍历方式有三种, 前序、中序、后序

  • 前序(先序)遍历顺序: 根节点、左子树、右子树

  • 中序遍历顺序:左子树、根节点、右子树

  • 后序遍历顺序:左子树、右子树、根节点

3、二叉树节点定义

public class TreeNode {

	// 左节点
	private TreeNode lefTreeNode;
	// 右节点
	private TreeNode rightNode;
	// 数据
	private int value;

	private boolean isDelete;

	public TreeNode getLefTreeNode() {
		return lefTreeNode;
	}

	public void setLefTreeNode(TreeNode lefTreeNode) {
		this.lefTreeNode = lefTreeNode;
	}

	public TreeNode getRightNode() {
		return rightNode;
	}

	public void setRightNode(TreeNode rightNode) {
		this.rightNode = rightNode;
	}

	public int getValue() {
		return value;
	}

	public void setValue(int value) {
		this.value = value;
	}

	public boolean isDelete() {
		return isDelete;
	}

	public void setDelete(boolean isDelete) {
		this.isDelete = isDelete;
	}

	public TreeNode() {
		super();
	}

	public TreeNode(int value) {
		this(null, null, value, false);
	}

	public TreeNode(TreeNode lefTreeNode, TreeNode rightNode, int value, boolean isDelete) {
		super();
		this.lefTreeNode = lefTreeNode;
		this.rightNode = rightNode;
		this.value = value;
		this.isDelete = isDelete;
	}

	@Override
	public String toString() {
		return "TreeNode [lefTreeNode=" + lefTreeNode + ", rightNode=" + rightNode + ", value=" + value + ", isDelete="
				+ isDelete + "]";
	}

	public void display() {  
        System.out.print(this.value + "\t");  
    }  
}

4、二叉树定义

public class BinaryTree {

	// 根节点
	private TreeNode root;

	public TreeNode getRoot() {
		return root;
	}

	/**
	 * 插入操作
	 * 
	 * @param value
	 */
	public void insert(int value) {

		TreeNode newNode = new TreeNode(value);

		if (root == null) {
			root = newNode;
			root.setLefTreeNode(null);
			root.setRightNode(null);
		} else {

			TreeNode currentNode = root;
			TreeNode parentNode;

			while (true) {

				parentNode = currentNode;
				// 往右放
				if (newNode.getValue() > currentNode.getValue()) {
					currentNode = currentNode.getRightNode();
					if (currentNode == null) {
						parentNode.setRightNode(newNode);
						return;
					}
				} else {
					// 往左放
					currentNode = currentNode.getLefTreeNode();
					if (currentNode == null) {
						parentNode.setLefTreeNode(newNode);
						return;
					}
				}
			}
		}
	}

	/**
	 * 查找
	 * 
	 * @param key
	 * @return
	 */
	public TreeNode find(int key) {
		TreeNode currentNode = root;
		if (currentNode != null) {
			while (currentNode.getValue() != key) {
				if (currentNode.getValue() > key) {
					currentNode = currentNode.getLefTreeNode();
				} else {
					currentNode = currentNode.getRightNode();
				}

				if (currentNode == null) {
					return null;
				}

			}

			if (currentNode.isDelete()) {
				System.out.println(key + "已被假删除");
				return null;
			} else {
				System.out.println(key + "已被找到");
				return currentNode;
			}
		} else {
			System.out.println(key + "未被找到");
			return null;
		}

	}

	/**
	 * //中序遍历(递归): 1、调用自身来遍历节点的左子树 2、访问这个节点 3、调用自身来遍历节点的右子树 先序(前序): 根节点、左子树、右子树
	 * 中序:左子树、根节点、右子树 后序:左子树、右子树、根节点
	 */
	public void inOrderTraverse() {
		System.out.print("中序遍历:");
		inOrder(root);
		System.out.println();
	}

	/**
	 * 中序遍历(递归): 1、调用自身来遍历节点的左子树 2、访问这个节点 3、调用自身来遍历节点的右子树 先序(前序): 根节点、左子树、右子树
	 * 中序:左子树、根节点、右子树 后序:左子树、右子树、根节点
	 * 
	 * @param treeNode
	 */
	public void inOrder(TreeNode treeNode) {
		if (treeNode != null && treeNode.isDelete() == false) {
			inOrder(treeNode.getLefTreeNode());
			treeNode.display();
			inOrder(treeNode.getRightNode());
		}
	}

	/**
	 * 中序非递归遍历: 1)对于任意节点current,若该节点不为空则将该节点压栈,并将左子树节点置为current,重复此操作,直到current为空。
	 * 2)若左子树为空,栈顶节点出栈,访问节点后将该节点的右子树置为current 3) 重复1、2步操作,直到current为空且栈内节点为空。
	 * 先序(前序): 根节点、左子树、右子树 中序:左子树、根节点、右子树 后序:左子树、右子树、根节点
	 */
	public void inOrderByStack() {
		System.out.print("中序非递归遍历:");
		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode current = root;
		while (current != null || !stack.isEmpty()) {
			while (current != null) {
				stack.push(current);
				current = current.getLefTreeNode();
			}

			if (!stack.isEmpty()) {
				current = stack.pop();
				current.display();
				current = current.getRightNode();
			}
		}
		System.out.println();
	}

	/**
	 * //前序遍历(递归): 1、访问这个节点 2、调用自身来遍历节点的左子树 3、调用自身来遍历节点的右子树 先序(前序): 根节点、左子树、右子树
	 * 中序:左子树、根节点、右子树 后序:左子树、右子树、根节点
	 */
	public void preOrderTraverse() {
		System.out.print("前序遍历:");
		preOrderTraverse(root);
		System.out.println();
	}

	private void preOrderTraverse(TreeNode node) {
		if (node == null)
			return;
		node.display();
		preOrderTraverse(node.getLefTreeNode());
		preOrderTraverse(node.getRightNode());
	}

	/**
	 * 前序非递归遍历:
	 * 1)对于任意节点current,若该节点不为空则访问该节点后再将节点压栈,并将左子树节点置为current,重复此操作,直到current为空。
	 * 2)若左子树为空,栈顶节点出栈,将该节点的右子树置为current 3) 重复1、2步操作,直到current为空且栈内节点为空。 先序(前序):
	 * 根节点、左子树、右子树 中序:左子树、根节点、右子树 后序:左子树、右子树、根节点
	 */
	public void preOrderByStack() {
		System.out.print("前序非递归遍历:");
		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode current = root;
		while (current != null || !stack.isEmpty()) {
			while (current != null) {
				stack.push(current);
				current.display();
				current = current.getLefTreeNode();
			}

			if (!stack.isEmpty()) {
				current = stack.pop();
				current = current.getRightNode();
			}
		}
		System.out.println();
	}

	/**
	 * //后序遍历(递归): 1、调用自身来遍历节点的左子树 2、调用自身来遍历节点的右子树 3、访问这个节点 先序(前序): 根节点、左子树、右子树
	 * 中序:左子树、根节点、右子树 后序:左子树、右子树、根节点
	 */
	public void postOrderTraverse() {
		System.out.print("后序遍历:");
		postOrderTraverse(root);
		System.out.println();
	}

	private void postOrderTraverse(TreeNode node) {
		if (node == null)
			return;

		postOrderTraverse(node.getLefTreeNode());
		postOrderTraverse(node.getRightNode());
		node.display();
	}

	public int getMinValue() {
		TreeNode current = root;
		while (true) {
			if (current.getLefTreeNode() == null)
				return current.getValue();
			current = current.getLefTreeNode();
		}
	}

	public int getMaxValue() {
		TreeNode current = root;
		while (true) {
			if (current.getRightNode() == null)
				return current.getValue();
			current = current.getRightNode();
		}
	}

	/**
	 * 
	 * 得到后继节点,即删除节点的左后代
	 */
	private TreeNode getSuccessor(TreeNode delNode) {
		TreeNode successor = delNode;
		TreeNode successorParent = null;
		TreeNode current = delNode.getRightNode();

		while (current != null) {
			successorParent = successor;
			successor = current;
			current = current.getLefTreeNode();
		}

		// 如果后继节点不是删除节点的右子节点时,
		if (successor != delNode.getRightNode()) {
			// 要将后继节点的右子节点指向后继结点父节点的左子节点,
			successorParent.setLefTreeNode(successor.getRightNode());
			// 并将删除节点的右子节点指向后继结点的右子节点
			successor.setRightNode(delNode.getRightNode());
		}
		// 任何情况下,都需要将删除节点的左子节点指向后继节点的左子节点
		successor.setLefTreeNode(delNode.getLefTreeNode());
		return successor;
	}

	/**
	 * 删除节点
	 * @param value
	 * @return
	 */
	public boolean delete(int value) {
		System.out.println("删除节点: "+value);
		TreeNode current = root; // 需要删除的节点
		TreeNode parent = null; // 需要删除的节点的父节点
		boolean isLeftChild = true; // 需要删除的节点是否父节点的左子树

		while (true) {
			if (value == current.getValue()) {
				break;
			} else if (value < current.getValue()) {
				isLeftChild = true;
				parent = current;
				current = current.getLefTreeNode();
			} else {
				isLeftChild = false;
				parent = current;
				current = current.getRightNode();
			}

			// 找不到需要删除的节点,直接返回
			if (current == null)
				return false;
		}

		// 分情况考虑
		// 1、需要删除的节点为叶子节点
		if (current.getLefTreeNode() == null && current.getRightNode() == null) {
			// 如果该叶节点为根节点,将根节点置为null
			if (current == root) {
				root = null;
			} else {
				// 如果该叶节点是父节点的左子节点,将父节点的左子节点置为null
				if (isLeftChild) {
					parent.setLefTreeNode(null);
				} else { // 如果该叶节点是父节点的右子节点,将父节点的右子节点置为null
					parent.setRightNode(null);
				}
			}
		}
		// 2.1、需要删除的节点有一个子节点,且该子节点为左子节点
		else if (current.getRightNode() == null) {
			// 如果该节点为根节点,将根节点的左子节点变为根节点
			if (current == root) {
				root = current.getLefTreeNode();
			} else {
				// 如果该节点是父节点的左子节点,将该节点的左子节点变为父节点的左子节点
				if (isLeftChild) {
					parent.setLefTreeNode(current.getLefTreeNode());
				} else { // 如果该节点是父节点的右子节点,将该节点的左子节点变为父节点的右子节点
					parent.setRightNode(current.getLefTreeNode());
				}
			}
		}
		// 2.2、需要删除的节点有一个子节点,且该子节点为右子节点
		else if (current.getLefTreeNode() == null) {
			// 如果该节点为根节点,将根节点的右子节点变为根节点
			if (current == root) {
				root = current.getRightNode();
			} else {
				// 如果该节点是父节点的左子节点,将该节点的右子节点变为父节点的左子节点
				if (isLeftChild) {
					parent.setLefTreeNode(current.getRightNode());
				} else { // 如果该节点是父节点的右子节点,将该节点的右子节点变为父节点的右子节点
					parent.setRightNode(current.getRightNode());
				}
			}
		}
		// 3、需要删除的节点有两个子节点,需要寻找该节点的后续节点替代删除节点
		else {
			TreeNode successor = getSuccessor(current);
			// 如果该节点为根节点,将后继节点变为根节点,并将根节点的左子节点变为后继节点的左子节点
			if (current == root) {
				root = successor;
			} else {
				// 如果该节点是父节点的左子节点,将该节点的后继节点变为父节点的左子节点
				if (isLeftChild) {
					parent.setLefTreeNode(successor);
				} else { // 如果该节点是父节点的右子节点,将该节点的后继节点变为父节点的右子节点
					parent.setRightNode(successor);
				}
			}
		}
		current = null;
		return true;
	}

	public static void main(String[] args) {

		BinaryTree tree = new BinaryTree();
		// 添加数据测试
		tree.insert(30);
		tree.insert(50);
		tree.insert(10);
		tree.insert(40);
		tree.insert(20);
		tree.insert(3);
		tree.insert(49);
		tree.insert(13);

		System.out.println("root = " + tree.getRoot().getValue());
		// 排序测试
		tree.inOrderTraverse();
		tree.preOrderTraverse();
		tree.postOrderTraverse();
		// 查找测试
		tree.find(10);
		// 删除测试
//		tree.find(40).setDelete(true);
		tree.find(40);
		System.out.println("最小值:" + tree.getMinValue() + ",最大值:" + tree.getMaxValue());
		tree.inOrderTraverse();
		tree.delete(3); // 删除叶子节点
		tree.inOrderTraverse();
		tree.preOrderTraverse();
		tree.postOrderTraverse();
		tree.delete(50); // 删除只有一个左子节点的节点
//		tree.delete(248); // 删除只有一个右子节点的节点
//		tree.delete(248); // 删除只有一个右子节点的节点
//		tree.delete(580); // 删除有两个子节点的节点,且后继节点为删除节点的右子节点的左后代
//		tree.delete(888); // 删除有两个子节点的节点,且后继节点为删除节点的右子节点
//		tree.delete(52); // 删除有两个子节点的节点,且删除节点为根节点
		tree.inOrderTraverse();
		tree.preOrderTraverse();
		tree.postOrderTraverse();
	}
}

// root = 30
// 中序遍历:3	10	13	20	30	40	49	50	
// 前序遍历:30	10	3	20	13	50	40	49	
// 后序遍历:3	13	20	10	49	40	50	30	
// 10已被找到
// 40已被找到
// 最小值:3,最大值:50
// 中序遍历:3	10	13	20	30	40	49	50	
// 删除节点: 3
// 中序遍历:10	13	20	30	40	49	50	
// 前序遍历:30	10	20	13	50	40	49	
// 后序遍历:13	20	10	49	40	50	30	
// 删除节点: 50
// 中序遍历:10	13	20	30	40	49	
// 前序遍历:30	10	20	13	40	49	
// 后序遍历:13	20	10	49	40	30	

5、二叉排序树的查找

5.1 二叉排序树查找最大最小值

要在二叉树中找出查找最大最小元素是极简单的事情,从根节点一直往左走,直到无路可走就可得到最小值;从根节点一直往右走,直到无路可走,就可以得到最大值。

// 查找最小值
public int getMinValue() {
	TreeNode current = root;
	while (true) {
		if (current.getLefTreeNode() == null)
			return current.getValue();
		current = current.getLefTreeNode();
	}
}

// 查找最大值
public int getMaxValue() {
	TreeNode current = root;
	while (true) {
		if (current.getRightNode() == null)
			return current.getValue();
		current = current.getRightNode();
	}
}

5.2 二叉排序树查找单个元素

// 二叉排序树查找单个元素
public TreeNode find(int key) {
	TreeNode currentNode = root;
	if (currentNode != null) {
		while (currentNode.getValue() != key) {
			if (currentNode.getValue() > key) {
				currentNode = currentNode.getLefTreeNode();
			} else {
				currentNode = currentNode.getRightNode();
			}

			if (currentNode == null) {
				return null;
			}
		}
		if (currentNode.isDelete()) {
			return null;
		} else {
			return currentNode;
		}

	} else {
		return null;
	}
}

6、二叉排序树插入

插入新元素时,可以从根节点开始,遇键值较大者就向左,遇键值较小者就向右,一直到末端,就是插入点。

image-1649581298926

// 二叉排序树插入新数据
public void insert(int value) {
	TreeNode newNode = new TreeNode(value);

	if (root == null) {
		root = newNode;
		root.setLefTreeNode(null);
		root.setRightNode(null);
	} else {

		TreeNode currentNode = root;
		TreeNode parentNode;

		while (true) {

			parentNode = currentNode;
			// 往右放
			if (newNode.getValue() > currentNode.getValue()) {
				currentNode = currentNode.getRightNode();
				if (currentNode == null) {
					parentNode.setRightNode(newNode);
					return;
				}
			} else {
				// 往左放
				currentNode = currentNode.getLefTreeNode();
				if (currentNode == null) {
					parentNode.setLefTreeNode(newNode);
					return;
				}
			}
		}
	}
}

7、二叉排序树删除

对于二叉排序树中的节点A,对它的删除分为两种情况:

  • 1)删除节点A为叶子节点,即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构,则可以直接删除此子结点。

image-1649581363522

  • 2)删除节点A只有一个子节点:只有一个左子节点或只有一个右子节点,就直接将A的子节点连至A的父节点上,并将A删除;

image-1649581378450

  • 3)删除节点有两个子节点:这种情况比较复杂,需要寻找后继节点,即比要删除的节点的关键值次高的节点是它的后继节点。说得简单一些,后继节点就是比要删除的节点的关键值要大的节点集合中的最小值。(右子节点的左后代)
/**
 * 得到后继节点,即删除节点的左后代
 */
private TreeNode getSuccessor(TreeNode delNode) {
	TreeNode successor = delNode;
	TreeNode successorParent = null;
	TreeNode current = delNode.getRightNode();

	while (current != null) {
		successorParent = successor;
		successor = current;
		current = current.getLefTreeNode();
	}

	// 如果后继节点不是删除节点的右子节点时,
	if (successor != delNode.getRightNode()) {
		// 要将后继节点的右子节点指向后继结点父节点的左子节点,
		successorParent.setLefTreeNode(successor.getRightNode());
		// 并将删除节点的右子节点指向后继结点的右子节点
		successor.setRightNode(delNode.getRightNode());
	}
	// 任何情况下,都需要将删除节点的左子节点指向后继节点的左子节点
	successor.setLefTreeNode(delNode.getLefTreeNode());
	return successor;
}
  • a)如果后继节点是刚好是要删除节点的右子节点

image-1649581437626

  • b)如果后继节点为要删除节点的右子节点的左后代:

image-1649581844994

删除节点代码

public boolean delete(int value) {
	System.out.println("删除节点: "+value);
	TreeNode current = root; // 需要删除的节点
	TreeNode parent = null; // 需要删除的节点的父节点
	boolean isLeftChild = true; // 需要删除的节点是否父节点的左子树

	while (true) {
		if (value == current.getValue()) {
			break;
		} else if (value < current.getValue()) {
			isLeftChild = true;
			parent = current;
			current = current.getLefTreeNode();
		} else {
			isLeftChild = false;
			parent = current;
			current = current.getRightNode();
		}
		// 找不到需要删除的节点,直接返回
		if (current == null)
			return false;
	}

	// 分情况考虑
	// 1、需要删除的节点为叶子节点
	if (current.getLefTreeNode() == null && current.getRightNode() == null) {
		// 如果该叶节点为根节点,将根节点置为null
		if (current == root) {
			root = null;
		} else {
			// 如果该叶节点是父节点的左子节点,将父节点的左子节点置为null
			if (isLeftChild) {
				parent.setLefTreeNode(null);
			} else { // 如果该叶节点是父节点的右子节点,将父节点的右子节点置为null
				parent.setRightNode(null);
			}
		}
	}
	// 2.1、需要删除的节点有一个子节点,且该子节点为左子节点
	else if (current.getRightNode() == null) {
		// 如果该节点为根节点,将根节点的左子节点变为根节点
		if (current == root) {
			root = current.getLefTreeNode();
		} else {
			// 如果该节点是父节点的左子节点,将该节点的左子节点变为父节点的左子节点
			if (isLeftChild) {
				parent.setLefTreeNode(current.getLefTreeNode());
			} else { // 如果该节点是父节点的右子节点,将该节点的左子节点变为父节点的右子节点
				parent.setRightNode(current.getLefTreeNode());
			}
		}
	}
	// 2.2、需要删除的节点有一个子节点,且该子节点为右子节点
	else if (current.getLefTreeNode() == null) {
		// 如果该节点为根节点,将根节点的右子节点变为根节点
		if (current == root) {
			root = current.getRightNode();
		} else {
			// 如果该节点是父节点的左子节点,将该节点的右子节点变为父节点的左子节点
			if (isLeftChild) {
				parent.setLefTreeNode(current.getRightNode());
			} else { // 如果该节点是父节点的右子节点,将该节点的右子节点变为父节点的右子节点
				parent.setRightNode(current.getRightNode());
			}
		}
	}
	// 3、需要删除的节点有两个子节点,需要寻找该节点的后续节点替代删除节点
	else {
		TreeNode successor = getSuccessor(current);
		// 如果该节点为根节点,将后继节点变为根节点,并将根节点的左子节点变为后继节点的左子节点
		if (current == root) {
			root = successor;
		} else {
			// 如果该节点是父节点的左子节点,将该节点的后继节点变为父节点的左子节点
			if (isLeftChild) {
				parent.setLefTreeNode(successor);
			} else { // 如果该节点是父节点的右子节点,将该节点的后继节点变为父节点的右子节点
				parent.setRightNode(successor);
			}
		}
	}
	current = null;
	return true;
}

8、二叉排序树遍历

二叉排序树遍历分为:先序(前序)、中序、后序。

  1. 前序遍历顺序为:根节点、左子树、右子树;
  2. 中序遍历顺序为:左子树、根节点、右子树;
  3. 后序遍历顺序为:左子树、右子树、根节点。其中中序遍历为升序排列。

8.1 中序遍历代码

/**
 * 中序遍历(递归): 
 * 1、调用自身来遍历节点的左子树 2、访问这个节点 3、调用自身来遍历节点的右子树 
 */
public void inOrderTraverse() {
	System.out.print("中序遍历:");
	inOrder(root);
	System.out.println();
}

/**
 * 中序遍历(递归): 
 * 1、调用自身来遍历节点的左子树 2、访问这个节点 3、调用自身来遍历节点的右子树 
 * 
 * @param treeNode
 */
public void inOrder(TreeNode treeNode) {
	if (treeNode != null && treeNode.isDelete() == false) {
		inOrder(treeNode.getLefTreeNode());
		treeNode.display();
		inOrder(treeNode.getRightNode());
	}
}

/**
 * 中序非递归遍历: 
 * 1)对于任意节点current,若该节点不为空则将该节点压栈,并将左子树节点置为current,重复此操作,直到current为空。
 * 2)若左子树为空,栈顶节点出栈,访问节点后将该节点的右子树置为current 3) 重复1、2步操作,直到current为空且栈内节点为空。
 */
public void inOrderByStack() {
	System.out.print("中序非递归遍历:");
	Stack<TreeNode> stack = new Stack<TreeNode>();
	TreeNode current = root;
	while (current != null || !stack.isEmpty()) {
		while (current != null) {
			stack.push(current);
			current = current.getLefTreeNode();
		}
		if (!stack.isEmpty()) {
			current = stack.pop();
			current.display();
			current = current.getRightNode();
		}
	}
	System.out.println();
}

8.2 前序遍历代码

/**
 * 前序遍历(递归): 
 * 1、访问这个节点 2、调用自身来遍历节点的左子树 3、调用自身来遍历节点的右子树 
 */
public void preOrderTraverse() {
	System.out.print("前序遍历:");
	preOrderTraverse(root);
	System.out.println();
}

private void preOrderTraverse(TreeNode node) {
	if (node == null)
		return;
	node.display();
	preOrderTraverse(node.getLefTreeNode());
	preOrderTraverse(node.getRightNode());
}

/**
 * 前序非递归遍历:
 * 1)对于任意节点current,若该节点不为空则访问该节点后再将节点压栈,并将左子树节点置为current,重复此操作,直到current为空。
 * 2)若左子树为空,栈顶节点出栈,将该节点的右子树置为current 3) 重复1、2步操作,直到current为空且栈内节点为空。 
 */
public void preOrderByStack() {
	System.out.print("前序非递归遍历:");
	Stack<TreeNode> stack = new Stack<TreeNode>();
	TreeNode current = root;
	while (current != null || !stack.isEmpty()) {
		while (current != null) {
			stack.push(current);
			current.display();
			current = current.getLefTreeNode();
		}
		if (!stack.isEmpty()) {
			current = stack.pop();
			current = current.getRightNode();
		}
	}
	System.out.println();
}

8.3 后续遍历代码

/**
 * 后序遍历(递归): 
 * 1、调用自身来遍历节点的左子树 2、调用自身来遍历节点的右子树 3、访问这个节点 
 */
public void postOrderTraverse() {
	System.out.print("后序遍历:");
	postOrderTraverse(root);
	System.out.println();
}

private void postOrderTraverse(TreeNode node) {
	if (node == null)
		return;
	postOrderTraverse(node.getLefTreeNode());
	postOrderTraverse(node.getRightNode());
	node.display();
}
0

评论区