形态：空树；只有根节点；只有左子女；只有右子女；既有左子女也有右子女。

1. 二元組表示：<前驱后继> 序偶：尖括号表示一对节点 2. 广义表示法： 双亲（左子女，右子女） ①：叶子节点总比双分支节点个数多一 ②：将一棵滿二叉树按层进行编号层数设为i，则每一层都有 2^（i-1）个节点一棵h层的二叉树有(2^h -1)个节点。

---

---

/*通过已有数组元素创建二叉搜索树 
先为root分配单え将数组中的第一个元素放置在root->data 上，然后遍历数组其他元素
用指针c 在二叉树上跑指针pa 跟在c 的后面，当要插入的元素比 c 大时c 往右边跑，反之往左边跑
c 为空时停下来pa 指在待被插结点上，然后判断待插结点p 与 pa 的大小小的插在左边，大的插在右边
结束后返回根节点root 二叉搜索树创建完成 */

---

一棵h层的二叉树，前h-1 层是满的第h层连续缺失右边子女
i.满二叉树是特殊的完全二叉树
ii.完全二叉树最多只有一个单分支
iii.一棵h層的完全二叉树有n个节点，则:

由以上代码可以看出来创建完全二叉树时，因h层的完全二叉树是前h-1层是满的第h层连续缺失右边子女（*注意，不是右子女）所以使用顺序存储的方式，按层一一存储下来并应用到了队列。
ii、创建其他节点——>先创建节点然后找到双亲，判断左右是否空最后挂新根节点

---

---

* 二叉树的非递归按层、前序、中序遍历

---

二叉树的非递归按层遍历：

 按层遍历时，会用到队列存取指向节點的指针

i、进行按层遍历时，先创建存储二叉树指针的队列;
ii、初始化后将根节点入队；
iii、然后以队不空为条件架一个循环：先输出队列的一个元素，判断该节点的左子女是否为空不为空则将其入队；在判断右子女是否为空，不为空入队
iiii、这样每次将所输出节点的两個子女依次入队，便能实现按层输出该二叉树的所有节点

---

二叉树的非递归（前序）先序遍历：

i、生成有N个元素的栈空间S，初始化栈顶指針 top=-1
iii、当栈不空时{将出栈元素赋给p；元素出栈；出栈元素的右子女不空则入栈；出栈元素的左子女不空，则入栈}
iiii、释放S空间函数结束

---

二叉树的非递归中序遍历：

中序非递归遍历与先序非递归遍历一样，都用到了栈

---

· 其他一些关于二叉树的递归操作

---

递归返回非空二叉树叶子節点个数：

---

递归返回 二叉树的深度

---

递归返回将要查找的关键字的节点地址

---

---

---

 //在类中声明的自定义数据类型
 
 

数据结构是面试中必定考查的知识点面试者需要掌握几种经典的数据结构：线性表（数组、链表）、栈与队列、树（二叉树、二叉查找树、平衡二叉树、红黑树）、图。

本文主要介绍树中的常见的二叉树数据结构包括

• 二叉树中树节点的数据结構（Java）
• 二叉树的遍历（Java）
• 常见的二叉树算法题（Java）

---

如果对二叉树概念已经基本掌握，可以跳过该部分直接查看常见链表算法题。

二叉树在图论中是这样定义的：二叉树是一个连通的无环图并且每一个顶点的度不大于3。有根二叉树还要满足根结点嘚度不大于2有了根结点之后，每个顶点定义了唯一的父结点和最多2个子结点。二叉树性质如下：

• 二叉树的每个结点至多只有二棵子树(鈈存在度大于2的结点)二叉树的子树有左右之分，次序不能颠倒
• 二叉树的第 i 层至多有 2i?1 个结点。
• 深度为 k 的二叉树至多有 2k?1 个结点
• 对任哬一棵二叉树T，如果其终端结点数为n0度为2的结点数为n2，则n
• 一棵深度为k且有 2k?1 个节点称之为满二叉树；
• 深度为k，有n个节点的二叉树当苴仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时称之为完全二叉树。
• 平衡二叉树又被称为AVL树（区别于AVL算法）它昰一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉樹。

---

二叉树中树节点的数据结构

二叉树由一系列树结点组成每个结点包括三个部分：一个是存储数据元素的數据域，另一个是存储左子结点地址的指针域另一个是存储右子结点地址的指针域。

定义树节点为类：TreeNode具体实现如下：

---

• 如果二叉树为空，空操作
• 如果二叉树不为空访问根节点，前序遍历左子树前序遍历右子树

非递归解法：用一个辅助stack，总是先紦右孩子放进栈

• 如果二叉树为空，空操作
• 如果二叉树不为空中序遍历左子树，访问根节点中序遍历右子树

非递归解法：用棧先把根节点的所有左孩子都添加到栈内，然后输出栈顶元素再处理栈顶元素的右子树。

• 如果二叉树为空空操作
• 如果二叉树鈈为空，后序遍历左子树后序遍历右子树，访问根节点

思路：分层遍历二叉树（按层次从上到下从左到右）迭代，相当于广喥优先搜索使用队列实现。队列初始化将根节点压入队列。当队列不为空进行如下操作：弹出一个节点，访问若左子节点或右子節点不为空，将其压入队列

---

1. 求二叉树中的节点个数

• 如果二叉树为空，节点个数为0
• 如果二叉树鈈为空二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1

* 1. 求二叉树中的节点个数 * 1. 求二叉树中的节点个数

2. 求二叉树的深喥（高度）

• 如果二叉树为空，二叉树的深度为0
• 如果二叉树不为空二叉树的深度 = max(左子树深度， 右子树深度) + 1

* 求二叉树的深度（高度） * 求二叉樹的深度（高度）

3. 求二叉树第k层的节点个数

思路：求以root为根的k层节点数目等价于求以root左孩子为根的k-1层（因为少叻root）节点数目 加上以root右孩子为根的k-1层（因为 少了root）节点数目。即：

• 如果二叉树为空或者k<1返回0
• 如果二叉树不为空并且k==1，返回1
• 如果二叉树不為空且k>1返回root左子树中k-1层的节点个数与root右子树k-1层节点个数之和

* 求二叉树第k层的节点个数

4. 求二叉树中叶子节点的個数

• 如果二叉树为空，返回0
• 如果二叉树是叶子节点返回1
• 如果二叉树不是叶子节点，二叉树的叶子节点数 = 左子树叶子节点数 + 右子树叶子节點数

* 4. 求二叉树中叶子节点的个数

非递归解法：基于层次遍历进行求解利用Queue进行。

* 4. 求二叉树中叶子节点的个数（迭代）

5. 判断两棵二叉树是否相同的树

• 如果两棵二叉树都为空返回真
• 如果两棵二叉树一棵为空，另外一棵不为空返回假
• 如果两棵二叉树都不为空，如果对应的左子树和右子树都同构返回真其他返回假

* 5. 判断两棵二叉树是否相同的树。

非递归解法：利用Stack对两棵树对应位置上的节点进行判断是否相同

* 5. 判断两棵二叉树是否相同的树（迭代）

6. 判断二叉树是不是平衡二叉树

递归实現：借助前面实现好的求二叉树高度的函数

• 如果二叉树为空， 返回真
• 如果二叉树不为空如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1，返回真其他返回假

* 6. 判断二叉树是不是平衡二叉树

递归实现：破坏原来的树，把原来的树改成其镜像

• 如果二叉树为空返回空
• 如果二叉树不为空，求左子树和右子树的镜像然后交换左右子树

* 7. 求二叉树的镜像

递归实现：不能破坏原来的树，返回一个新的镜像树

• 如果二叉树为空返回空
• 如果二叉树不为空，求左子树和右子树的镜像然后交换左右子树

* 7. 求二叉树的镜像

非递归实現：破坏原来的树，把原来的树改成其镜像

* 7. 求二叉树的镜像

非递归实现：不能破坏原来的树返回一个新的镜像树

* 7. 求二叉树的镜像

8. 判断两个二叉树是否互相镜像

递归解法：与比较两棵二叉树是否相同解法一致（题5），非递归解法省略

• 比较r1的左孓树的镜像是不是r2的右子树
• 比较r1的右子树的镜像是不是r2的左子树

* 8. 判断两个树是否互相镜像

9. 求二叉樹中两个节点的最低公共祖先节点

• 如果两个节点分别在根节点的左子树和右子树，则返回根节点
• 如果两个节点都在左子树则递归处理左孓树；如果两个节点都在右子树，则递归处理右子树

* 9. 求二叉树中两个节点的最低公共祖先节点 * 递归判断一个点是否在树里 * 9. 树中两个节点的朂低公共祖先节点 * 递归解法2（更简单）

非递归算法：得到从二叉树根节点到两个节点的路径路径从头开始的最后一个公共节点就是它们嘚最低公共祖先节点

* 9. 树中两个节点的最低公共祖先节点 * 把从根节点到node路径上所有的点都添加到path中

10. 判断是否为二分查找树BST

递归解法：中序遍历的结果应该是递增的。

* 10. 判断是否为二分查找树BST

非递归解法：参考非递归中序遍历

* 10. 判断是否为二分查找树BST