二叉树
目录
– 二叉树
– 节点结构
– 遍历顺序
– 用递归实现遍历
– 用非递归实现遍历
– 先序遍历
– 中序遍历
– 后序遍历
– 直观打印二叉树
– 特殊遍历
– 深度优先遍历
– 广度优先遍历
– 二叉树分类
– 搜索二叉树
– 完全二叉树
– 满二叉树
– 平衡二叉树
– 线索二叉树
节点结构
class Node<V>{
V value;
Node left;
Node right;
}
其实和链表类似, 但不会出现环
特别的:
+ 左孩子和右孩子都为空的节点称为叶节点
+ 最顶上的节点称为根节点 / 头节点
我们称一个子节点开头以下的所有节点为子树
遍历顺序
二叉树的遍历要用到递归的思想
我们把递归的顺序称为递归序
一般有三种遍历方法:
+ 先序遍历: 头 -> 左 -> 右
+ 中序遍历: 左 -> 头 -> 右
+ 后序遍历: 左 -> 右 -> 头
中序遍历中, A节点的下一个节点成为A的 后继节点
中序遍历中, A节点的上一个节点成为A的 前驱节点
用递归实现遍历
标准的递归代码如下:
void preOrder(Node node){
if(node == null){
return;
}
// 1
preOrder(node.left);
// 2
preOrder(node.right);
// 3
}
三种遍历的顺序都可以由上述递归序加工而来, 例如:
+ 在1处打印, 就是先序遍历
+ 在2处打印, 就是中序遍历
+ 在3处打印, 就是后序遍历
用非递归实现遍历
所有递归的代码都可以改成非递归的代码
先序遍历
先准备一个栈, 将头节点压入栈中, 接下来的流程如下:
+ 栈中弹出一个节点cur
+ 处理(打印)cur
+ (如果有的话)先右后左将cur的孩子压入栈中
+ 循环
代码如下:
void preOrderUnRecur(Node head){
if(head != null){
stack<Node> stack;
stack.push(head);
while(!stack.empty()){
Node cur = stack.top();
stack.pop();
cout << cur.value << " "; // 处理
if(cur.right != null){
stack.push(cur.right);
}
if(cur.left != null){
stack.push(cur.left);
}
}
cout << endl;
}
}
中序遍历
流程是:
+ 先整棵树所有左侧进栈
+ 每弹出一个, 就先打印
+ 接着对其右树做同样的操作
代码如下:
void inOrderUnRecur(Node head){
if(head != null){
stack<Node> stack;
while(!stack.empty() || head != null){
if(head != null){
stack.push(head);
head = head.left;
}else{
head = stack.top();
stack.pop();
cout << head.value << " ";
head = head.right;
}
}
cout << endl;
}
}
可以把左的方向向下画, 右的方向向右水平画, 就比较好理解了
后序遍历
和先序遍历类似, 相当于将先序的”头左右”先改成”头右左”, 然后再逆序打印(通过一个辅助的栈实现), 相当于”左右头”
流程是:
+ 栈中弹出一个节点cur
+ cur压入收集栈
+ (如果有的话)先左后右将cur的孩子压入栈中
+ 循环
代码如下:
void posOrderUnRecur(Node head){
if(head != null){
stack<Node> stack;
stack.push(head);
stack<Node> help;
while(!stack.empty()){
Node cur = stack.top();
stack.pop();
help.push(cur);
if(cur.left != null){
stack.push(cur.left);
}
if(cur.right != null){
stack.push(cur.right);
}
}
while(!help.empty()){
cout << help.top().value << " ";
help.pop();
}
cout << endl;
}
}
直观打印二叉树
1
/ \
2 3
/ \ / \
代码如下:
string getSpace(int num)
{
string space = " ";
string buf;
for (int i = 0; i < num; i++)
{
buf += space;
}
return buf;
}
void printInOrder(Node *head, int height, string to, int len)
{
if (head == nullptr)
{
return;
}
printInOrder(head->right, height + 1, "v", len);
string val = to + " " + to_string(head->value) + " " + to;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val + getSpace(lenR);
cout << getSpace(height * len) + val << endl;
printInOrder(head->left, height + 1, "^", len);
}
void printTree(Node *head)
{
cout << "Binary Tree:" << endl;
printInOrder(head, 0, "H", 17);
cout << endl;
}
使用示例:
int main()
{
Node *head = new Node(1);
head->left = new Node(-222222222);
head->right = new Node(3);
head->left->left = new Node(4444);
head->right->left = new Node(55555555);
head->right->right = new Node(66);
head->left->left->right = new Node(777);
printTree(head);
return 0;
}
特殊遍历
深度优先遍历
就是先序遍历的非递归实现
广度优先遍历
也叫 宽度优先遍历 / 按层遍历
用队列实现, 流程是:
+ 头节点进队列
+ 每次从队列中弹出(从右边出)一个节点, 就处理(打印)
+ (如果有的话)先左后右将弹出节点的孩子进队列(左边进)
代码如下:
void levelOrder(Node head){
if(head != null){
queue<Node> queue;
queue.push(head);
while(!queue.empty()){
Node cur = queue.front();
queue.pop();
cout << cur.value << " ";
if(cur.left != null){
queue.push(cur.left);
}
if(cur.right != null){
queue.push(cur.right);
}
}
cout << endl;
}
}
二叉树分类
搜索二叉树
搜索二叉树是一种特殊的二叉树, 也叫二叉查找树, 二叉排序树
英文名: Binary Search Tree, BST
特点是: 左树<头<右树
+ 每个节点都大于其左子树的所有节点的值
+ 每个节点都小于其右子树的所有节点的值
+ 每个节点的左右子树都是搜索二叉树
直观图:
6
/ \
4 8
/ \ / \
2 5 7 9
/
1...
判断方法: 中序遍历
+ 如果是搜索二叉树, 那么中序遍历的结果是递增的
+ 一旦中序遍历有降序, 那么就不是搜索二叉树
代码如下:
非递归实现
bool isBST(Node head){
if(head != null){
stack<Node> stack;
int pre = INT_MIN;
while(!stack.empty() || head != null){
if(head != null){
stack.push(head);
head = head.left;
}else{
head = stack.top();
stack.pop();
if(head.value < pre){
return false;
}
pre = head.value;
head = head.right;
}
}
return true;
}
return false;
}
递归实现
// 全局变量
int pre = INT_MIN;
bool isBST(Node head){
if(head == nullptr){
return true;
}
if(!isBST(head.left)){
return false;
}
// 将原本是处理的逻辑, 写成比较的环节
if(head.value < pre){
return false;
}else{
pre = head.value;
}
return isBST(head.right);
}
完全二叉树
完全二叉树是一种特殊的二叉树, 也叫完美二叉树
英文名: Complete Binary Tree, CBT
特点是: 从上到下, 从左到右依次填满节点
+ 除了最后一层, 其他层的节点数都是满的
+ 最后一层的节点都靠左排列
直观图:
a
/ \
b c
/ \ / \
d e f g
/ \
h i ...
判断方法: 层序遍历
+ 如果有右孩子, 没有左孩子, 那么不是完全二叉树, 直接false
+ 在不违反上一条规则的情况下: 如果出现了左右孩子不双全的节点, 那么后面的节点都必须是叶节点, 否则false
代码如下:
bool isCBT_flag = false;
bool isCBT(Node *head)
{
queue<Node *> q;
q.push(head);
Node *cur;
while (!q.empty())
{
cur = q.front();
q.pop();
Node *left = cur->left;
Node *right = cur->right;
if (isCBT_flag && (left != nullptr || right != nullptr) || (left == nullptr && right != nullptr))
{
return false;
}
if (left != nullptr)
{
q.push(left);
}
if (right != nullptr)
{
q.push(right);
}
else
{
isCBT_flag = true;
}
}
return true;
}
满二叉树
满二叉树是一种特殊的二叉树, 也叫真二叉树
英文名: Full Binary Tree, FBT
特点是: 每一层的节点数都是满的(包括最后一层)
+ 每一层的节点数都是满的
+ 每个节点的左右子树都是满二叉树
特别的, 从数学上来说, 如果该树的最大深度为h, 节点数为n, 那么有:
$$
n = 2^h – 1
$$
这是满二叉树的充要条件
直观图:
a
/ \
b c
/ \ / \
d e f g
判断代码如下:
struct FBT_return
{
int h;
int n;
FBT_return(int h, int n){
this->h = h;
this->n = n;
}
};
FBT_return FBT_process(Node *head)
{
if(head == nullptr)
return FBT_return(0, 0);
FBT_return left = FBT_process(head->left);
FBT_return right = FBT_process(head->right);
int h = max(left.h, right.h)+1;
int n = left.n + right.n + 1;
return FBT_return(h, n);
}
bool isFBT(Node *head)
{
FBT_return ans = FBT_process(head);
return ans.n == (1 << ans.h) - 1;
}
平衡二叉树
平衡二叉树是一种特殊的二叉树, 也叫AVL树(Adelson-Velskii and Landis)
英文名: Balanced Binary Tree, BBTree
之所以研究ta, 主要是希望二叉树查询的时间复杂度能够降低到O(logN)
特点是: 左右子树的高度差不超过1
+ 每个节点的左右子树的高度(深度)差不超过1
+ 每个节点的左右子树都是平衡二叉树
直观图:
a
/ \
b c
\ / \
d e f
\
g
图中是高度为4的最小平衡二叉树
代码如下:
struct BBT_return
{
bool isBBT;
int height;
BBT_return(bool isBBT, int height)
{
this->isBBT = isBBT;
this->height = height;
}
};
BBT_return BBT_process(Node *head)
{
if (head == nullptr)
{
return BBT_return(true, 0);
}
BBT_return left = BBT_process(head->left);
BBT_return right = BBT_process(head->right);
bool isBBT = left.isBBT && right.isBBT && abs(left.height - right.height) < 2;
int height = 1 + (left.height > right.height ? left.height : right.height);
return BBT_return(isBBT, height);
}
bool isBBT(Node *head)
{
return BBT_process(head).isBBT;
}
线索二叉树
线索二叉树是一种特殊的二叉树, 也叫Threaded Binary Tree
英文名: Threaded Binary Tree, TBT
特点是: 在二叉树的节点上, 除了有左右孩子指针, 还有指向前驱和后继的指针
+ 二叉树的每个节点都有指向前驱和后继的指针
+ 二叉树的每个节点都有左右孩子指针, 除了左右孩子指针, 还有指向前驱和后继的指针
其意义就是为了解决二叉树的遍历难问题, 使得遍历的时间复杂度降低到O(1)
缺点是: 会占用额外的空间, 并且这样的线索二叉树不可共用
