void Creat(BiNode *&root,int i1,int i2,int len)
Node* &root，这个是指针的引用，
主要目的是为了通过在函数内改Node* root的值（注意区分所指的值的区别）， 实参（就是你调用时传入的参数）同步获得改变，也就相当于 “传址”， 否则就是“传值”了，应该明白了吧？
#include<stdio.h> void plus(int p, int *q){ p++; (*q)++; } main(){ int a = 1; int b = 1; plus(a, &b); // 把baia的值和b的地址传给plus函数du printf("a=%d, b=%d\n", a, b); // 经过plus处理，得到结zhi果，a不变，b变；dao void insert(node* &root,int data){//node* root=NULL;//定义头结点 if(root==NULL){//找到空节点，即为需要插入的位置 root=new node; root->data=data; root->left=root->right=NULL;//此句不能漏 return; } if(data<root->data)insert(root->left,data);//插在左子树 else insert(root->right,data);//插在右子树 } //16 //1043 Is It a Binary Search Tree (25分) //8 //38 24 12 45 58 67 42 51//（定义为左子树键值大，右子树键值小） //======================= //38 45 24 58 42 12 67 51//层序遍历的结果 //NO//输出YES，如果该树是完全二叉树；否则输出NO。 //1.用数组存储原始的序列 //2.根据原始的序列--建立二叉树 //3.根据建立的二叉树来获得对应的先序，镜像先序，后序，镜像后序的序列，用数组存储 //4.将先序/先序镜像序列与原始序列进行比较，输出“Yes”或“No”---如果是，输出相应后序/后序镜像数组的元素 #include <iostream> #include <cstdio> #include <vector> using namespace std; vector<int>origin,pre,preM,post,postM;//初始序列 struct node{ int data;//数据域 node *left,*right;//指针域 }; void insert(node* &root,int data){//node* root=NULL;//定义头结点 if(root==NULL){//找到空节点，即为需要插入的位置 root=new node; root->data=data; root->left=root->right=NULL;//此句不能漏 return; } if(data<root->data)insert(root->left,data);//插在左子树 else insert(root->right,data);//插在右子树 } void preOrder(node* root,vector<int> &vi){//先序遍历，结果存在vi if(root==NULL)return; vi.push_back(root->data); preOrder(root->left,vi); preOrder(root->right,vi); } //镜像树先序遍历，结果存在vi //所谓镜像树---是指交换二叉树所有左右子树而形成的树 //（左子树的所有节点大于或等于根节点） //（根节点数据域小于右子树所有节点的数据域）//-----二叉排序树 void preOrderMirror(node* root,vector<int>& vi){ if(root==NULL)return; vi.push_back(root->data); preOrderMirror(root->right,vi); preOrderMirror(root->left,vi); } void postOrder(node* root,vector<int> &vi){//后序遍历，结果存在vi if(root==NULL)return; postOrder(root->left,vi); postOrder(root->right,vi); vi.push_back(root->data); } //镜像树后序遍历，结果存在vi void postOrderMirror(node* root,vector<int> vi){ if(root==NULL)return; postOrderMirror(root->right,vi); postOrderMirror(root->left,vi); vi.push_back(root->data); } int main(){ int n,data; node* root=NULL;//定义头结点 cin>>n;//输入节点个数 for(int i=0;i<n;i++){ cin>>data; origin.push_back(data);//将数据加到origin insert(root,data);//将data插入二叉树 } preOrder(root,pre);//求先序--根左右 preOrderMirror(root,preM);//求镜像树先序--根右左 postOrder(root,post);///求后序 postOrderMirror(root,postM); if(origin==pre){//初始序列等于先序序列//origin.push_back(data);//将数据加到origin cout<<"YES\n"; for(int i=0;i<post.size();i++){ if(i==0)cout<<post[i]; else cout<<" "<<post[i]; } }else if(origin==preM){//初始序列等于镜像先序序列 cout<<"YES\n"; for(int i=0;i<postM.size();i++){ if(i==0)cout<<postM[i]; else cout<<" "<<postM[i]; } }else{ cout<<"NO\n"; } return 0; }二叉搜索树 1.使用vector数组来存放初始序列、先序序列、镜像树先序序列，可以方便相互之间的比较，若使用数组，则需要循环才能实现 2.定义根节点，要将其设为空节点（一开始没有元素），在新建节点时要注意把左右子节点的地址设为NULL
二叉树的建立（递归实现）
Node* build(Node* root, int val){ if(root == NULL){ root = new Node(); root->val = val; return root; } if(val < root->val) root->left = build(root->left, val); else if(val > root->val) root->right = build(root->right, val); return root; } #include <iostream> #include <cstdio> using namespace std; vector<int>origin;//初始序列 struct node{ int data;//数据域 node *left,*right;//指针域 }; void insert(node* &root,int data){//node* root=NULL;//定义头结点 if(root==NULL){//找到空节点，即为需要插入的位置 root=new node; root->data=data; root->left=root->right=NULL;//此句不能漏 return; } if(data<root->data)insert(root->left,data);//插在左子树 else insert(root->right,data);//插在右子树 } int main(){ int n,data; node* root=NULL;//定义头结点 cin>>n;//输入节点个数 for(int i=0;i<n;i++){ cin>>data; origin.push_back(data);//将数据加到origin insert(root,data);//将data插入二叉树 } return 0; }二叉树的先序遍历
class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new LinkedList<>(); preorderHelper(root, result); return result; } private void preorderHelper(TreeNode root, List<Integer> result) { if (root == null) return; result.add(root.val); // 访问根节点 preorderHelper(root.left, result); // 递归遍历左子树 preorderHelper(root.right, result); //递归遍历右子树 } } void preOrder(node* root,vector<int> &vi){//先序遍历，结果存在vi if(root==NULL)return; vi.push_back(root->data); preOrder(root->left,vi); preOrder(root0>right,vi); }二叉树的后序遍历 无论对于哪种方式，递归的方法总是很容易实现的，也是很符合直觉的。对于后序遍历，就是先访问左子树，再访问右子树，再访问根节点，即 左->右->根：
class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new LinkedList<>(); postorderHelper(root, result); return result; } private void postorderHelper(TreeNode root, List<Integer> result) { if (root == null) return; postorderHelper(root.left, result); // 遍历左子树 postorderHelper(root.right, result); // 遍历右子树 result.add(root.val); // 访问根节点 } } void postOrder(node* root,vector<int>& vi){//后序遍历，结果存在vi if(root==NULL)return; postOrder(root->left,vi); postOrder(root->right,vi); vi.push_back(root->data); } int main(){ int n,data; node* root=NULL;//定义头结点 cin>>n;//输入节点个数 for(int i=0;i<n;i++){ cin>>data; origin.push_back(data);//将数据加到origin insert(root,data);//将data插入二叉树 } preOrder(root,pre);//求先序--根左右 preOrderMirror(root,preM);//求镜像树先序--根右左 postOrder(root,post);///求后序 return 0; }与前序遍历和后序遍历相比，代码结构完全一致，差别仅仅是递归函数的调用顺序。
https://blog.csdn.net/weixin_44586473/article/details/90263261?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param#211__18
https://www.pianshen.com/article/7106254596/
完全二叉树
首先建立二叉搜索树, 其次需要层序遍历, 重点在于如何判断是完全二叉树,我们分成两种情况, 假设是一个n层的完全二叉树,那么2**(n-1) - 1等于前n - 1层的数目,通过这个,我们可以先判断出前n - 1层是否正确,对于最后一层,如果出现有节点有右子树,但是没有左子树,或者某个结点的左边的表兄弟节点没有左子树或右子树,但是自己却有子孩子,那也不是完全树.
在我写的代码里,emmm,我建立的二叉搜索树仍然是左孩子小于右孩子,这与题目不同,不过在进行层序遍历时,是先将右孩子加入队列,再加入左孩子,所以实质上还是一样的.所以在判断完全二叉搜索树时,所有的左都换成了右,所有的右都换成了左.
分析： 首先二叉搜索树， 我们根据定义建立就好， 但是如何判定其是不是完全二叉树呢？ 首先我们要先区别一下满二叉树和完全二叉树的区别。
满二叉树： 假设这个二叉树有n层，那么每一层的节点数都达到最大的二叉树。
完全二叉树：把最后一层去掉就是满二叉树， 同时最后一层： 我们假设最后一层里面如果是满的话是有n个节点， 我们从左往右标号1-n,那么最后一层如果想要有节点的话， 一定要按照标号顺序建立，不能隔过一个或多个标号去建立其他的节点。
完全二叉树
所以 我们分析一下 完全二叉树的特点： 我们按照层次顺序遍历这颗树的过程中，对于任意一节点x 1 》如果x 有右子树，但是却没有左子树，这肯定不是完全二叉树 2 》如果x 有左子树，但是却没有右子树，那么剩余的所有节点一定要为叶子节点 3 》如果 x 左右子树都没有，那么剩余的所有节点也要为叶子节点
