42.二叉树的常用操作。

0.森林转二叉树

还原：二叉树还原成森林。
1.加线条：若某节点的做孩子节点存在，则将这个左孩子的右孩子节点，右右孩子节点，右右右孩子节点...
都作为该节点的孩子用线链接起来。
有左孩子的右孩子，把他们连起来。然后断开右孩子的连线。
2.去线，只留下左边的连线和新连接的线。
3.再做调整。

1.二叉树的分类

• 普通二叉树、
• 完全二叉树(左右层级不会超过1个以上的深度)、
• 满二叉树(都满了，只能从最右边缺少叶子节点)。
• 斜树（左斜树，右斜树），相当于链表。

常用操作：
二叉搜索树（Binary Search Tree）又称B树。sql搜索优化。
哈弗曼树(哈夫曼编解码，节点带权的二叉树)
平衡二叉树（AVL树): 左右两个子树的高度差不会超过1，并且左右两颗子树都是一棵平衡二叉树，可以是一棵空树.
红黑树(平衡二叉树的搜索树)

2.二叉树的遍历（前序，中序，后续，层序）

根据前序+中序遍历，还原二叉树。
前序：ABCDEFGH
中序：BDCEAFHG 后序：DECB HGF A
要还原二叉树，必须知道2个顺序。否则由于二义性，必须要有中序+另外的一种顺序(前序/后序)。才能还原。
中序遍历的A，决定了BDCE在左子树，FHG在右子树。
DCE 在 B的右边。F根节点，

根节点什么时候被访问。先访问根节点叫前序，中间访问根节点的叫中序。
前序(根节点再最前)：先访问根节点，然后访问左节点(子树)，最后访问右节点(子树)。 ABDEC
中序(根节点在中)：先访问左节点(子树)，然后访问根节点，最后访问右节点(子树)。 DBEAC
后序(根节点在后)：先访问左节点(子树)，然后访问右节点(子树)，最后访问根节点。 DEBCA
层序遍历： ABCDE，使用队列来实现-先进先出。按层来遍历输出

#include <jni.h>
#include <string>
#include <android/log.h>
#include <queue>
#include <cmath>
using namespace std;

template<class T>
class TreeNode {
public:
    TreeNode(T data) {
        this->data = data;
    }
    T data; // 数据
    TreeNode *left = NULL;  // 左孩子(子树)
    TreeNode *right = NULL; // 右子树
};

// 获取树深度
int getDepthTree(TreeNode<char> *pNode) {
    if (pNode == NULL) {
        return 0;
    }
    int leftDepth = getDepthTree(pNode->left);
    int rightDepth = getDepthTree(pNode->right);
    return max(leftDepth, rightDepth) + 1; // 取最深的深度，然后+1.
}
// 是否平衡二叉树，依赖获取树的深度。
bool isBalanceTree(TreeNode<char> *pNode) {
    // 可以是一棵空树，左右子树的高度差不会超过 1 ，并且左右两棵子树都是一棵平衡二叉树
    if (pNode == NULL) {
        return true;
    }
    // 1.左右子树的高度差不会超过 1
    int leftDepth = getDepthTree(pNode->left);
    int rightDepth = getDepthTree(pNode->right);

    // 2.并且左右两棵子树都是一棵平衡二叉树
    return abs(leftDepth - rightDepth) <= 1 
            && isBalanceTree(pNode->left) 
            && isBalanceTree(pNode->right);
}

/**
 * 前序遍历 (必须写成模板才会通用) (方法的回调) 返回值void visit(T)，T是泛型的参数。
 * 先访问元素自己，再访问左右子树。
 * 思考：CSDN 排序的稳定性
 */
template<class T>
void preOrderTraverse(TreeNode<T> *pNode, void visit(T)) {// 怎么解决这个通用问题
    if (pNode == NULL) { // 0.递归结束条件
        return;
    }
    // 1.首先访问根节点
    visit(pNode->data);
    // 2.递归：然后访问左节点
    preOrderTraverse(pNode->left, visit);
    // 3.递归：最后再去访问右子树(节点)
    preOrderTraverse(pNode->right, visit);
}

// 打印访问的节点。
void visitNode(char data) {
    __android_log_print(ANDROID_LOG_ERROR, "TAG", "%c", data);
}
/**
 * 中序遍历
 */
template<class T>
void infixOrderTraverse(TreeNode<T> *pNode, void visit(T)) {// 怎么解决这个通用问题
    if (pNode == NULL) {
        return;
    }

    // 1.访问左子树
    infixOrderTraverse(pNode->left, visit);
    // 2.访问根节点
    visit(pNode->data);
    // 3.访问右子树
    infixOrderTraverse(pNode->right, visit);
}
// 后序遍历
template<class T>
void epilogueOrderTraverse(TreeNode<T> *pNode, void visit(T)) {// 怎么解决这个通用问题
    if (pNode == NULL) {
        return;
    }
    // 1.访问左子树
    epilogueOrderTraverse(pNode->left, visit);
    // 2.访问右子树
    epilogueOrderTraverse(pNode->right, visit);
    // 3.访问根节点
    visit(pNode->data);
}

// 层序遍历：使用队列，将根节点，左右子树压入队列，然后从队列中弹出item，访问item，同时将其左右子树压入队列。
template<class T>
void levelOrderTraverse(TreeNode<T> *pNode, void visit(T)) {// 怎么解决这个通用问题
    if (pNode == NULL) {
        return;
    }
    queue<TreeNode<T> *> nodeQ; // 辅助队列，存储节点指针。
    nodeQ.push(pNode);

    while (!nodeQ.empty()) {
        TreeNode<T> *front = nodeQ.front(); // 拿到item
        nodeQ.pop(); // 弹出item
        visit(front->data); // 打印节点

        if (front->left) {
            nodeQ.push(front->left); //队列压入左子树
        }
        if (front->right) {
            nodeQ.push(front->right); //队列压入右子树
        }
    }
}

extern "C"
JNIEXPORT jstring
JNICALL
Java_com_ndk_day42_MainActivity_stringFromJNI(
        JNIEnv *env,
        jobject /* this */) {

    TreeNode<char> *A = new TreeNode<char>('A');
    TreeNode<char> *B = new TreeNode<char>('B');
    TreeNode<char> *C = new TreeNode<char>('C');
    TreeNode<char> *D = new TreeNode<char>('D');
    TreeNode<char> *E = new TreeNode<char>('E');
    TreeNode<char> *F = new TreeNode<char>('F');
    TreeNode<char> *G = new TreeNode<char>('G');

    A->left = B;
    A->right = C;

    B->left = D;
    B->right = E;

    C->right = F; // 构成一棵树
    // F->left = G;

    /*__android_log_print(ANDROID_LOG_ERROR,"前序遍历","%c");
    // 遍历 （前序，中序，后序，层序）
    preOrderTraverse(A, visitNode);
    __android_log_print(ANDROID_LOG_ERROR,"中序遍历","%c");
    infixOrderTraverse(A, visitNode);
    __android_log_print(ANDROID_LOG_ERROR,"后序遍历","%c");
    epilogueOrderTraverse(A, visitNode);
    // 层序遍历
    __android_log_print(ANDROID_LOG_ERROR,"层序遍历","%c");
    levelOrderTraverse(A, visitNode);*/

    int depth = getDepthTree(A); // 求树的深度
    __android_log_print(ANDROID_LOG_ERROR, "TAG", "depth = %d", depth);

    bool isBalance = isBalanceTree(A); // 是否平衡二叉树
    __android_log_print(ANDROID_LOG_ERROR, "TAG", "isBalanceTree = %d", isBalance);
    std::string hello = "Hello from C++";
    return env->NewStringUTF(hello.c_str());
}

二叉树的序列化和反序列化。
二叉树的深度
判断平衡二叉树。

3.平衡二叉树

先求子树的深度，然后结合深度+递归，判断是否是平衡二叉树。

Java后台：
1.热门框架源码分析，设计模式。
2.微服务框架；
3.高并发与分布式
4.系统优化，jvm优化，sql优化。
5.搜索引擎。

---

二叉树遍历.png image.png