/* 二叉链表就是以链表为存储结构存储二叉树 ,我么要像编号 完全二叉树一样 存储 普通的二叉树 。 节点的声明如下 node */ #include <iostream> using namespace std ; typedef struct node { int data ; node* lChild ; node* rChild ; }BTreeNode,*LinkTree ;
void CreateTree(LinkTree*pTree,int nIndex[],char ch[]) //nIndex是二叉树的节点编号数组 ch是节点数据 每个编号对应一个字符 nIndex 等于0时候结束 ch='#'结束 { int i =1 ;//用作下标 int j ;//当前双亲节点的下标 LinkTree temNode[50] ;//辅助建立二叉链表 BTreeNode *newNode =NULL;//用来指向新分配的节点空间 while(nIndex[i]!=0&&ch[i]!='#') //如果没有到达最后一个节点 { newNode=new BTreeNode ; newNode->data=ch[i] ; //为节点赋值 newNode->lChild=newNode->rChild=NULL ;//lChild=rChild=NULL temNode[nIndex[i]]=newNode ;//将这个新节点保存在辅助节点数组的指定编号为下标的元素中。 if(nIndex[i]==1) //如果是根节点的话那么我们将这个节点的地址保存在pTree中。 { *pTree=newNode ; } else { j=nIndex[i]/2 ;//获得双亲节点的编号 也就是数组下标 if(nIndex[i]%2==0) temNode[j]->lChild=newNode ; //编号基数那么是左子树 else temNode[j]->rChild=newNode ; //编号是偶数那么是右子树 } i++ ; //索引自加1 } } void Preorder(LinkTree pTree) //递归方式实现先序遍历 { if(pTree!=NULL) { cout<<pTree->data<<" " ; Preorder(pTree->lChild) ; Preorder(pTree->rChild) ; } } void Inorder(LinkTree pTree) //中序遍历 { if(pTree!=NULL) { Inorder(pTree->lChild) ; cout<<pTree->data<<" " ; Inorder(pTree->rChild) ; } } void Postorder(LinkTree pTree) //后序遍历 { if(pTree!=NULL) { Postorder(pTree->lChild) ; Postorder(pTree->rChild) ; cout<<pTree->data<<" "; } }
void Postorder(LinkTree pTree) //后序遍历 { if(pTree!=NULL) { Postorder(pTree->lChild) ; Postorder(pTree->rChild) ; cout<<pTree->data<<" "; } }
/* 按照层次进行遍历 需要用到队列 循环队列 思想是把所有的节点进队列 进入队列的节点输出data 然后将这个节点的lChild rChild 不为NULL的孩子节点进入队列 。 进行一个 Rear!=Front的while循环 */ void Traverse(BTreeNode*pTree) { BTreeNode* queue[MAX_SIZE] ; //指针队列数组保存遍历过的节点的指针 BTreeNode*tem=NULL; //临时指针保存出队列的节点 int Front = 0; int Rear = 0; if(pTree!=NULL) //初始化队尾为树的第一个节点 { Rear=(Rear+1)%MAX_SIZE; //队尾+1 queue[Rear]=pTree ; //节点指针进队尾 } while(Rear!=Front) { Front=(Front+1)%MAX_SIZE ; tem=queue[Front] ; cout<<tem->data<<" " ; if(tem->lChild!=NULL) //如果出队列的lChild不为空的话 那么进队列 { Rear=(Rear+1)%MAX_SIZE ; //lChild进队列 queue[Rear]=tem->lChild ;
} if(tem->rChild!=NULL ) //如果出队列的节点的rChild不为空的话 那么进队列 {
Rear=(Rear+1)%MAX_SIZE ; //rChild进队列 queue[Rear]=tem->rChild; }
}
}
void main() { LinkTree pTree ; int nIndex[]={9999,1,2,3,4,5,6,7,8,9,0} ; char ch[]={'?',1,2,3,4,5,6,7,8,9,'#'}; CreateTree(&pTree,nIndex,ch); cout<<"先序遍历结果:"<<endl ; Preorder(pTree) ; cout<<endl ; cout<<"中序遍历结果:"<<endl ; Inorder(pTree) ; cout<<endl ; cout<<"后续遍历结果:"<<endl ; Postorder(pTree) ; cout<<endl ;
ClearTree(&pTree) ;
}
