[計算機軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)06gj-文庫吧
2025-09-20 04:11 本頁面
【正文】 二叉樹的存儲結(jié)構(gòu) G F 216。 216。 216。 216。 E D C B A 一般二叉樹 216。表示該處沒有元素存在。 A C B D 216。 216。 E F G 216。 216。 存儲特點 ：適用于完全二叉樹 。對于非完全二叉樹，將浪費大量存貯單元 。不適合需要經(jīng)常插入、刪除樹中結(jié)點的操作。 若該二叉樹為非完全二叉樹，則必須將相應(yīng)位置空出來，使存放的結(jié)果符合完全二叉樹形狀。 二叉鏈表法 A B ^ ^ C D E ^ ^ F ^ ^ G ^ ^ H ^ rchild data lchild 二叉樹的存儲結(jié)構(gòu)（續(xù)） //二叉樹的二叉鏈表存儲表示 typedef struct BiTNode{ TElemType data。 struct BiTNode *lchild,*rchild。 } BiTNode,*BiTree。 二叉樹的鏈表存儲 基本操作函數(shù)原型 Status CreateBiTree(BiTree amp。T)； //按先序次序輸入二叉樹中結(jié) 點的值 (一個字符 ), //構(gòu)造二叉鏈表表示的二叉樹 T。 Status PreOrderTraverse(BiTree T, Status (*Visit)(BiTree t))； //先序遍歷 Status InOrderTraverse(BiTree T, Status (*Visit)(BiTree t))。 //中序遍歷 基本操作函數(shù)原型（續(xù)） Status PostOrderTraverse(BiTree T, Status (*Visit)(TElemType e))。 //后序遍歷 Status LevelOrderTraverse(BiTree T, Status (*Visit)(TElemType e))。 //層序遍歷 按某路徑對樹中每個結(jié)點訪問一次且僅一 次。 二叉樹的三個基本組成單元： 根結(jié)點（ D）、左子樹（ L）和右子樹（ R） 。 遍歷二叉樹的三種方案 先序遍歷 DLR 中序遍歷 LDR 后序遍歷 LRD 遍歷二叉樹和線索二叉樹 A B D C E F G H I K J 先序遍歷序列 :DLR A B D E H I K C F G J 先序遍歷示例 中序遍歷序列 :LDR D B H E K I A F C G J A B D C E F G H I K J 中序遍歷示例 A B D C E F G H I K J 后序遍歷序列 :LRD D H K I E B F J G C A 后序遍歷示例 最簡單的 Visit函數(shù) Status PrintElement(TElemType e){ printf(e)。 //輸出元素 e的值 return OK。//返回成功標志 } //前向遍歷原型 //PreOrderTraverse(BiTree T, Status(*Visit)(TElemTyep e)) //調(diào)用實例： PreOrderTraverse(T,PrintElement) 函數(shù)的聲明定義和調(diào)用？ Status PreOrderTraverse(BiTree T, Status (*Visit)(BiTree t)){ if(T){ if((*Visit)(T)) //訪問結(jié)點 if(PreOrderTraverse(Tlchild,Visit)) if(PreOrderTraverse(Trchild,Visit)) return OK。 return ERROR。 } else return OK。 } reO e 后序和中序遍歷？ 何時訪問了數(shù)據(jù) //中序遍歷 Status InOrderTraverse(BiTree T, Status (*Visit)(BiTree t)){ if(T){ if(InOrderTraverse(Tlchild, Visit)) if((*Visit)(T)) if(InOrderTraverse(Trchild, Visit)) return OK。 return ERROR。 } else return OK。 } e //后序遍歷 Status PostOrderTraverse(BiTree T, Status (*Visit)(BiTree e)){ if(T){ if(PostOrderTraverse(Tlchild,Visit)) if(PostOrderTraverse(Trchild,Visit)) if((*Visit)(T)) //訪問結(jié)點 return OK。 return ERROR。 } else return OK。 } e Status CreateBiTree(BiTree amp。T){ //先序次序輸入二叉樹中結(jié) 點的值 (一個字符 ), //空格符表空 樹 ,構(gòu)造二叉鏈表樹 T. char c。 c=getchar()。 if(c= =39。 39。) T = NULL。 else{T=(BiTNode *)malloc(sizeof(BiTNode))。 if(!T) exit(OVERFLOW)。 T–data=c。 CreateBiTree(Tlchild)。 CreateBiTree(Trchild)。 } return OK。 } ree 后序和中序遍歷？ Status InOrderTraverse(BiTree T, Status (*Visit)(BiTree t)){ InitStack(S)。Push(S,T)。//根指針進棧
教學課件相關(guān)推薦
鄂ICP備17016276號-1