struct node{
typename data;
node *lchild;
node *rchild;
}
node* newnode(int v){
node* Node=new node;
Node->data=v;
Node->lchild=Node->rchild=NULL;
return Node;
}
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);
}
void insert(node* &root,int x){
if(root==NULL){
root=newnode(x);
return;
}
if(插入左子树){
insert(root->lchild,x);
}else{
insert(root->rchild,x);
}
}
node *create(int data[],int n){
node *root=NULL;
for(int i=0;i<n;i++){
insert(root,data[i]);
}
return root;
}
void preOrder(Node* root)
{
if(root==NULL){
return;
}else{
cout<<root->data<<' ';
preOrder(root->Left);
preOrder(root->Right);
}
}
void inOrder(Node* root)
{
if(root==NULL){
return;
}else{
inOrder(root->Left);
cout<<root->data<<' ';
inOrder(root->Right);
}
}
void postOrder(Node* root)
{
if(root==NULL){
return;
}else{
postOrder(root->Left);
postOrder(root->Right);
cout<<root->data<<' ';
}
}
void LayerOrder(node *root){
queue<node*> q;
q.push(root);
while(!q.empty){
node* now=q.front();
q.pop();
cout<<now->data<<" ";
if(now->lchild!=NULL)
q.push(now->lchild);
if(now->rchild!=NULL)
q.push(now->rchild);
}
}
node *create(int preL,int preR,int inL,int inR)
{
if(preL>preR) return NULL;
node *root=new node;
root->data=pre[preL];
int k;
for(k=inL;k<=inR;k++){
if(in[k]==pre[preL]){
break;
}
}
int numLeft=k-inL;
root->lchild=create(preL+1,preL+numLeft,inL,k-1);
root->rchild=create(preL+numLeft+1,preR,k+1,inR);
return root;
}
node *create(int postL,int postR,int inL,int inR)
{
if(postL>postR) return NULL;
node *root=new node;
root->data=post[postR];
int k;
for(k=inL;k<=inR;k++){
if(in[k]==post[postR]){
break;
}
}
int numLeft=k-inL;
root->lchild=create(postL,postL+numLeft-1,inL,k-1);
root->rchild=create(postL+numLeft,postR-1,k+1,inR);
return root;
}
int Nodenum(Node* root)
{
if(root == NULL)
return 0;
else
return 1+Nodenum(root->Left)+Nodenum(root->Right);
}
int DepthOfTree(Node* root)
{
if(root)
{
if(DepthOfTree(root->Left)>DepthOfTree(root->Right))
return DepthOfTree(root->Left)+1;
else
return DepthOfTree(root->Right)+1;
}
if( root == NULL )
return 0;
}
int Leafnum(Node* root)
{
if(root==NULL)
return 0;
else if((root->Left==NULL) && (root->Right==NULL))
return 1;
else
return (Leafnum(root->Left)+Leafnum(root->Right)) ;
}