Bài giảng Cấu trúc dữ liệu 1: Chương 4B - Huỳnh Cao Thế Cường

Cây nhị phân là cây rỗng hoặc là cây mà mỗi nút có tối đa hai nút con. Các nút con của cây được phân biệt thứ tự rõ ràng, một nút con gọi là nút con trái và một nút con gọi là nút con phải. Trong chương này sẽ cung cấp cho người học những kiến thức về cây nhị phân (binary trees) và cách cài đặt cây nhị phân. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu 1: Chương 4B - Huỳnh Cao Thế Cường TRƯỜNGĐẠIHỌCANGIANGKHOAKỸTHUẬTCÔNGNGHỆMÔITRƯỜNG CẤUTRÚCDỮLIỆU1 Giảngviênphụtrách: HUỲNHCAOTHẾCƯỜNG BộmônTinhọc email:hctcuong@agu.edu.vn 1 1 CÂY NHỊ PHÂN (BINARY TREES)Địnhnghĩa  Câynhịphânlàcâyrỗnghoặclàcâymàmỗinútcótối đahainútcon.  Cácnútconcủacâyđượcphânbiệtthứtựrõràng • mộtnútcongọilànútcontrái • mộtnútcongọilànútconphải. • Taquiướcvẽnútcontráibêntráinútchavànútcon phảibênphảinútcha,mỗinútconđượcnốivớinút chacủanóbởimộtđoạnthẳng. 2Cây nhị phân 3Cây nhị phân 4 Cây nhị phân Duyệtcâynhịphân  Duyệttiềntự(NodeLeftRight):duyệtnútgốc,duyệt tiềntựcontráirồiduyệttiềntựconphải.  Duyệttrungtự(LeftNodeRight):duyệttrungtựcon tráirồiđếnnútgốcsauđólàduyệttrungtựconphải.  Duyệthậutự(LeftRightNode):duyệthậutựcontrái rồiduyệthậutựconphảisauđólànútgốc. 5Cây nhị phân 6 Cài đặt cây nhị phântypedef…TData;typedefstructTnode{ TDataData;//nhãn TNode*left TNode*right;};typedefTNode*TTree; 7 Cài đặt cây nhị phân Tạocâyrỗng:Câyrỗnglàmộtcâylàkhôngchứa mộtnútnàocả. voidMakeNullTree(TTree*T) { (*T)=NULL; } Kiểmtracâyrỗng intEmptyTree(TTreeT) { returnT==NULL; } 8 Cài đặt cây nhị phânXácđịnhcontráicủamộtnút TTreeLeftChild(TTreen) { if(n!=NULL)returnn>left; elsereturnNULL; }Xácđịnhconphảicủamộtnút TTreeRightChild(Ttreen) { if(n!=NULL)returnn>right; elsereturnNULL; } 9 Cài đặt cây nhị phânKiểmtranútlá:  Nếunútlànútláthìnókhôngcóbấtkỳmộtconnàocả nênkhiđócontráivàconphảicủanócùngbằngnil intIsLeaf(TTreen) { if(n!=NULL) return(LeftChild(n)==NULL) &&(RightChild(n)==NULL); elsereturnNULL; } 10 Cài đặt cây nhị phânXácđịnhsốnútcủacây intnb_nodes(TTreeT) { if(EmptyTree(T)) return0; else return1+nb_nodes(LeftChild(T)) +nb_nodes(RightChild(T)); } 11 Cài đặt cây nhị phânTạocâymớitừhaicâycósẵnTTreeCreate2(Tdatav,TTreel,TTreer){ TTreeN; N=(TNode*)malloc(sizeof(TNode)); N>Data=v; N>left=l; N>right=r; returnN;} 12 Cài đặt cây nhị phânThủtụcduyệttiềntựvoidPreOrder(TTreeT) { printf(%c,T>Data); if(LeftChild(T)!=NULL) PreOrder(LeftChild(T)); if(RightChild(T)!=NULL) PreOrder(RightChild(T)); } 13 Cài đặt cây nhị phânThủtụcduyệttrungtựvoidInOrder(TTreeT){ if(LeftChild(T)=!NULL) InOrder(LeftChild(T)); printf(%c,T>data); if(RightChild(T)!=NULL) InOrder(RightChild(T));} 14 Cài đặt cây nhị phânThủtụcduyệthậutựvoidPosOrder(TTreeT){ if(LeftChild(T)!=NULL) PosOrder(LeftChild(T)); if(RightChild(T)!=NULL) PosOrder(RightChild(T)); printf(%c,T>data);} 15