1、先序遍历

void preorder(node* root) {
    if (root == NULL) {
        return;
    }
    printf("%d", root->data);
    preorder(root->lchild);
    preorder(root->rchild);
}

2、中序遍历

//中序遍历
void inorder(node* root) {
    if (root == NULL) {
        return;
    }
    inorder(root->lchild);
    printf("%d", root->data);

    inorder(root->rchild);
}

3、后序遍历

//后序遍历
void postorder(node* root) {
    if (root == NULL) {
        return;
    }
    postorder(root->lchild);
    

    postorder(root->rchild);
    printf("%d", root->data);
}

4、层序遍历
1、用BFS模板来记忆真的挺好的
2、注意队列用的node*，这样就很好了！

//层序遍历
void leverorder(node* root) {
queue<node*> q;
q.push(root);
while (!q.empty()) {
node temp = q.front();
q.pop();
printf("%d", temp->data);
if (temp->lchild != NULL) {
q.push(temp->lchild);
}
if (temp->rchild != = NULL) {
q.push(temp->right);
}
}
}

5、求节点层数

//
计算每个节点所在的层次
struct node {
int data; //数据域
int layer; //层次
node* lchild; //左孩子
node* rchild; //右孩子
};

//需要在根节点入队前就先令根节点层次为1,来表示根节点是第一层
//之后now->lchild,now->rchild入队前，把它们的层号+1

void layerorder(node* root) {
queue<node> q;
root->layer = 1;
q.push(root);
while (!q.empty()) {
node now = q.front();
q.pop();
printf("%d", root->layer);
if (root->lchild != NULL) {
now->lchild->layer = now->layer + 1;
q.push(now->lchild);
}
if (root->rchild != NULl) {
now->rchild->layer = now->layer + 1;
q.push(now->rchild);
}
}
}

6、知道先、中序列，合成一棵树

node* create(int preL, int preR, int inL, int inR) {
if (preL < preR) {
return NULL; //先序序列长度小于等于0，直接返回
}

node* root = new node;  //新建新的一个节点，用来存放当前二叉树的根节点
root->data = pre[preL]; //新节点的数据域为根节点的值
int k;

for (int k = inL;k <= inR; k++) {
    if (in[k] == pre[preL]) {   //在中序序列找到in[k] == pre[L]的结点
        break;
    }
}

int numLeft = k - inL;  //左子树的结点个数

//左子树的先序区间为[preL+1,preL+numLeft],中序区间为[inL,k-1]
//返回左子树的根节点地址，复制给root的左指针
root->lchild = create(preL + 1, preL + numLeft, intL, k - 1);

//右子树的先序区间为[preL + numLeft + 1,preR],中序为[k+1,inR]   //看出来了吗，只有中序才用了k
root->rchild = create(pre + numleft + 1, preR, k + 1, inR);

return root; //返回根节点地址

}