|
一、使用指针
/*
*二叉树的前序、中序、后序遍历
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
using namespace std;
typedef int ElemType;
typedef struct treeT{
ElemType key;
struct treeT* left;
struct treeT* right;
}*pTreeT;
int N;
pTreeT root;
void visit(pTreeT root){
if(root != NULL){
printf("%d\n",root->key);
}
}
pTreeT BT_MakeNode(ElemType target){ //创建一个新节点
pTreeT pNode = (pTreeT)malloc(sizeof(treeT));
//assert(pNode != NULL);
pNode->key = target;
pNode->left = NULL;
pNode->right = NULL;
return pNode;
}
pTreeT BT_Insert(pTreeT* root,ElemType target){
//pTreeT pNode = *root;
if((*root) == NULL)
return *root = BT_MakeNode(target);
if((*root)->key == target) //不允许有相同值
return NULL;
else if(target < (*root)->key)
return BT_Insert(&(*root)->left,target);
else
return BT_Insert(&(*root)->right,target);
}
void BT_PreOrder(pTreeT root){ //前序遍历
if(root == NULL) return;
visit(root);
BT_PreOrder(root->left);
BT_PreOrder(root->right);
}
void BT_InOrder(pTreeT root){ //中序遍历
if(root == NULL) return;
BT_InOrder(root->left);
visit(root);
BT_InOrder(root->right);
}
void BT_PostOrder(pTreeT root){ //后序遍历
if(root == NULL) return;
BT_PostOrder(root->left);
BT_PostOrder(root->right);
visit(root);
}
void Init(){
root = NULL;
ElemType target;
int i;
for(i = 0; i < N; i ++){
scanf("%d",&target);
//printf("*\n");
BT_Insert(&root,target);
}
}
int main(){
while(scanf("%d",&N)!=EOF){
Init();
BT_PreOrder(root); printf("\n");
BT_InOrder(root); printf("\n");
BT_PostOrder(root); printf("\n");
}
return 0;
}
二、使用数组
#include <iostream>
#include <cstdio>
#define MAXN 10005
using namespace std;
struct Node{
int val;
int l,r;
}Tree[MAXN];
int cnt; //树中的节点数
int N;
void Set_Node(int x){
Tree[x].val = -1;
Tree[x].l = Tree[x].r = -1;
}
void Insert(int u,int target){
if(target == Tree[u].val) return;
if(target < Tree[u].val){
if(Tree[u].l == -1){
Set_Node(++cnt);
Tree[u].l = cnt;
Tree[cnt].val = target;
return;
}else{
Insert(Tree[u].l,target);
}
}else{
if(Tree[u].r == -1){
Set_Node(++cnt);
Tree[u].r = cnt;
Tree[cnt].val = target;
return;
}else{
Insert(Tree[u].r,target);
}
}
}
void BT_PreOrder(int u){
printf("%d ",Tree[u].val);
if(Tree[u].l != -1) BT_PreOrder(Tree[u].l);
if(Tree[u].r != -1) BT_PreOrder(Tree[u].r);
}
void BT_InOrder(int u){
if(Tree[u].l != -1) BT_InOrder(Tree[u].l);
printf("%d ",Tree[u].val);
if(Tree[u].r != -1) BT_InOrder(Tree[u].r);
}
void BT_PostOrder(int u){
if(Tree[u].l != -1) BT_PostOrder(Tree[u].l);
if(Tree[u].r != -1) BT_PostOrder(Tree[u].r);
printf("%d ",Tree[u].val);
}
void Init(){
cnt = 0;
int target;
scanf("%d",&target);
Set_Node(++cnt);
Tree[cnt].val = target;
for(int i=1; i<N; i++){
scanf("%d",&target);
Insert(1,target);
}
}
int main(){
while(scanf("%d",&N) != EOF){
if(N <= 0) continue;
Init();
BT_PreOrder(1); puts("");
BT_InOrder(1); puts("");
BT_PostOrder(1); puts("");
}
return 0;
}
| 
转播
