树的一些操作,杂记
//新建结点数据类型
typedef struct{
typename data;
node* lchild;
node* rchild;
}Node;
//新建树结点
Node* new_node(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= new_node(x);
return; //空树,也就是查找失败,也就是插入位置
}
if(由二叉树的性质,x应该插在左子树)
{
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;
}
printf("%d",root->data);
preorder(root->lchild);
preorder(root->rchild);
}
//层序遍历
void layerorder(Node* root)
{
queue<Node*> queue;
queue.push(root);
while(!queue.empty())
{
Node* now=queue.front();
queue.pop();
printf("%d",now->data);
if(now->lchild!=NULL)
{
queue.push(now->lchild);
}
if(now->rchild!=NULL)
{
queue.push(now->rchild);
}
}
}
//加入 层 的树结点。
struct ndoe{
int data; //数据域
int layer; //层次
node* lchild;
node* rchild;
};
//新的层序遍历
void layerorder(Node* root)
{
queue<Node*> queue;
root->layer=1;
queue.push(root);
while(!queue.empty())
{
Node* now=queue.front();
queue.pop();
printf("%d",now->data);
if(now->lchild!=NULL)
{
now->lchild->layer=now->layer+1;
queue.push(now->lchild);
}
if(now->rchild!=NULL)
{
now->rchild->layer=now->layer+1;
queue.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;
//在中序序列中找到in[k] == pre[L]的结点
for(k=inL;k<=inR;k++)
{
if(in[k] == pre[preL] )
{
break;
}
}
//左子树的结点个数
int num_left = k-inL;
root->lchild=create(prL+1,preL+num_left,inL,k-1);
root->rchild=create(preL+num_left+1,preR,k+1,inR);
}