二叉樹基礎(chǔ)篇

?叉樹基礎(chǔ)篇?錄?叉樹的結(jié)構(gòu)?先定義?叉樹節(jié)點(diǎn)的結(jié)構(gòu)#define_CRT_SECURE_NO_WARNINGS#include<iostream>#include<stack>#include<queue>#defineEND'#'usingnamespacestd;typedefcharElemType;typedefstructBtNode{structBtNode*leftchild;//左孩?結(jié)點(diǎn)structBtNode*rightchild;//右孩?結(jié)點(diǎn)ElemTypedata;//char類型}BtNode,*BinaryTree;圖??叉樹節(jié)點(diǎn)的結(jié)構(gòu)：現(xiàn)有?個(gè)如下圖所?的?叉樹;?個(gè)?叉樹是由若?個(gè)結(jié)點(diǎn)組成的，因此要想建??個(gè)?叉樹，就要先創(chuàng)建?個(gè)個(gè)?叉樹結(jié)點(diǎn)，我們?先給出?叉樹結(jié)點(diǎn)創(chuàng)建和銷毀的code。BtNode*NewNode()//構(gòu)造?個(gè)新的?叉樹節(jié)點(diǎn){BtNode*s=(BtNode*)malloc(sizeof(BtNode));if(NULL==s)exit(1);memset(s,0,sizeof(BtNode));//此時(shí)左右孩?節(jié)點(diǎn)也都指向空了returns;}voidFreeNode(BtNode*node)//釋放?個(gè)?叉樹節(jié)點(diǎn){free(node);node=nullptr;}?叉樹的建?我們將使?如下三種?法建??個(gè)?叉樹。?法?利?遞歸BtNode*CreateTree1()//第?種?法創(chuàng)建?個(gè)?叉樹{BtNode*p=NULL;ElemTypeitem;scanf("%c",&item);if(item!=END){p=NewNode();p->data=item;p->leftchild=CreateTree1();p->rightchild=CreateTree1();}returnp;}?法?同利?遞歸，但使?這種?法建??叉樹時(shí)，需傳?參數(shù)BtNode*CreateTree2(constchar*&str)//引?{BtNode*p=NULL;if(NULL!=str&&*str!=END){p=NewNode();p->data=*str;p->leftchild=CreateTree2(++str);p->rightchild=CreateTree2(++str);}returnp;}?法三與?法?類似BtNode*CreateTree3(constchar**constpstr){BtNode*p=NULL;if(NULL!=pstr&&NULL!=*pstr&&**pstr!=END){p=NewNode();p->data=**pstr;p->leftchild=CreateTree3(&++*pstr);p->rightchild=CreateTree3(&++*pstr);}returnp;}先序遍歷?叉樹先序遍歷也叫做先根遍歷、前序遍歷，可記做根左右（?叉樹?結(jié)點(diǎn)向下先左后右）。遍歷規(guī)則是：?先訪問根結(jié)點(diǎn)然后遍歷左?樹，最后遍歷右?樹。在遍歷左、右?樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左?樹，最后遍歷右?樹，如果?叉樹為空則返回。例如：這顆?叉樹的先序遍歷結(jié)果是：ABCDEFGH。遍歷?叉樹有多種?法，總的來說可以分為遞歸和?遞歸兩種形式。遞歸形式voidPreOrder(BtNode*p)/*先序遞歸遍歷*/{if(p!=NULL){printf("%c",p->data);PreOrder(p->leftchild);//遍歷左?樹PreOrder(p->rightchild);//遍歷右?樹}}?遞歸形式voidNicePreOrder(BtNode*p)/*先序?遞歸遍歷*/{if(p==NULL)return;std::stack<BtNode*>st;st.push(p);while(!st.empty()){p=st.top();st.pop();std::cout<<p->data<<"";if(p->rightchild!=NULL){st.push(p->rightchild);}if(p->leftchild!=NULL){st.push(p->leftchild);}}std::cout<<std::endl;}在先序?遞歸遍歷中，使?到了棧來存儲(chǔ)?叉樹的每?個(gè)結(jié)點(diǎn)。1.如果棧不為空，則獲取當(dāng)前棧頂元素，并將棧頂元素pop，接著打印當(dāng)前元素(即結(jié)點(diǎn))的值。2.然后再判斷當(dāng)前結(jié)點(diǎn)的右孩?結(jié)點(diǎn)是否為空，如果不為空，則將當(dāng)前結(jié)點(diǎn)的右孩?結(jié)點(diǎn)?棧。接下來在判斷當(dāng)前結(jié)點(diǎn)的左孩?是否為空，如果不為空，則將當(dāng)前結(jié)點(diǎn)的左孩?結(jié)點(diǎn)?棧。這?之所以先判斷右孩?結(jié)點(diǎn)然后再判斷左孩?結(jié)點(diǎn)，是因?yàn)闂５奶攸c(diǎn)是，先進(jìn)后出。只有右孩?結(jié)點(diǎn)先?棧，左孩?結(jié)點(diǎn)后?棧，這樣左孩?才會(huì)先被訪問，訪問棧的元素時(shí)才能和先序遍歷的規(guī)則相符合，即先訪問左結(jié)點(diǎn)再訪問右結(jié)點(diǎn)。中序遍歷?叉樹中序遍歷（LDR）也叫做中根遍歷、中序周游。遍歷規(guī)則是中序遍歷?先遍歷左?樹，然后訪問根結(jié)點(diǎn)，最后遍歷右?樹。若?叉樹為空則結(jié)束返回，否則：（1）中序遍歷左?樹（2）訪問根結(jié)點(diǎn)（3）中序遍歷右?樹例如：這顆?叉樹的中序遍歷結(jié)果是：CBEDFAGH遞歸形式voidInOrder(BtNode*p)/*中序遞歸遍歷*/{if(p!=NULL){InOrder(p->leftchild);//遍歷左?樹printf("%c",p->data);InOrder(p->rightchild);//遍歷右?樹}}?遞歸形式voidNiceInOrder(BtNode*p)/*中序?遞歸遍歷*/{if(p==NULL)return;std::stack<BtNode*>st;while(!st.empty()||p!=NULL){while(p!=NULL){st.push(p);p=p->leftchild;}p=st.top();st.pop();std::cout<<p->data<<"";p=p->rightchild;}std::cout<<std::endl;}在中序?遞歸遍歷中，使?到了棧來存儲(chǔ)?叉樹的每?個(gè)結(jié)點(diǎn)。1.?先，如果棧不為空或?叉樹不為空則進(jìn)?主循環(huán)。2.進(jìn)?主循環(huán)后，如果是?叉樹不為空，則進(jìn)??循環(huán)，將當(dāng)前結(jié)點(diǎn)和當(dāng)前結(jié)點(diǎn)的左孩?結(jié)點(diǎn)全部?棧。3.?循環(huán)結(jié)束后，說明此時(shí)已到到左?樹的最左結(jié)點(diǎn)，類似于圖中的結(jié)點(diǎn)C4.接著獲取當(dāng)前棧頂元素，并將棧頂元素pop，接著打印當(dāng)前元素(即結(jié)點(diǎn))的值。5.最后，讓當(dāng)前結(jié)點(diǎn)變?yōu)樗挠液?結(jié)點(diǎn)，如果它的右孩?結(jié)點(diǎn)為空，則會(huì)打印它??即根結(jié)點(diǎn)的值，若不為空則會(huì)繼續(xù)遍歷它的右?樹。后序遍歷?叉樹后序遍歷（LRD）是?叉樹遍歷的?種，也叫做后根遍歷、后序周游，可記做左右根。遍歷?法：中序遍歷?先遍歷左?樹，然后訪問根結(jié)點(diǎn)，最后遍歷右?樹。若?叉樹為空則結(jié)束返回，否則：（1）中序遍歷左?樹（2）訪問根結(jié)點(diǎn)（3）中序遍歷右?樹例如：這顆?叉樹的中序遍歷結(jié)果是：CEFDBHGA遞歸形式voidPastOrder(BtNode*p)/*后序遞歸遍歷*/{if(p!=NULL){PastOrder(p->leftchild);//遍歷左?樹PastOrder(p->rightchild);//遍歷右?樹printf("%c",p->data);}}?遞歸形式voidNicePastOrder(BtNode*p)/*后序?遞歸遍歷*/{if(p==NULL)return;std::stack<BtNode*>st;BtNode*tag=NULL;while(!st.empty()||p!=NULL){while(p!=NULL){st.push(p);p=p->leftchild;}p=st.top();st.pop();if(p->rightchild==NULL||p->rightchild==tag){std::cout<<p->data<<"";tag=p;p=NULL;}else{st.push(p);p=p->rightchild;}}std::cout<<std::endl;}在后序?遞歸遍歷中，使?到了棧來存儲(chǔ)?叉樹的每?個(gè)結(jié)點(diǎn)。打印?叉樹某?層的所有結(jié)點(diǎn)/*打印第k層所有節(jié)點(diǎn)的值*/voidPrintK(structBtNode*ptr,intk){if(ptr!=NULL&&k==0)/*當(dāng)k=0時(shí)就到了樹的第K層了*/{std::cout<<ptr->data<<"";}elseif(ptr!=NULL){PrintK(ptr->leftchild,k-1);PrintK(ptr->rightchild,k-1);}}以打印第三層為例，因?yàn)?叉樹中根結(jié)點(diǎn)所在的那?次為第0層，所以結(jié)點(diǎn)CDH所存在的那?層為第2層，因此k為2。具體的過程圖如下：最終的打印結(jié)果：計(jì)算?叉樹的所有結(jié)點(diǎn)個(gè)數(shù)/*樹所有節(jié)點(diǎn)的個(gè)數(shù)*/intGetSize(structBtNode*ptr){if(ptr==NULL)return0;elsereturnGetSize(ptr->leftchild)+GetSize(ptr->rightchild)+1;//這?的+1，相當(dāng)于+ptr這個(gè)節(jié)點(diǎn)}最終的打印結(jié)果：計(jì)算?叉樹的深度/*樹的深度*/intGetDepth(structBtNode*ptr){if(ptr==NULL)return0;elsereturnstd::max(GetDepth(ptr->leftchild),GetDepth(ptr->rightchild))+1;//這?的+1，相當(dāng)于+ptr這個(gè)節(jié)點(diǎn)的這?層}最終左?樹（紅?）的深度為4，右?樹（綠?）的深度為3，取max，因此這顆?叉樹的深度為4。最終的打印結(jié)果：查找?叉樹中值為value的節(jié)點(diǎn)/*查找?叉樹中值為value的節(jié)點(diǎn)*/structBtNode*FindValue(structBtNode*ptr,ElemTypeval){if(ptr==NULL||ptr->data==val){returnptr;}else{structBtNode*p=FindValue(ptr->leftchild,val);if(NULL==p)/*左邊沒有找到*/{p=FindValue(ptr->rightchild,val);}returnp;}}實(shí)現(xiàn)該查找函數(shù)的主要?法還是遞歸，即不斷的在左?樹和右?樹中查找。尋找某?節(jié)點(diǎn)的雙親節(jié)點(diǎn)structBtNode*Parent(structBtNode*ptr,structBtNode*child)//ptr為?叉樹的根結(jié)點(diǎn)（??），child是要尋找雙親結(jié)點(diǎn)的孩?結(jié)點(diǎn){if(ptr==NULL||ptr->leftchild==child||ptr->rightchild==child)//找到了{(lán)returnptr;}else{structBtNode*p=Parent(ptr->leftchild,child);//在左?樹尋找if(NULL==p){p=Parent(p