# 二叉树相关操作

#include <bits/stdc++.h>
using namespace std;

typedef struct BTNode{
int data;
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode;

void create(BTNode *&p){
int i;
scanf("%d", &i);
if(i == 0)  p = NULL;
else{
p = (BTNode *)malloc(sizeof(BTNode));
p -> data = i;
create(p -> lchild);
create(p -> rchild);
}
}

void preOrder(BTNode *&root){
if(root){
printf("%d", root -> data);
preOrder(root -> lchild);
preOrder(root -> rchild);
}
}

void InOrder(BTNode *&root){
if(root){
InOrder(root -> lchild);
printf("%d", root -> data);
InOrder(root -> rchild);
}
}

void PostOrder(BTNode *&root){
if(root){
PostOrder(root -> lchild);
PostOrder(root -> rchild);
printf("%d", root -> data);
}
}

int main(){
BTNode *T = NULL;
create(T);
printf("\n先序遍历：");
preOrder(T);
printf("\n中序遍历：");
InOrder(T);
printf("\n后序遍历：");
PostOrder(T);
return 0;
}



#include <bits/stdc++.h>
using namespace std;

typedef struct BTNode{
int data;
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode;

int a[100];

void create(BTNode *&p, int n, int i){
if(i > n || a[i] == 0)  p = NULL; //a[i] = 0 为空节点
else{
p = (BTNode *)malloc(sizeof(BTNode));
p -> data = a[i];
create(p -> lchild, n, 2 * i);
create(p -> rchild, n, 2 * i + 1);
}
}

int main(){
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
scanf("%d", &a[i]);
BTNode *T = NULL;
create(T, n, 1);
return 0;
}


p和q都在左子树：

p和q都在右子树：

p和q分别在左右子树：

BTNode *lowerstCommonAncesor(BTNode *root, BTNode *p, BTNode *q){
if(root == null || root == p || root == q){
return root;
}
struct BTNode *left = lowerstCommonAncesor(root->lchild, p, q);
struct BTNode *right = lowerstCommonAncesor(root->rchild, p, q);
return left == NULL ? right : right == NULL ? left : root;
}


bool dfs(BTNode *root, int mi, int mx){
if(root == null)  return true;
if(root -> data <= mi || root -> data >= mx)  return false;
return dfs(root -> left, mi, root -> data) || dfs(root -> right, root -> data, mx);
}

void IsValidBST(BTNode *root, int mi, int mx){
dfs(root, INT_MIN, INT_MAX);
}


int MaxDepth(BTNode *bt){
if(bt == NULL)  return 0;
int hl = 1;
int hr = 1;
if(bt -> lchild)  hl += MaxDepth(bt -> lchild);
if(bt -> rchild)  hr += MaxDepth(bt -> rchild);
return hl > hr ? hl : hr;
}


typedef struct LNode{
int data;
struct LNode *next;
}LNode;

typedef struct BTNode{
int data;
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode;

LNode *GetMid(LNode *left, LNode *right){
LNode fast = left;
LNode slow = left;
while(fast != right && fast -> next != right){
fast = fast -> next -> next;
slow = slow -> next;
}
return slow;
}

BTNode *BuildTree(LNode *left, LNode *right){
if(left == right) return NULL;
LNode *mid = GetMid(left, right);
BTNode *root = new(BTNode);
root -> data = mid -> data;
root -> left = BuildTree(left, mid);
root -> right = BuildTree(mid -> next, right);
return root;
}

}


int dfs(BTNode *root){
if(root == NULL)    return 0;
int left = dfs(root -> lchild);
int right = dfs(root -> rchild);
if(left != -1 && right != -1 && abs(left - right) < 2){
return left > right ? left + 1 : right + 1;
}
else{
return -1;
}
}

bool isBalanced(BTNode* root) {
int ans = dfs(root);
return ans == -1 ? false : true;
}


bool check(BTNode *p, BTNode *q){
if(!p && !q)    return true;
if(!p || !q)    return false;
return p -> data == q -> data && check(p->lchild,q->rchild) && check(p->rchild,q->lchild);
}

bool isSymmetric(BTNode* root) {
return check(root, root);
}


bool hasPathSum(TreeNode* root, int targetSum) {
if(root == NULL)    return NULL;
if(root -> lchild == NULL && root -> rchild == NULL){
return targetSum == root -> data;
}
return hasPathSum(root -> lchild, targetSum - root->data) || hasPathSum(root -> rchild, targetSum - root->data);
}


void dfs(TreeNode *root, int &cnt){
if(root == NULL)    return ;
cnt ++;
dfs(root -> lchild, cnt);
dfs(root -> rchild, cnt);
}

int countNodes(TreeNode* root) {
int cnt = 0;
dfs(root, cnt);
return cnt;
}


typedef struct BTNode{
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode, *BinTree;

bool completeBTree(BTNOde *bt){
if(bt == NULL){
return 0;
}
BinTree queue[maxsize];
BinTree left, right;
bool leaf = false;
int front = 0, rear = 0;
rear = (rear + 1) % maxsize;
queue[rear] = bt;

while(rear != front){
front = (front + 1) % maxsize;
p = queue[front];
left = p -> lchild;
right = p -> rchild;
//当前节点有右孩子，但没有左孩子，直接返回false
//当前节点有左孩子，但没有右孩子，则接下来所有节点必须都是叶子节点
if((leaf && (leaf != NULL || right != NULL)) || (leaf = NULL && right != NULL)){
return -1;
}
if(leaf != NULL){
rear = (rear + 1) % maxsize;
queue[rear] = left;
}
if(right != null){
rear = (rear + 1) % maxsize;
queue[rear] = right;
}
if(left == null || right == null){
leaf = 1;
}
}
return true;
}


typedef struct BTNode{
int bf;
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode, *BinTree;

int height(BinTree bt){
int l = 0, r = 0;
if(bt == NULL)  return 0;
l = height(bt -> lchild);//遍历左子树
r = height(bt -> rchild);//遍历右子树
return (l > r ? l : r) + 1;//左子树与右子树个数多的为当前树的深度
}

void balance(BinTree bt){
int hl = 0;
int hr = 0;//记录左右子树的度
if(bt != NULL){
balance(bt -> lchild); //从树的底部开始计算
balance(bt -> rchild);
hl = height(bt -> lchild);  //当前节点左子树的度
hr = height(bt -> rchild);  //当前节点右子树的度
bt -> bf = hl - hr; //当前节点的平衡因子
}


typedef struct BTNode{
int weight;
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode, *BinTree;

int WPL(BinTree bt){
return wpl_PreOrder(bt, 0);
}

int wpl_PreOrder(BinTree bt, int deep){
static wpl = 0;
if(bt -> lchild == NULL && bt -> rchild == NULL){
wpl += deep * bt -> weight;
}
if(bt -> lchild != NULL)  wpl_PreOrder(bt -> lchild);
if(bt -> rchild != NULL)  wpl_PreOrder(bt -> rchild);
}


typedef struct BTNode{
int weight;
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode, *BinTree;

int wpl_levelOrder(BinTree bt){
int L = 0;  // 当前节点到根节点的距离
int wpl = 0;
BinTree p;
BinTree queue[maxsize];
int rear = 0, front = 0;

rear = (rear + 1) % maxsize;
queue[rear] = bt;

while(rear != front){
int len = (rear - front + 1) % maxsize;
for(int i = 0; i < len; i ++){  //循环遍历每一层节点
front = (front + 1) % maxsize;
p = queue[front];
if(p -> lchild == NULL && p -> rchild == NULL){
wpl += p -> weight * L;
}
if(p -> lchild != NULL){
rear = (rear + 1) % maxsize;
q[rear] = p -> lchild;
}
if(p -> rchild != NULL){
rear = (rear + 1) % maxsize;
q[rear] = p -> rchild;
}
}
L ++;
}
return wpl;
}


typedef struct BTNode{
int data;
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode, *BinTree;

void Elem_depth(BinTree T, int level, int *depth, int x){
if(T != NULL){
level ++;
if(T -> data == x)  depth = level;
}
Elem_depth(T -> lchild, level, depth, x);
Elem_depth(T -> rchild, level, depth, x);
}


typedef struct BTNode{
int data;
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode, *BinTree;

int L = 1;

void Elem_level(BinTree T, int x){
if(T != NULL){
if(T -> data == x){
cout << L << endl;
return ;
}
L ++;
Elem_level(T -> lchild, x);
Elem_level(T -> rchild, x);
L --;
}
}


typedef struct BTNode{
int data;
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode, *BinTree;

int Elem_Height(BinTree bt){
int l, r;
if(bt == NULL){
return 0;
}
else{
l = Elem_Height(bt -> lchild);
r = Elem_Height(bt -> rchild);
return (l > r ? l : r) + 1;
}
}

void Elem_Height(BinTree bt, int x){
if(bt != NULL){
if(bt -> data == x){
cout << getheight(bt) << endl;
}
Elem_Height(bt -> lchild);
Elem_Height(bt -> rchild);
}
}


typedef struct BTNode{
int data;
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode, *BinTree;

bool IsBST(BinTree bt){
if(bt == NULL)  return true;
else if(bt -> rchild == NULL && bt -> lchild == NULL) return true;
else if((bt -> lchild != NULL) && (bt -> rchild == NULL)){
if(bt -> lchild -> data <= bt -> data)  return true;
else  return IsBST(bt -> lchild);
}
else if((bt -> rchild != NULL) && (bt -> lchild == NULL)){
if(bt -> rchild -> data >= bt -> data)  return true;
else  return IsBST(bt -> rchild);
}
else{
if(bt -> lchild -> data > bt -> data || bt -> rchild -> data < bt -> data){
return false;
}
else{
return IsBST(bt -> lchild) && IsBST(bt -> rchild);
}
}
}


typedef struct BTNode{
int data;
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode, *BinTree;

void BiTree_Merge(BinTree &t, BiTree &s){//s合并到t中
if(s->lchild){
BiTree_Merge(t, s->lchild);
}
if(s->rchild){
BiTree_Merge(t, s->rchild);
}
insert_Node(t, s);//后序遍历插入节点
}

void insert_Node(BiTree &t, BTNode *s){//把s树上节点合并到t树中
if(s->data > t->data){//插入的节点大于当前节点，右子树查找位置
if(t -> rchild == NULL){
t -> rchild = s;
}
else{
insert_Node(t->rchild, s)//否则继续向右递归
}
}
else if(s->data < t->data){//插入的节点小于当前节点，左子树查找位置
if(t -> lchild != NULL){
t -> lchid = s;
}
else{
insert_Node(t->lchild, s);//否则继续向左递归
}
}
s -> rchild = NULL;//插入的新节点必须与原来节点断绝关系
s -> lchild = NULL;
}