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)