二叉树的创建、查找、插入、遍历

1 二叉树结构

struct node{int data;		//数据域 int layer;		//层次 node* lchild;	//指向左子树根结点的指针 node* rchild;	//指向右子树根结点的指针 
};

2 新建结点

//新建结点，v为结点权值 
node* newNode(int v){node* Node=new node;Node->data=v;Node->lchild=Node->rchild=NULL;return Node;
} 

3 查找、修改结点

//二叉树结点的查找、修改
void search(node* root,int x,int newdata){if(root==NULL)return;if(root->data==x)root->data=newdata;search(root->lchild,x,newdata);search(root->rchild,x,newdata);
} 

4 插入结点

//二叉树结点的插入
//如果需要新建结点（修改二叉树的结构）就需要加引用 
void insert(node* &root,int x){	//加了引用&，就会修改原变量 if(root==NULL){root=newNode(x);return;} if(root->data>x)insert(root->lchild,x);elseinsert(root->rchild,x);
}

5 创建二叉树

//二叉树的建立
node* Create(int data[],int n){node* root=NULL;for(int i=0;i<n;i++)insert(root,data[i]);return root;
}

6 遍历

6.1 先序遍历

//二叉树的先序遍历
void preorder(node* root){if(root==NULL)return;printf("%d\n",root->data);preorder(root->lchild);preorder(root->rchild);
}

6.2 中序遍历

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

6.3 后序遍历

//二叉树的后序遍历 
void postorder(node* root){if(root==NULL)return;postorder(root->lchild);postorder(root->rchild);printf("%d\n",root->data);
}

6.4 层序遍历

//层序遍历
void LayerOrder(node* root){	//注意是node*型变量 queue<node*> q;root->layer=1;q.push(root);while(!q.empty()){node* now=q.front();q.pop();printf("%d",now->data);if(now->lchild!=NULL){now->lchild->layer=now->layer+1;q.push(now->lchild);}if(now->rchild!=NULL){now->rchild->layer=now->layer+1;q.push(now->rchild);} }
} 

6.5 已知先序和中序遍历结果创建二叉树

//当前先序序列区间为[preL,preR],中序序列区间为[inL,inR],返回根结点地址
node* create(int preL,int preR,int inL,int inR){if(preL>preR)	//先序序列长度小于等于0时，直接返回 return NULL;node* root=new node;	//新建一个新的结点，用来存放当前二叉树的根节点root->data=pre[preL];int k;for(k=0;k<inR;k++){if(in[k]==pre[preL])break;} int numLeft=k-inL;	//左子树的结点个数//左子树的先序区间为[preL+1,preL+numLeft],中序区间为[inL,k-1]//返回左子树的根节点地址，赋值给root的左指针root->lchild=create(preL+1,preL+numLeft,inL,k-1);//右子树的先序区间为[preL+numLeft+1,preR],中序区间为[k+1,inR]//返回右子树的根节点地址，赋值给root的右指针root->lchild=create(preL+numLeft+1,preR,preR,k+1,inR);return root;
}