数据结构（一）二叉树
2021-11-02 本文已影响0人
又语
二叉树（Binary Tree）是n个有限元素的集合，该集合或者为空，或者由一个称为根（root）的元素及两个不相交的、被称为左子树和右子树的二叉树组成，是有序树。在二叉树中，一个元素也称作一个节点。
二叉树（Binary Tree）又指树中节点的度不大于2的有序树。
二叉树有两种特殊类型：
- 满二叉树（Full Binary Tree）是高度为
k，且拥有(2^k)-1个节点的二叉树。一颗满二叉树每个节点，要么都有两棵子树，要么都没有子树。 - 完全二叉树（Complete Binary Tree，假设完全二叉树高度为
k）遵循以下规则：- 所有叶子节点都出现在
k层或k-1层，并且从1 ~ k-1层必须达到最大节点数； - 第
k层可以是不满的，但是第k层的所有节点必须集中在最左边。
- 所有叶子节点都出现在
Java 代码实现
1. 二叉树定义
首先，定义树节点，参考附录部分第一段代码。
其次，定义树：
public class BinaryTree {
private BinaryTreeNode root;
public BinaryTree() {
}
public BinaryTree(BinaryTreeNode root) {
this.root = root;
}
// Getter & Setter 略
}
2. 清空二叉树
首先，定义一个清空某节点下子树的方法，利用递归删除每个节点。
然后，定义一个删除树的方法。
/**
* 清空以某个节点为根节点的子树及当前节点的方法，既递归地删除每个节点
*/
public void clear(BinaryTreeNode node) {
if (node != null) {
clear(node.getLeftChild());
clear(node.getRightChild());
// 删除节点
node = null;
}
}
/**
* 清空二叉树
*/
public void clear() {
clear(this.root);
}
3. 判断树是否为空
只需要判断根节点是否存在。
/**
* 判断二叉树是否为空
*/
public boolean isEmpty() {
return this.root == null;
}
4. 获取树高度
/**
* 获取以某节点为根节点的子树的高度，包括当前节点
*/
public int height(BinaryTreeNode node) {
if (node == null) {
return 0;
}
int leftHeight = height(node.getLeftChild());
int rightHeight = height(node.getRightChild());
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
/**
* 获取二叉树高度
*/
public int height() {
return height(this.root);
}
5. 求节点数
/**
* 获取以某节点为根节点的所有子节点数，包括当前节点
*/
public int size(BinaryTreeNode node) {
if (node == null) {
return 0;
}
return 1 + size(node.getLeftChild()) + size(node.getRightChild());
}
/**
* 获取二叉树全部节点数
*/
public int size() {
return size(this.root);
}
6. 返回父节点
/**
* 给定一个子树subTree，获取某节点在此子树中的父节点
*/
public BinaryTreeNode getParent(BinaryTreeNode subTree, BinaryTreeNode node) {
if (subTree == null) {
return null;
}
if (subTree.getLeftChild() == node || subTree.getRightChild() == node) {
return subTree;
}
BinaryTreeNode parent = getParent(subTree.getLeftChild(), node);
return parent != null ? parent : getParent(subTree.getRightChild(), node);
}
/**
* 获取某节点在二叉树中的父节点
*/
public BinaryTreeNode getParent(BinaryTreeNode node) {
return (this.root == null || this.root == node) ? null : getParent(this.root, node);
}
7. 返回左右子树
/**
* 获取某节点的左子树
*/
public BinaryTreeNode getLeftTree(BinaryTreeNode node) {
return node.getLeftChild();
}
/**
* 获取某节点的右子树
*/
public BinaryTreeNode getRightTree(BinaryTreeNode node) {
return node.getRightChild();
}
8. 插入
/**
* 给某节点插入左子节点
*/
public void insertLeftChild(BinaryTreeNode parent, BinaryTreeNode newLeftChild) {
parent.setLeftChild(newLeftChild);
}
/**
* 给某节点插入右子节点
*/
public void insertRightChild(BinaryTreeNode parent, BinaryTreeNode newRightChild) {
parent.setRightChild(newRightChild);
}
9. 遍历
9.1 前序遍历
考察到一个节点后，即刻输出该节点的值，并继续遍历其左右子树。(根左右)
/**
* 前序遍历（递归实现）
*/
public void preOrderTraversalRecursion(BinaryTreeNode node) {
if (node != null) {
System.out.println(node.getData());
preOrderTraversalRecursion(node.getLeftChild());
preOrderTraversalRecursion(node.getRightChild());
}
}
/**
* 前序遍历（非递归实现）
*/
public void preOrderTraversal(BinaryTreeNode node) {
// 用以暂存节点的栈
Stack<BinaryTreeNode> nodeStack = new Stack<>();
// 新建一个节点赋值为待遍历的节点
BinaryTreeNode temp = node;
// 当遍历到最后一个节点时，无论其左右子树，又或是节点栈，都应该为空
while (temp != null || !nodeStack.isEmpty()) {
while (temp != null) {
System.out.println(temp.getData());
nodeStack.push(temp);
temp = temp.getLeftChild();
}
if (!nodeStack.isEmpty()) {
temp = nodeStack.pop();
temp = temp.getRightChild();
}
}
}
9.2 中序遍历
考察到一个节点后，将其暂存，遍历完左子树后，再输出该节点的值，然后遍历右子树。(左根右)
/**
* 中序遍历（递归实现）
*/
public void inOrderTraversalRecursion(BinaryTreeNode node) {
inOrderTraversalRecursion(node.getLeftChild());
System.out.println(node.getData());
inOrderTraversalRecursion(node.getRightChild());
}
/**
* 中序遍历（非递归实现）
*/
public void inOrderTraversal(BinaryTreeNode node) {
Stack<BinaryTreeNode> nodeStack = new Stack<>();
BinaryTreeNode temp = node;
while (temp != null || !nodeStack.isEmpty()) {
while (temp != null) {
nodeStack.push(temp);
temp = temp.getLeftChild();
}
if (!nodeStack.isEmpty()) {
temp = nodeStack.pop();
System.out.println(temp.getData());
temp = temp.getRightChild();
}
}
}
9.3 后序遍历
后序：考察到一个节点后，将其暂存，遍历完左右子树后，再输出该节点的值。(左右根)
/**
* 后续遍历（递归实现）
*/
public void postOrderTraversalRecursion(BinaryTreeNode node) {
if (node != null) {
postOrderTraversalRecursion(node.getLeftChild());
postOrderTraversalRecursion(node.getRightChild());
System.out.println(node.getData());
}
}
/**
* 后续遍历（非递归实现）
*/
public void postOrderTraversal(BinaryTreeNode node) {
Stack<BinaryTreeNode> nodeStack = new Stack<>();
BinaryTreeNode temp = node;
BinaryTreeNode lastVisit = node;
while (temp != null || !nodeStack.isEmpty()) {
while (temp != null) {
nodeStack.push(temp);
temp = temp.getLeftChild();
}
// 查看当前栈顶元素
temp = nodeStack.peek();
// 如果其右子树也为空，或右子树已经访问，则可以直接输出当前节点的值
if (temp.getRightChild() == null || temp.getRightChild() == lastVisit) {
System.out.println(temp.getData());
nodeStack.pop();
lastVisit = temp;
temp = null;
} else {
temp = temp.getRightChild();
}
}
}
附：完整代码
二叉树节点
/**
* 二叉树的左右链表表示法
*/
public class BinaryTreeNode {
private int data;
private BinaryTreeNode leftChild;
private BinaryTreeNode rightChild;
// Getter & Setter 略
// hashCode & equals 略
}
二叉树
public class BinaryTree {
private BinaryTreeNode root;
public BinaryTree() {
}
public BinaryTree(BinaryTreeNode root) {
this.root = root;
}
/**
* 清空以某个节点为根节点的子树及当前节点的方法，既递归地删除每个节点
*/
public void clear(BinaryTreeNode node) {
if (node != null) {
clear(node.getLeftChild());
clear(node.getRightChild());
// 删除节点
node = null;
}
}
/**
* 清空二叉树
*/
public void clear() {
clear(this.root);
}
/**
* 判断二叉树是否为空
*/
public boolean isEmpty() {
return this.root == null;
}
/**
* 获取以某节点为根节点的子树的高度，包括当前节点
*/
public int height(BinaryTreeNode node) {
if (node == null) {
return 0;
}
int leftHeight = height(node.getLeftChild());
int rightHeight = height(node.getRightChild());
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
/**
* 获取二叉树高度
*/
public int height() {
return height(this.root);
}
/**
* 获取以某节点为根节点的所有子节点数，包括当前节点
*/
public int size(BinaryTreeNode node) {
if (node == null) {
return 0;
}
return 1 + size(node.getLeftChild()) + size(node.getRightChild());
}
/**
* 获取二叉树全部节点数
*/
public int size() {
return size(this.root);
}
/**
* 给定一个子树subTree，获取某节点在此子树中的父节点
*/
public BinaryTreeNode getParent(BinaryTreeNode subTree, BinaryTreeNode node) {
if (subTree == null) {
return null;
}
if (subTree.getLeftChild() == node || subTree.getRightChild() == node) {
return subTree;
}
BinaryTreeNode parent = getParent(subTree.getLeftChild(), node);
return parent != null ? parent : getParent(subTree.getRightChild(), node);
}
/**
* 获取某节点在二叉树中的父节点
*/
public BinaryTreeNode getParent(BinaryTreeNode node) {
return (this.root == null || this.root == node) ? null : getParent(this.root, node);
}
/**
* 获取某节点的左子树
*/
public BinaryTreeNode getLeftTree(BinaryTreeNode node) {
return node.getLeftChild();
}
/**
* 获取某节点的右子树
*/
public BinaryTreeNode getRightTree(BinaryTreeNode node) {
return node.getRightChild();
}
/**
* 给某节点插入左子节点
*/
public void insertLeftChild(BinaryTreeNode parent, BinaryTreeNode newLeftChild) {
parent.setLeftChild(newLeftChild);
}
/**
* 给某节点插入右子节点
*/
public void insertRightChild(BinaryTreeNode parent, BinaryTreeNode newRightChild) {
parent.setRightChild(newRightChild);
}
/**
* 前序遍历（递归实现）
*/
public void preOrderTraversalRecursion(BinaryTreeNode node) {
if (node != null) {
System.out.println(node.getData());
preOrderTraversalRecursion(node.getLeftChild());
preOrderTraversalRecursion(node.getRightChild());
}
}
/**
* 前序遍历（非递归实现）
*/
public void preOrderTraversal(BinaryTreeNode node) {
// 用以暂存节点的栈
Stack<BinaryTreeNode> nodeStack = new Stack<>();
// 新建一个节点赋值为待遍历的节点
BinaryTreeNode temp = node;
// 当遍历到最后一个节点时，无论其左右子树，又或是节点栈，都应该为空
while (temp != null || !nodeStack.isEmpty()) {
while (temp != null) {
System.out.println(temp.getData());
nodeStack.push(temp);
temp = temp.getLeftChild();
}
if (!nodeStack.isEmpty()) {
temp = nodeStack.pop();
temp = temp.getRightChild();
}
}
}
/**
* 中序遍历（递归实现）
*/
public void inOrderTraversalRecursion(BinaryTreeNode node) {
inOrderTraversalRecursion(node.getLeftChild());
System.out.println(node.getData());
inOrderTraversalRecursion(node.getRightChild());
}
/**
* 中序遍历（非递归实现）
*/
public void inOrderTraversal(BinaryTreeNode node) {
Stack<BinaryTreeNode> nodeStack = new Stack<>();
BinaryTreeNode temp = node;
while (temp != null || !nodeStack.isEmpty()) {
while (temp != null) {
nodeStack.push(temp);
temp = temp.getLeftChild();
}
if (!nodeStack.isEmpty()) {
temp = nodeStack.pop();
System.out.println(temp.getData());
temp = temp.getRightChild();
}
}
}
/**
* 后续遍历（递归实现）
*/
public void postOrderTraversalRecursion(BinaryTreeNode node) {
if (node != null) {
postOrderTraversalRecursion(node.getLeftChild());
postOrderTraversalRecursion(node.getRightChild());
System.out.println(node.getData());
}
}
/**
* 后续遍历（非递归实现）
*/
public void postOrderTraversal(BinaryTreeNode node) {
Stack<BinaryTreeNode> nodeStack = new Stack<>();
BinaryTreeNode temp = node;
BinaryTreeNode lastVisit = node;
while (temp != null || !nodeStack.isEmpty()) {
while (temp != null) {
nodeStack.push(temp);
temp = temp.getLeftChild();
}
// 查看当前栈顶元素
temp = nodeStack.peek();
// 如果其右子树也为空，或右子树已经访问，则可以直接输出当前节点的值
if (temp.getRightChild() == null || temp.getRightChild() == lastVisit) {
System.out.println(temp.getData());
nodeStack.pop();
lastVisit = temp;
temp = null;
} else {
temp = temp.getRightChild();
}
}
}
// Getter & Setter 略
// hashCode & equals 略
}
