【数据结构】之二叉树

雁字回时

发布于 2022-12-13 18:54:08

3330

发布于 2022-12-13 18:54:08

文章被收录于专栏：安卓随笔

一、二叉树的定义

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。

一棵深度为k，且有2^k-1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。

二、二叉树的实现

本篇文章主要讲一下二叉树的实现，以及遍历方法（递归与非递归）包括前序、中序、后序。

1、节点类Node

这边我其实用一个内部类简单实现了一下二叉树的节点定义。

private class BinaryTreeNode {
		private BinaryTreeNode left = null;  //左节点
		private BinaryTreeNode right = null; //右节点

		private String data;
		private int key;

		public BinaryTreeNode(int key, String data) {
			this.data = data;
			this.left = null;
			this.right = null;
		}

		public String getData() {
			return data;
		}

		public void setData(String data) {
			this.data = data;
		}

		public BinaryTreeNode getLeft() {
			return left;
		}

		public void setLeft(BinaryTreeNode left) {
			this.left = left;
		}

		public BinaryTreeNode getRight() {
			return right;
		}

		public void setRight(BinaryTreeNode right) {
			this.right = right;
		}
	}

2、创建二叉树

	public void createTree() {
		//自己创建节点，用于组成二叉树
		BinaryTreeNode newNodeB = new BinaryTreeNode(2, "B");
		BinaryTreeNode newNodeC = new BinaryTreeNode(3, "C");
		BinaryTreeNode newNodeD = new BinaryTreeNode(4, "D");
		BinaryTreeNode newNodeE = new BinaryTreeNode(5, "E");
		BinaryTreeNode newNodeF = new BinaryTreeNode(6, "F");
		BinaryTreeNode newNodeG = new BinaryTreeNode(7, "G");
		BinaryTreeNode newNodeH = new BinaryTreeNode(8, "H");
		BinaryTreeNode nodes[] = { root, newNodeB, newNodeC, newNodeD,
				newNodeE, newNodeF, newNodeG, newNodeH };
        //这是根据二叉树的定义，第i个节点的子节点为i * 2 + 1和i * 2 + 2
		for (int i = 0; i < nodes.length / 2 - 1; i++) {
			nodes[i].setLeft(nodes[i * 2 + 1]);
			nodes[i].setRight(nodes[i * 2 + 2]);
		}
        //最后一个节点需要单独考虑，因为如果节点总数为奇数那么最后一个为右子节点，反正偶数为左子节点
		int lastIndex = nodes.length / 2 - 1;
		if (nodes.length % 2 == 1) {
			nodes[lastIndex].setRight(nodes[lastIndex * 2 + 2]);
		} else {
			nodes[lastIndex].setLeft(nodes[lastIndex * 2 + 1]);
		}
	}

3、递归遍历算法

3.1 前序

    // 递归遍历 前序
	public void preOrder(BinaryTreeNode node) {
		if (node == null)
			return;
		System.out.print(node.getData());
		preOrder(node.getRight());
		preOrder(node.getLeft());
	}

3.2 中序

    // 递归遍历 中序
	public void inOrder(BinaryTreeNode node) {
		if (node != null) {
			inOrder(node.getLeft());
			System.out.print(node.getData());
			inOrder(node.getRight());
		}
	}

3.3 后序

    // 递归遍历 后序
	public void backOrder(BinaryTreeNode node) {
		if (node != null) {
			backOrder(node.getLeft());
			backOrder(node.getRight());
			System.out.print(node.getData());
		}
	}

其实从上面的三个方法，大家可以看到，就是三句话换个顺序。换句话说就是打印的那句话换位置：前序放前面，中序放中间，后序放后面。

4、非递归遍历算法

4.1 前序

    // 非递归遍历 前序
	public void preorderNoRec(BinaryTreeNode node) {
		Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
		BinaryTreeNode tempNode = node;
		while (tempNode != null || stack.size() > 0) {
			while (tempNode != null) {
				System.out.print(tempNode.getData());
				stack.push(tempNode);
				tempNode = tempNode.getLeft();
			}
			if (stack.size() > 0) {
				tempNode = stack.pop();
				tempNode = tempNode.getRight();
			}
		}
	}

从根节点开始，然后把左子树放入stack，同时打印出顺序。然后再查找右子树。

4.2 中序

    // 非递归遍历 中序
	public void inOrderNoRec(BinaryTreeNode node) {
		Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
		BinaryTreeNode tempNode = node;
		while (tempNode != null || stack.size() > 0) {
			while (tempNode != null) {
				stack.push(tempNode);
				tempNode = tempNode.getLeft();
			}
			if (stack.size() > 0) {
				tempNode = stack.pop();
				System.out.print(tempNode.getData());
				tempNode = tempNode.getRight();
			}
		}
	}

这个和前序的区别就在于利用了Stack后进先出的特性。后入栈的左子树先打印再到根节点，最后右子树。

4.3 后序

    // 非递归遍历 后序
	public void backOrderNoRec(BinaryTreeNode node) {
		Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
		BinaryTreeNode tempNode = node;
		while (node != null) {
			for (; node.getLeft() != null; node = node.getLeft())
				stack.push(node);
			while (node != null
			    && (node.getRight() == null || node.getRight() == tempNode)) {
				System.out.print(node.getData());
				tempNode = node;
				if (stack.empty())
					return;
				node = stack.pop();
			}
			stack.push(node);
			node = node.getRight();
		}
	}

后序和前两个区别比较多，先把左子树放入stack，通过判断是否含有右子树，含有就先打印左子节点，再放入stack，打印其右节点。其实最后就形成了先把节点的子节点都打印在打印父节点。而根节点是最终的父节点，所以根节点最后打印。

5、打印结果

	public static void main(String[] args) {
		BinaryTree test = new BinaryTree();
		test.createTree();

		System.out.println("*******前序递归********");
		test.preOrder(test.root);
		System.out.println();
		System.out.println("*******前序非递归********");
		test.preorderNoRec(test.root);
		System.out.println();
		System.out.println("*******中序递归********");
		test.inOrder(test.root);
		System.out.println();
		System.out.println("*******中序非递归********");
		test.inOrderNoRec(test.root);
		System.out.println();
		System.out.println("*******后序递归********");
		test.backOrder(test.root);
		System.out.println();
		System.out.println("*******后序非递归********");
		test.backOrderNoRec(test.root);
	}

结果显示：

*******前序递归********
(root)ACGFBEDH
*******前序非递归********
(root)ABDHECFG
*******中序递归********
HDBE(root)AFCG
*******中序非递归********
HDBE(root)AFCG
*******后序递归********
HDEBFGC(root)A
*******后序非递归********
HDEBFGC(root)A

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017-06-20，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

二叉树

编程算法

登录后参与评论

0 条评论

热度