二叉树基础
2020-05-11 本文已影响0人
范柏柏
树
聊二叉树之前，先看看什么是树。
一些树.png
“树”这种数据结构真的很像我们现实生活中的“树”，这里面每个元素我们叫作“节点”；用来连线相邻节点之间的关系，我们叫作“父子关系”。且子节点只能有一个父节点。
一棵树.png
入上图。B节点是D节点的父节点，D节点是B节点的子节点。D、E、F的父节点是同一个节点，所以他们之间互相称为兄弟节点。
我们把没有父节点的节点称为根节点，也就是节点A。
把没有子节点的节点称为叶子节点，也就是I、J、K、F、G、H
关于树，有三个概念：高度、深度、层
高度：节点到叶子节点的最长边数
深度：节点到根节点的边数
层数：节点的深度 + 1
树高：根节点的高度
树的三个概念.png
二叉树
二叉树，顾名思义，每个节点最多有两个叉，也就是两个子节点，分别称为左子节点和右子节点。
两种特殊的二叉树.png
如图，二叉树里有两种比较特殊的二叉树。
满二叉树：叶子节点全部都在最底层，除叶子节点之外，每个节点都有左右两个子节点。
完全二叉树：叶子节点都在最底下两层，最后一层叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都是满的。
满二叉树比较好理解。为什么把完全二叉树当做一个特殊的二叉树呢？？这就要讲到如何存储一棵二叉树了。
二叉树的存储
想要存一棵二叉树，有两种办法，一种是基于指针的链表法，一种是基于数组的顺序存储法。
链式存储法
这个比较简单，直接上图。
链式存储法.png
顺序存储法
基于数组的顺序存储法，我们把根节点存储在下标 i=1的位置，那左子节点存储在下标 2i = 2 的位置，右子节点存储在 2i + 1 = 3 的位置。以此类推。B节点的左子节点存储在 22=4的位置，右子节点存储在22+1 = 5的位置。
顺序存储法.png
如果是完全二叉树，可以发现，数组的格子是被沾满的。如果不是完全二叉树，少哪个节点，哪个下标是空着的。这也是为什么把完全二叉树拎出来的原因。
二叉树的遍历
经典的三种方案：前序遍历、中序遍历、后序遍历
- 前序遍历：对于树的任意节点来说，先打印这个节点，然后打印它的左子树，最后打印它的右子树。
- 中序遍历：对于树的任意节点来说，先打印这个节点的左子树，然后在打印它本身，最后打印它的右子树。
- 后序遍历：对于树的任意节点来说，先打印这个节点的左子树，然后在打印它的右子树，最后打印它本身。
以上图顺序存储法的图为例
- 前序遍历：A -> B -> D -> H -> I -> E -> J -> C -> F -> G
- 中序遍历：H -> D -> I -> B -> J -> E -> A -> F -> C -> G
- 后序遍历：H -> I -> D -> J -> E -> B -> F -> G -> C -> A
接下来上代码
public class BinaryTree {
/**
* 前序遍历
* 自己 -> 左子树 -> 右子树
*/
public static void preOrder(TreeNode node) {
if (node != null) {
visited(node);
preOrder(node.leftChild);
preOrder(node.rightChild);
}
}
/**
* 非递归前序遍历
*
* 自己实现压栈
*/
public static void noRecPreOrder(TreeNode node) {
Stack<TreeNode> stack = new Stack();
TreeNode pNode = node;
while (pNode != null || stack.size() > 0) {
while (pNode != null) {
// 先打印自己
visited(pNode);
// 将自己压入栈
stack.push(pNode);
// 依次把左子树都执行一遍
pNode = pNode.leftChild;
}
// 此时 最后一个节点的左子树已经都打印完了
// 开始打印右子树
if (stack.size() > 0) {
pNode = stack.pop();
pNode = pNode.rightChild;
}
}
}
/**
* 中序遍历
* 左子树 -> 自己 -> 右子树
*/
public static void inOrder(TreeNode node) {
if (node != null) {
inOrder(node.leftChild);
visited(node);
inOrder(node.rightChild);
}
}
/**
* 非递归中序遍历
*
* 自己实现压栈
*/
public static void noRecInOrder(TreeNode node) {
Stack<TreeNode> stack = new Stack();
TreeNode pNode = node;
while (pNode != null || stack.size() > 0) {
while (pNode != null) {
// 先把左子树压栈
stack.push(pNode);
// 一直压倒左子树最后一个节点
pNode = pNode.leftChild;
}
// 此时 最后一个节点的左子树都已经压进来了
// 打印自己，将自己的右子树压栈，下一轮循环，先出栈的，就是自己的右子树
if (stack.size() > 0) {
pNode = stack.pop();
visited(pNode);
pNode = pNode.rightChild;
}
}
}
/**
* 后序遍历
* 左子树 -> 右子树 -> 自己
*/
public static void postOrder(TreeNode node) {
if (node != null) {
postOrder(node.leftChild);
postOrder(node.rightChild);
visited(node);
}
}
/**
* 非递归后序遍历
*
* 自己实现压栈
*/
public static void noRecPostOrder(TreeNode node) {
Stack<TreeNode> stack = new Stack();
TreeNode pNode = node;
TreeNode lastVisit = node;
while (pNode != null || !stack.isEmpty()) {
while (pNode != null) {
// 先把左子树压栈
stack.push(pNode);
// 一直压倒左子树最后一个节点
pNode = pNode.leftChild;
}
// 查看当前栈顶元素
pNode = stack.peek();
// 如果其右子树也为空，或者右子树已经被访问
// 那么就可以直接打印自己
if (pNode.rightChild == null || pNode.rightChild == lastVisit) {
visited(pNode);
stack.pop();
lastVisit = pNode;
pNode = null;
} else {
// 否则，继续遍历右子树
pNode = pNode.rightChild;
}
}
}
/**
* 层序遍历
*/
public static void layerOrder(TreeNode node) {
ArrayDeque<TreeNode> queue = new ArrayDeque<>();
queue.addLast(node);
while (!queue.isEmpty()) {
TreeNode current = queue.pop();
// 先打印自己
visited(current);
//在将自己的所有节点一次入队列
if (current.leftChild != null) {
queue.addLast(current.leftChild);
}
if (current.rightChild != null) {
queue.addLast(current.rightChild);
}
}
}
/**
* 打印节点
*/
private static void visited(TreeNode node) {
node.isVisited = true;
System.out.println(node.data+","+node.key);
}
/**
* 计算树的高度
*/
private int height(TreeNode node){
if(node == null){
return 0;
}else{
int i = height(node.leftChild);
int j = height(node.rightChild);
return (i<j)?j+1:i+1;
}
}
/**
* 计算树的节点数
*/
private int size(TreeNode node){
if(node == null){
return 0;
}else{
return 1+size(node.leftChild)+size(node.rightChild);
}
}
/**
* 创建二叉树
*/
public static void createBinaryTree(TreeNode root){
TreeNode nodeB = new TreeNode(2, "B");
TreeNode nodeC = new TreeNode(3, "C");
TreeNode nodeD = new TreeNode(4, "D");
TreeNode nodeE = new TreeNode(5, "E");
TreeNode nodeF = new TreeNode(6, "F");
TreeNode nodeG = new TreeNode(7, "G");
TreeNode nodeH = new TreeNode(8, "H");
TreeNode nodeI = new TreeNode(9, "I");
TreeNode nodeJ = new TreeNode(10, "J");
root.leftChild = nodeB;
root.rightChild = nodeC;
nodeB.leftChild = nodeD;
nodeB.rightChild = nodeE;
nodeD.leftChild = nodeH;
nodeD.rightChild = nodeI;
nodeE.leftChild = nodeJ;
nodeC.leftChild = nodeF;
nodeC.rightChild = nodeG;
}
/**
* 定义根节点
*/
private TreeNode root;
public TreeNode getRoot() {
return root;
}
public void setRoot(TreeNode root) {
this.root = root;
}
public BinaryTree() {
this.root = new TreeNode(1, "A");
}
/**
* 节点数据结构
*/
private static class TreeNode {
private int key = 0;
private String data = null;
private boolean isVisited = false;
private TreeNode leftChild = null;
private TreeNode rightChild = null;
public TreeNode(){}
public TreeNode(int key, String data) {
this.key = key;
this.data = data;
}
}
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
TreeNode root = binaryTree.root;
createBinaryTree(root);
System.out.println("=============前序遍历=================");
preOrder(root);
System.out.println("=====================================");
System.out.println("=============中序遍历=================");
inOrder(root);
System.out.println("=====================================");
System.out.println("=============后续遍历=================");
postOrder(root);
System.out.println("=====================================");
System.out.println("=============前序遍历 非递归=================");
noRecPreOrder(root);
System.out.println("=====================================");
System.out.println("=============中序遍历 非递归=================");
noRecInOrder(root);
System.out.println("=====================================");
System.out.println("=============后续遍历 非递归=================");
noRecPostOrder(root);
System.out.println("=====================================");
System.out.println("=============层序遍历 非递归=================");
layerOrder(root);
System.out.println("=====================================");
}
}
