一. 树的简介
1. 什么是树(tree)
树是一种非线性的数据结构，是由n（n >=0）个结点组成的有限集合，运行时间平均为O(logN)。请看下图
简单树实例
2. 树的相关概念
①根节点(root)：每个树的顶部节点
②树存在子节点与父节点的概念，除去根节点外每个节点都只有一个父亲(可以用来识别是不是树)
③树叶(leaf)：没有儿子的节点，即最底层节点
④兄弟(sibling)：具有同一个父亲的两个节点称为兄弟节点
⑤深度(depth)：从根节点到n节点的唯一路径的长(即第n节点到根节点的边的条数)
⑥高(height)：从n节点到自己树叶的最长路径的长
二. 实现
1. 数据结构
- 左孩子右兄弟表示法
package com.shan.tree;
import com.shan.list.Node;
public class TreeNode {
private int element;
private Node firstChild; // 第一个孩子节点
private Node nextSib; // 下一个兄弟节点
public TreeNode(int element) {
this.element = element;
this.firstChild = null;
this.nextSib = null;
}
public TreeNode(int element, Node firstChild, Node nextSib) {
this.element = element;
this.firstChild = firstChild;
this.nextSib = nextSib;
}
public int getElement() {
return element;
}
public void setElement(int element) {
this.element = element;
}
public Node getFirstChild() {
return firstChild;
}
public void setFirstChild(Node firstChild) {
this.firstChild = firstChild;
}
public Node getNextSib() {
return nextSib;
}
public void setNextSib(Node nextSib) {
this.nextSib = nextSib;
}
}
2. 二叉树
- 学习树最简单的就是二叉树：每个节点的子节点不能超过两个
- 二叉树的平均深度比节点数N少得多，最坏情况N-1
数据结构
package com.shan.tree;
import com.shan.list.Node;
public class BinaryTreeNode<T> {
private T element;
private Node left;
private Node right;
public BinaryTreeNode(T element) {
this.element = element;
}
public T getElement() {
return element;
}
public void setElement(T element) {
this.element = element;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
表达式树
- 二叉树的重要应用就是表达式树
package com.shan.tree;
import java.util.Stack;
public class BinaryTree {
private BinaryTreeNode root;
public BinaryTree(BinaryTreeNode root) {
this.root = root;
}
/**
* 后缀表达式转成表达式树
* @param exp 后缀表达式
* @return 表达式树
*/
public BinaryTree postorderToExpressionTree(String exp) {
Stack<BinaryTreeNode<Character>> optionStack = new Stack<>();
for(int i=0; i<exp.length(); i++) {
char nextChar = exp.charAt(i);
if(nextChar == '+' || nextChar == '-' || nextChar == '*'|| nextChar == '/') {
BinaryTreeNode midNode = new BinaryTreeNode(nextChar);
BinaryTreeNode rightNode = optionStack.pop();
BinaryTreeNode leftNode = optionStack.pop();
midNode.setLeft(leftNode);
midNode.setRight(rightNode);
optionStack.push(midNode);
}else {
optionStack.push(new BinaryTreeNode<>(nextChar));
}
}
BinaryTreeNode root = optionStack.pop();
BinaryTree tree = new BinaryTree(root);
return tree;
}
}
