PAT---二叉树总结
二叉树的静态实现，能完全不使用指针来解题
- 二叉树定义
// 定义
struct Node{
int data; //数据域
int lchild;//指向左子树根结点的指针
int rchild;//指向右子树根结点的指针
}node[maxn];
- 新建结点
//新建结点
int index=0;
int newNode(int data){
node[index].data=data;
node[index].lchild=-1;
node[index].rchild=-1;
return index++;
}
- 插入
//插入
void insert(int &root,int x){
if(root==-1){
root=newNode(x);
return ;
}
if(由二叉树的性质x应该插在左子树){
insert(node[root].lchild,x);
}else{
insert(node[root].rchild,x);
}
}
- 创建
//创建
int Create(int data[],int n){
int root=-1;
for(int i=0;i<n;i++){
insert(root,data[i]);
}
return root;
}
- 查找
//查找
void search (int root,int x,int newdata){
if(root == -1){
return ;
}
if(node[root].data==x){
node[root].data=newdata;
}
search(node[root].lchild,x,newdata);
search(node[root].rchild,x,newdata);
}
- 先序遍历
//先序遍历
void preorder(int root){
if(root==-1){
return ;
}
printf("%d\n",node[root].data);
preorder(node[root].lchild);
preorder(node[root].rchild);
}
- 中序遍历
//中序遍历
void inorder(int root){
if(root==-1){
return ;
}
inorder(node[root].lchild);
printf("%d\n",node[root].data);
inorder(node[root].rchild);
}
- 后序遍历
//后序遍历
void postorder(int root){
if(root==-1){
return ;
}
postorder(node[root].lchild);
postorder(node[root].rchild);
printf("%d\n",node[root].data);
}
- 层序遍历
//层序遍历
void LayerOrder(int root){
queue<int > q;
q.push(root);
while(!q.empty()){
int now = q.front();
q.pop();
printf("%d ",node[root].data);
if(node[now].lchild!=-1) q.push(node[now].lchild);
if(node[now].rchild!=-1) q.push(node[now].rchild);
}
}
题目链接
1020 Tree Traversals (25)
1086 Tree Traversals Again (25)
1102 Invert a Binary Tree (25)
1119 Pre- and Post-order Traversals (30)
1127 ZigZagging on a Tree (30)
1138 Postorder Traversal (25)
1151 LCA in a Binary Tree (30)
