概述
概念
二叉树是含有含有n（n≥0）个结点的有限集合。n=0时称为空二叉树。
若结点a有两个分支结点b和c，则：
a.结点b和结点c是结点a的子结点。位于结点a左边的结点b是结点a的左子结点；位于结点a右边的结点c是结点a的右子结点。
b.结点a是结点b和结点c的父结点。
c.结点b和结点c互为兄弟结点。
d.没有父结点的结点称为根结点。
e.没有子结点的结点称为叶子结点。
在非空二叉树中：
a.有且只有一个根结点。
b.每一个结点可以有0~2个子结点。
结点的层次从根结点开始计，根结点为第1层，根结点的子结点为第2层...依次往下。最高层次代表了该二叉树的深度。
性质
二叉树的性质有：
a.在非空二叉树的第i（i≥1）层上最多有2i-1个结点。
b.深度为k（k≥1）的二叉树最多有2k-1个结点。
c.叶子结点的个数总比有两个子结点的结点的个数多1。
满二叉树：一棵深度为k（k≥1）且有2k-1个结点的二叉树。满二叉树的性质有：
a.第i（i≥1）层上有2i-1个结点。
b.除了最后一层全为叶子结点外，其余每一层的结点都有两个子结点。
c.满二叉树的判定条件：m=n=2k-1。其中m为最大结点编号，n为结点个数，k为深度。
结点编号：从根结点起，自上而下，自左而右给满二叉树的每一个结点从1开始编号。也就是说：
a.结点i（i≥1）的左子结点为结点2i，右子结点为结点2i+1。
b.i（i＞1）若为偶数，则结点i的父结点为结点i/2，且结点i为其左子结点；若为奇数，则结点i的父结点为结点(i-1)/2，且结点i为其右子结点。
c.第k（k≥1）层的第一个结点为结点2k-1。
d.二叉树的最后一个结点i与深度d的关系为：2d-1-1＜i≤2d-1。
完全二叉树：每个结点i（1≤i≤n，n为结点个数）都存在的二叉树。满二叉树是一种特殊的完全二叉树。完全二叉树的性质有：
a.只有一个子结点的结点的个数n1=1-n%2。
b.有两个子结点的结点的个数n2=(n-n1-1)/2=(n-2+n%2)/2。
c.叶子结点的个数n0=n2+1=(n+n%2)/2。
d.完全二叉树的判定条件：m=n。
e.若一个结点存在右子结点，则必定存在左子结点；若一个结点不存在左子结点，则必定是叶子结点。
e.完全二叉树叶子结点的编号i（n/2＜i≤n），非叶子结点的编号i（1≤i≤n/2）。
遍历
二叉树的遍历是指从根结点出发，按照某种遍历策略访问二叉树的所有结点，使得每个结点都被访问一次。
遍历策略是指遍历的次序，通常情况下遍历左子（L）先于右子（R），于是根据遍历根结点（V）的时机，遍历策略分为：
先序遍历（VLR）：先遍历根结点（V），再遍历左子（L），最后遍历右子（R）。
中序遍历（LVR）：先遍历左子（L），再遍历根结点（V），最后遍历右子（R）。
后序遍历（LRV）：先遍历左子（L），再遍历右子（R），最后遍历根结点（V）。
对于二叉树：
a.先序遍历：1 2 4 5 3 6 7
b.中序遍历：4 2 5 1 6 3 7
c.后序遍历：4 5 2 6 7 3 1
二叉树结构
二叉树结构常用的操作有：增加、修改、删除、查询结点，以及判断二叉树类型、清空二叉树等。其接口定义如下：
1 /** 2 * 二叉树 3 * @param4 */ 5 public interface BiTree { 6 7 /** 8 * 遍历策略 9 */ 10 enum TraversingStrategy { 11 /** 12 * 先序遍历 13 */ 14 VLR, 15 16 /** 17 * 中序遍历 18 */ 19 LVR, 20 21 /** 22 * 后序遍历 23 */ 24 LRV; 25 } 26 27 /** 28 * 清空 29 */ 30 void clear(); 31 32 /** 33 * 是否为空二叉树 34 * @return 35 */ 36 boolean isEmpty(); 37 38 /** 39 * 是否为完全二叉树 40 * @return 41 */ 42 boolean isComplete(); 43 44 /** 45 * 是否为满二叉树 46 * @return 47 */ 48 boolean isFull(); 49 50 /** 51 * 获取结点数 52 * @return 53 * @throws BiTreeException 54 */ 55 int getNum() throws BiTreeException; 56 57 /** 58 * 获取深度 59 * @return 60 * @throws BiTreeException 61 */ 62 int getDepth() throws BiTreeException; 63 64 /** 65 * 获取指定元素在二叉树的结点编号 66 * @param e 元素 67 * @return 返回结点编号，若不存在该结点则返回-1 68 * @throws BiTreeException 69 */ 70 int getIndex(E e) throws BiTreeException; 71 72 /** 73 * 获取指定结点的元素 74 * @param index 结点编号 75 * @return 76 * @throws BiTreeException 77 */ 78 E get(int index) throws BiTreeException; 79 80 /** 81 * 获取指定结点的左子结点的元素 82 * @param index 结点编号 83 * @return 84 * @throws BiTreeException 85 */ 86 E getLchild(int index) throws BiTreeException; 87 88 /** 89 * 获取指定结点的右子结点的元素 90 * @param index 结点编号 91 * @return 92 * @throws BiTreeException 93 */ 94 E getRchild(int index) throws BiTreeException; 95 96 /** 97 * 获取指定结点的父结点的元素 98 * @param index 结点编号 99 * @return100 * @throws BiTreeException101 */102 E getParent(int index) throws BiTreeException;103 104 /**105 * 指定结点是否为叶子结点106 * @param index 结点编号107 * @return108 * @throws BiTreeException109 */110 boolean isLeaf(int index) throws BiTreeException;111 112 /**113 * 在指定位置插入结点114 * @param index 结点编号115 * @param e 元素116 * @throws BiTreeException117 */118 void add(int index, E e) throws BiTreeException;119 120 /**121 * 为指定结点赋值122 * @param index 结点编号123 * @param e 元素124 * @throws BiTreeException125 */126 void set(int index, E e) throws BiTreeException;127 128 /**129 * 删除指定结点130 * @param index 结点编号131 * @throws BiTreeException132 */133 void remove(int index) throws BiTreeException;134 135 /**136 * 遍历137 * @param strategy 遍历策略138 */139 void traverse(TraversingStrategy strategy);140 141 }
抽象类定义如下：
1 public abstract class AbstractBiTreeimplements BiTree { 2 3 protected int num; 4 protected int depth; 5 protected int maxIndex; 6 7 /** 8 * 计算父结点的编号 9 * @param index 结点编号 10 * @return 11 */ 12 protected int getParentIndex(int index) { 13 return index % 2 == 0 ? index / 2 : (index - 1) / 2; 14 } 15 16 /** 17 * 计算左子结点的编号 18 * @param index 结点编号 19 * @return 20 */ 21 protected int getLchildIndex(int index) { 22 return 2 * index; 23 } 24 25 /** 26 * 计算右子结点的编号 27 * @param index 结点编号 28 * @return 29 */ 30 protected int getRchildIndex(int index) { 31 return 2 * index + 1; 32 } 33 34 35 protected void setDepth() { 36 depth = 0; 37 for (int i = 1; i <= maxIndex; depth++, i *= 2); 38 } 39 40 /** 41 * 检查是否为空二叉树 42 * @throws BiTreeException 43 */ 44 protected void checkEmpty() throws BiTreeException { 45 if (isEmpty()) { 46 throw new BiTreeException("该树为空二叉树！"); 47 } 48 } 49 50 /** 51 * 检查编号是否为正数 52 * @param index 结点编号 53 * @throws BiTreeException 54 */ 55 protected void checkPositive(int index) throws BiTreeException { 56 if (index < 1) { 57 throw new BiTreeException("编号必须为正数！"); 58 } 59 } 60 61 /** 62 * 检查编号是否超出范围 63 * @param index 结点编号 64 * @throws BiTreeException 65 */ 66 protected void checkOutOfBounds(int index) throws BiTreeException { 67 checkPositive(index); 68 checkEmpty(); 69 if (index > maxIndex) { 70 throw new BiTreeException("编号" + index + "超出范围！"); 71 } 72 } 73 74 protected abstract void addRoot(E e) throws BiTreeException; 75 76 protected abstract void addLchild(E e, int parent) throws BiTreeException; 77 78 protected abstract void addRchild(E e, int parent) throws BiTreeException; 79 80 @Override 81 public void clear() { 82 num = 0; 83 depth = 0; 84 maxIndex = 0; 85 } 86 87 @Override 88 public boolean isEmpty() { 89 return num == 0; 90 } 91 92 @Override 93 public boolean isComplete() { 94 return ! isEmpty() && maxIndex == num; 95 } 96 97 @Override 98 public boolean isFull() { 99 return isComplete() && maxIndex == Math.pow(2, depth) - 1;100 }101 102 @Override103 public int getNum() {104 return num;105 }106 107 @Override108 public int getDepth() {109 return depth;110 }111 112 @Override113 public void add(int index, E e) throws BiTreeException {114 checkPositive(index);115 if (index == 1) {116 addRoot(e);117 } else {118 int parent = getParentIndex(index);119 if (index % 2 == 0) {120 addLchild(e, parent);121 } else {122 addRchild(e, parent);123 }124 }125 num++;126 }127 128 }
二叉树分为顺序存储和链式存储。
顺序存储结构如下：
1 public class SqBiTreeextends AbstractBiTree { 2 3 protected Object[] elem; 4 protected int size; 5 protected int increment; 6 7 public SqBiTree() { 8 this (5, 3); 9 } 10 11 public SqBiTree(int size, int inc) { 12 this.size = size; 13 increment = inc; 14 elem = new Object[size]; 15 } 16 17 @SuppressWarnings("unchecked") 18 public SqBiTree(E ... elems) { 19 size = 5; 20 increment = 3; 21 elem = elems; 22 num = maxIndex = elems.length; 23 setDepth(); 24 } 25 26 @Override 27 public void clear() { 28 elem = new Object[size]; 29 super.clear(); 30 } 31 32 @Override 33 public int getIndex(E e) throws BiTreeException { 34 checkEmpty(); 35 for (int i = 0; i < maxIndex; i++) { 36 if (elem[i].equals(e)) return i + 1; 37 } 38 return -1; 39 } 40 41 @SuppressWarnings("unchecked") 42 @Override 43 public E get(int index) throws BiTreeException { 44 checkOutOfBounds(index); 45 return (E) elem[index - 1]; 46 } 47 48 @SuppressWarnings("unchecked") 49 @Override 50 public E getLchild(int index) throws BiTreeException { 51 if (get(index) == null) { 52 throw new BiTreeException("结点" + index + "不存在！"); 53 } 54 if (getLchildIndex(index) > maxIndex) return null; 55 return (E) elem[getLchildIndex(index) - 1]; 56 } 57 58 @SuppressWarnings("unchecked") 59 @Override 60 public E getRchild(int index) throws BiTreeException { 61 if (get(index) == null) { 62 throw new BiTreeException("结点" + index + "不存在！"); 63 } 64 if (getRchildIndex(index) > maxIndex) return null; 65 return (E) elem[getRchildIndex(index) - 1]; 66 } 67 68 @SuppressWarnings("unchecked") 69 @Override 70 public E getParent(int index) throws BiTreeException { 71 if (get(index) == null) { 72 throw new BiTreeException("结点" + index + "不存在！"); 73 } 74 if (index == 1) return null; 75 return (E) elem[getParentIndex(index) - 1]; 76 } 77 78 @Override 79 public boolean isLeaf(int index) throws BiTreeException { 80 if (get(index) == null) { 81 throw new BiTreeException("结点" + index + "不存在！"); 82 } 83 if (getLchildIndex(index) > maxIndex) return true; 84 if (elem[getLchildIndex(index) - 1] != null) return false; 85 if (getRchildIndex(index) > maxIndex || elem[getRchildIndex(index) - 1] == null) return true; 86 return false; 87 } 88 89 @Override 90 public void set(int index, E e) throws BiTreeException { 91 if (get(index) == null) { 92 throw new BiTreeException("结点" + index + "不存在！"); 93 } 94 elem[index - 1] = e; 95 } 96 97 @Override 98 public void remove(int index) throws BiTreeException { 99 if (index < 1 || index > maxIndex) return;100 if (elem[index - 1] != null) {101 elem[index - 1] = null;102 num--;103 }104 if (index == maxIndex) {105 do {106 maxIndex--;107 } while (elem[maxIndex - 1] == null);108 setDepth();109 }110 remove(getLchildIndex(index));111 remove(getRchildIndex(index));112 }113 114 @SuppressWarnings("preview")115 private void traverse(int index, TraversingStrategy strategy) {116 if (index < 1 || index > maxIndex || elem[index - 1] == null) return;117 switch (strategy) {118 case VLR -> {119 System.out.print(elem[index - 1] + " ");120 traverse(getLchildIndex(index), strategy);121 traverse(getRchildIndex(index), strategy);122 }123 case LVR -> {124 traverse(getLchildIndex(index), strategy);125 System.out.print(elem[index - 1] + " ");126 traverse(getRchildIndex(index), strategy);127 }128 case LRV -> {129 traverse(getLchildIndex(index), strategy);130 traverse(getRchildIndex(index), strategy);131 System.out.print(elem[index - 1] + " ");132 }133 }134 }135 136 @Override137 public void traverse(TraversingStrategy strategy) {138 traverse(1, strategy);139 System.out.println();140 }141 142 @Override143 protected void addRoot(E e) throws BiTreeException {144 if (isEmpty()) {145 elem[0] = e;146 maxIndex = depth = 1;147 } else {148 throw new BiTreeException("结点1已存在！");149 }150 }151 152 private void capacity(int size) {153 Object[] elem = new Object[size];154 System.arraycopy(this.elem, 0, elem, 0, maxIndex);155 this.elem = elem;156 }157 158 @Override159 protected void addLchild(E e, int parent) throws BiTreeException {160 if (elem[parent - 1] == null) throw new BiTreeException("父结点" + parent + "不存在！");161 int index = getLchildIndex(parent);162 if (index <= maxIndex) {163 if (elem[index - 1] != null) throw new BiTreeException("结点" + index + "已存在！");164 } else {165 capacity(index + increment);166 maxIndex = index;167 setDepth();168 }169 elem[index - 1] = e;170 }171 172 @Override173 protected void addRchild(E e, int parent) throws BiTreeException {174 if (elem[parent - 1] == null) throw new BiTreeException("父结点" + parent + "不存在！");175 int index = getRchildIndex(parent);176 if (index <= maxIndex) {177 if (elem[index - 1] != null) throw new BiTreeException("结点" + index + "已存在！");178 } else {179 capacity(index + increment);180 maxIndex = index;181 setDepth();182 }183 elem[index - 1] = e;184 }185 186 private String toString(int index) {187 if (index < 1 || index > maxIndex || elem[index - 1] == null) return null;188 String s = elem[index - 1] + "";189 String ls = toString(getLchildIndex(index));190 String rs = toString(getRchildIndex(index));191 if (ls != null || rs != null) s += "[" + (ls == null ? "-" : ls) + ", " + (rs == null ? "-" : rs) + "]";192 return s;193 }194 195 @Override196 public String toString() {197 try {198 checkEmpty();199 } catch (BiTreeException e) {200 return "该树为空二叉树！";201 }202 return toString(1);203 }204 205 }
链式存储结构如下：
1 public class LBiTreeextends AbstractBiTree { 2 3 protected enum Tag { 4 ROOT, LEFT, RIGHT; 5 } 6 7 protected class Node { 8 9 /** 10 * 元素 11 */ 12 E elem; 13 14 /** 15 * 左子结点 16 */ 17 Node lchild; 18 19 /** 20 * 右子结点 21 */ 22 Node rchild; 23 24 /** 25 * 父结点 26 */ 27 Node parent; 28 29 /** 30 * 标志 31 */ 32 Tag tag; 33 34 Node(E elem) { 35 this.elem = elem; 36 tag = Tag.ROOT; 37 } 38 39 Node(E elem, Node parent, Tag tag) { 40 this.elem = elem; 41 this.parent = parent; 42 this.tag = tag; 43 } 44 45 int getIndex() { 46 if (tag == Tag.ROOT) return 1; 47 return tag == Tag.LEFT ? getLchildIndex(parent.getIndex()) : getRchildIndex(parent.getIndex()); 48 } 49 50 } 51 52 protected Node root = null; 53 54 public LBiTree() { 55 56 } 57 58 @SuppressWarnings("unchecked") 59 public LBiTree(E ... elems) { 60 maxIndex = num = elems.length; 61 setDepth(); 62 root = new Node(elems[0]); 63 Node parent = root; 64 for (int i = 1; i < num; i += 2) { 65 Node lchild = new Node(elems[i], parent, Tag.LEFT); 66 parent.lchild = lchild; 67 if (i + 1 < num) { 68 Node rchild = new Node(elems[i + 1], parent, Tag.RIGHT); 69 parent.rchild = rchild; 70 } 71 if (parent == root) { 72 parent = root.lchild; 73 } else if (parent.tag == Tag.LEFT) { 74 parent = parent.parent.rchild; 75 } else { 76 Node node = parent; 77 int level = 1; 78 while (node.tag == Tag.RIGHT) { 79 node = node.parent; 80 level++; 81 } 82 if (node.tag == Tag.LEFT) { 83 parent = node.parent.rchild.lchild; 84 } else { 85 while (level > 0) { 86 node = node.lchild; 87 level--; 88 } 89 parent = node; 90 } 91 } 92 } 93 } 94 95 @Override 96 public void clear() { 97 root = null; 98 super.clear(); 99 }100 101 private Node getNode(E e, Node node) {102 if (node.elem.equals(e)) return node;103 Node n;104 if (node.lchild != null) {105 n = getNode(e, node.lchild);106 if (n != null) {107 return n;108 }109 }110 if (node.rchild != null) {111 n = getNode(e, node.rchild);112 if (n != null) {113 return n;114 }115 }116 return null;117 }118 119 @Override120 public int getIndex(E e) throws BiTreeException {121 checkEmpty();122 Node node = getNode(e, root);123 return node == null ? -1 : node.getIndex();124 }125 126 private Node getNode(int index) {127 if (index == 1) return root;128 Node node = getNode(getParentIndex(index));129 if (node == null) return null;130 return index % 2 == 0 ? node.lchild : node.rchild;131 }132 133 @Override134 public E get(int index) throws BiTreeException {135 checkOutOfBounds(index);136 Node node = getNode(index);137 if (node == null) return null;138 return node.elem;139 }140 141 @Override142 public E getLchild(int index) throws BiTreeException {143 checkOutOfBounds(index);144 Node node = getNode(index);145 if (node == null) throw new BiTreeException("父结点" + index + "不存在！");146 node = node.lchild;147 if (node == null) return null;148 return node.elem;149 }150 151 @Override152 public E getRchild(int index) throws BiTreeException {153 checkOutOfBounds(index);154 Node node = getNode(index);155 if (node == null) throw new BiTreeException("父结点" + index + "不存在！");156 node = node.rchild;157 if (node == null) return null;158 return node.elem;159 }160 161 @Override162 public E getParent(int index) throws BiTreeException {163 checkOutOfBounds(index);164 if (index == 1) return null;165 Node node = getNode(index);166 if (node == null) throw new BiTreeException("结点" + index + "不存在！");167 node = node.parent;168 if (node == null) return null;169 return node.elem;170 }171 172 @Override173 public boolean isLeaf(int index) throws BiTreeException {174 checkOutOfBounds(index);175 Node node = getNode(index);176 if (node == null) throw new BiTreeException("结点" + index + "不存在！");177 return node.lchild == null && node.rchild == null;178 }179 180 @Override181 public void set(int index, E e) throws BiTreeException {182 checkOutOfBounds(index);183 Node node = getNode(index);184 if (node == null) throw new BiTreeException("结点" + index + "不存在！");185 node.elem = e;186 }187 188 private int getSubNum(Node node) {189 int num = 0;190 if (node != null) num++;191 if (node.lchild != null) num += getSubNum(node.lchild);192 if (node.rchild != null) num += getSubNum(node.rchild);193 return num;194 }195 196 @Override197 public void remove(int index) throws BiTreeException {198 checkOutOfBounds(index);199 Node node = getNode(index);200 if (node != null) {201 if (index % 2 == 0) {202 node.parent.lchild = null;203 } else {204 node.parent.rchild = null;205 }206 num -= getSubNum(node);207 while (getNode(maxIndex) == null) maxIndex--;208 setDepth();209 }210 }211 212 @SuppressWarnings("preview")213 private void traverse(TraversingStrategy strategy, Node node) {214 switch (strategy) {215 case VLR -> {216 if (node != null) {217 System.out.print(node.elem + " ");218 traverse(strategy, node.lchild);219 traverse(strategy, node.rchild);220 }221 }222 case LVR -> {223 if (node != null) {224 traverse(strategy, node.lchild);225 System.out.print(node.elem + " ");226 traverse(strategy, node.rchild);227 }228 }229 case LRV -> {230 if (node != null) {231 traverse(strategy, node.lchild);232 traverse(strategy, node.rchild);233 System.out.print(node.elem + " ");234 }235 }236 }237 }238 239 @Override240 public void traverse(TraversingStrategy strategy) {241 traverse(strategy, root);242 System.out.println();243 }244 245 @Override246 protected void addRoot(E e) throws BiTreeException {247 if (isEmpty()) {248 root = new Node(e);249 maxIndex = depth = 1;250 } else {251 throw new BiTreeException("结点1已存在！");252 }253 }254 255 @Override256 protected void addLchild(E e, int parent) throws BiTreeException {257 Node node = getNode(parent);258 if (node == null) throw new BiTreeException("父结点" + parent + "不存在！");259 int index = getLchildIndex(parent);260 if (node.lchild != null) throw new BiTreeException("结点" + index + "已存在！");261 node.lchild = new Node(e, node, Tag.LEFT);262 if (index > maxIndex) {263 maxIndex = index;264 setDepth();265 }266 }267 268 @Override269 protected void addRchild(E e, int parent) throws BiTreeException {270 Node node = getNode(parent);271 if (node == null) throw new BiTreeException("父结点" + parent + "不存在！");272 int index = getRchildIndex(parent);273 if (node.rchild != null) throw new BiTreeException("结点" + index + "已存在！");274 node.rchild = new Node(e, node, Tag.RIGHT);275 if (index > maxIndex) {276 maxIndex = index;277 setDepth();278 }279 }280 281 private String toString(Node node) {282 String s = "" + node.elem;283 if (node.lchild != null || node.rchild != null) {284 s += "[" + (node.lchild == null ? "-" : toString(node.lchild));285 s += ", " + (node.rchild == null ? "-" : toString(node.rchild)) + "]";286 }287 return s;288 }289 290 @Override291 public String toString() {292 return toString(root);293 }294 295 }