二叉树及其基本操作

一些概念(待补充)

·二叉树与度为2的树的区别:二叉树的左右子树严格区分,不能随意交换
·满二叉树与完全二叉树:满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树

二叉树的存储结构与基本操作

1.二叉树的存储结构

二叉链表

1
2
3
4
5
struct node{
typename data;
node* lchild;
node* rchild;
};

由于二叉树建树前根结点不存在,因此其地址一般设为NULL:

1
node* root=NULL;

新建结点(往二叉树中插入结点)

1
2
3
4
5
6
node* newNode(int v){
node* Node=new node;
Node->data=v;
Node->lchild=Node->rchild=NULL;
return Node;
}

关于申请node型地址空间,也可用(node* )malloc(sizeof(node)); 【关于malloc和new的区别这个问题对我来说暂且有点高深……

2.二叉树结点的查找、修改

查找操作是指在给定数据域的条件下,在二叉树中找到所有数据域为给定数据域的结点,并将它们的数据域修改为给定的数据域

1
2
3
4
5
6
7
8
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);
}

3.二叉树结点的插入

二叉树结点的插入位置就是数据域在二叉树中查找失败的位置
此处根结点指针root要使用引用

1
2
3
4
5
6
7
8
9
void insert(node* &root,int x){
if(root==NULL){
root=newNode(x); //新建数据域为x的结点
return;
}
if(??由题意要求的二叉树性质应该插在左子树){
insert(root->lchild,x);
}else insert(root->rchild,x);
}

4.二叉树的创建

实质为二叉树结点的插入过程

1
2
3
4
5
6
7
node* Create(int data[],int n){
node* root=NULL;
for(int i=0;i<n;i++){
insert(root,data[i]);
}
return root;
}

5.完全二叉树的存储结构

基于完全二叉树的性质,有更方便的存储方法,可通过建立一个2^n的数组来存放所有结点的信息
·在1号位存根结点的前提下,对于完全二叉树中的任何一个结点(编号x),其lchild一定为2x,rchild一定为2x+1
·该数组中元素存放的顺序恰好为该完全二叉树的层序遍历序列
·判断某个结点是否为叶子结点的标志为:该结点(x)的左子结点编号2x大于结点总个数n
·判断某个结点是否为空结点的标志为:该结点下标大于结点总个数n

二叉树的遍历

1.先序遍历

对一棵二叉树的先序遍历,序列的第一个一定是根结点

1
2
3
4
5
6
7
8
void preorder(node* root){
if(root==NULL){
return;
}
printf("%d",root->data); //访问根结点,例如输出数据域
preorder(root->lchild);
preorder(root->rchild);
}

2.中序遍历

只要知道根结点,就可以通过根结点在中序遍历序列中的位置区分出左右子树

1
2
3
4
5
6
7
8
void inorder(node* root){
if(root==NULL){
return
}
inorder(root->lchild);
printf("%d",root->data);
inorder(root->rchild);
}

3.后序遍历

对于后序遍历,序列的最后一个一定是根结点

1
2
3
4
5
6
7
8
void postorder(node* root){
if(root==NULL){
return;
}
postorder(root->lchild);
postorder(root->rchild);
printf("%d",root->data);
}

无论是先序还是后序,都必须知道中序遍历序列才能唯一地确定一棵树

4.层序遍历

与树的层序遍历同样套路
若要记录结点层次,则在node结构体中加设layer

1
2
3
4
5
6
struct node{
int data;
int layer;
node* lchild;
node* rchild;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void bfs(node* root){
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;
q.push(now->rchild);
}
}
}

给定先、中序重建二叉树

(给定先后序同理)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 numL=k-inL;
root->lchild=create(preL+1,preL+numL,inL,k-1);
root->rchild=create(preL+numL+1,preR,k+1,inR);
return root;
}

二叉树的静态实现

1
2
3
struct node{
int data,lchild,rchild; //通常用-1表示子树为空
}Node[maxn];

其他操作相应更改即可~

【手码一遍基础操作做一个归纳就酱…】