二叉樹的創建以及利用迭代實現中序、先序、后序遍歷、清空 · C/C++算法

~~~ /* 二叉鏈表就是以鏈表為存儲結構存儲二叉樹 ,我么要像編號完全二叉樹一樣存儲普通的二叉樹。節點的聲明如下 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) ; } ~~~