目課程設計目 課程設計目 課程設計任 課程設計要 分析與設 題目需求分 結構設 算法描 程序流程 測試程序說 程序測 測試數 分 總 參考文 運用樹特別是二叉樹根據樹的相關概念了解樹的方法和算法及應用以及二叉樹的方法、遍歷、算法和應用。同時在此基礎上對樹和二叉樹的轉換的實現進行編程掌握。這次課程設計的目標是通過這次的課程設計，能夠使在數的訓練培養工作所需要的動手能力熟練的掌握數據結構有關知識的應用，分析樹和二叉樹的結構，二叉樹的結構如圖2.1圖2.1二叉樹的結構有三種結構，即雙親表示法、孩子表示法、和孩子兄弟表示法。事實上一棵樹采用孩子兄弟表示法所建立的結構與它所對應的二叉樹的二叉鏈表結構是完全相同的，只是兩個指針域的名稱及解釋不同而已,通2.2123、層次調整：以根結點為，將整棵樹旋轉，使之層次分明2.4一般樹的結構有以下幾種：雙親結點，孩子結點，孩子兄弟結點。本實驗運用到的是雙親結點和孩子兄弟結點。具體結構如下typedefstructst1/{chardata;//charstructst1*children[DEGREE];/typedefstructst2{chardata;//structst2*lchild,*rchild;/voidpreorderTree(CTreeNode{CTreeNode*ctchild;inti; }}

voidPreorder(BTreeNode*T){{cout<<T->data<<"";Preorder(T-}}CTreeNode*CreateSTree(parentNode=SearchCTree(root,parent)查找指定數據的結點。CTreeNode*CreateSTree(){intchardata,CTreeNode*root,*parentNode,*node;returnNULL;//空樹，結束函數root=(CTreeNode*)malloc(sizeof(CTreeNode));{node=(CTreeNode*)malloc(sizeof(CTreeNode));{if(parentNode-{}}}return}*CTreeArray[MAX_NODE_NUMtypedefstructnodeCTree{CTreeNode*CTreeArray[MAX_NODE_NUM];intCTreeFront,CTreeRear;typedefstruct{BTreeNode*BTreeArray[MAX_NODE_NUM];intBTreeFront,BTreeRear;下面是將樹轉換為二叉樹的主要程序段，ctroot一直向右，遇到的右均依次作為樹的(二叉樹中結點的右中變為該voidTreeToBTree(CTreeNode*ctroot,BTreeNode{QueueCTree*VisitedCTreeNodes;QueueBTree*VisitedBTreeNodes;//輔助隊列initQueueCTree(VisitedCTreeNodes);CTreeNode*ctnode;BTreeNode*btnode,*p,*LastSibling;inti;btroot=(BTreeNode*)malloc(sizeof(BTreeNode)); {{p=(BTreeNode*)malloc(sizeof(BTreeNode));

btnode-LastSibling-}}usingnamespacestd;#defineDEGREE5#defineNULL0#defineQUEUESIZE#defineMAX_NODE_NUMtypedefstructst1//樹結點的類{chardata;//數據域，采用charstructst1*children[DEGREE]typedefstructst2{chardatastructst2*lchild,*rchild;/CTreeNode*SearchCTree(CTreeNode*root,char{intCTreeNode*returnNode;returnroot;{{returnNULL;{return}}}}CTreeNode{intchardata,CTreeNode*root,*parentNode,*node;returnNULL;//空樹，結束函數root=(CTreeNode*)malloc(sizeof(CTreeNode));{cin>>data>>parent;//切記當以%c格式輸入數據時候，不要輸入空格node=(CTreeNode*)malloc(sizeof(CTreeNode));//printf("驗證parent=%c\n",parent);{{}}}return}voidpreorderTree(CTreeNode*ctroot)//遍歷每個節點的操作就是輸出該結點的data{CTreeNode*ctchild;inti;cout<<ctroot->data<<"";//先遍歷根結點{}}typedefstructnodeCTree{//structnodeCTree*next;int}typedefstructnodeBTree{//structnodeBTree*next;intvoidinitQueueCTree(QueueCTree{q=(QueueCTree*)malloc(sizeof(QueueCTree));}voidinitQueueBTree(QueueBTree{q=(QueueBTree*)malloc(sizeof(QueueBTree));}intaddQueueCTree(QueueCTree*&q,CTreeNode{return0;return1;//入隊}intaddQueueBTree(QueueBTree*&q,BTreeNode{return0;return1;//入隊}intQueueCTreeEmpty(QueueCTree{}intQueueBTreeEmpty(QueueBTree{}CTreeNode*delQueueCTree(QueueCTree{CTreeNodereturnNULL;//返回空指針returnctroot;//返回結}BTreeNode*delQueueBTree(QueueBTree{BTreeNodereturnNULL;//返回空指針returnbtroot;//返回節}voidTreeToBTree(CTreeNode*ctroot,BTreeNode*&btroot)//樹轉化為二叉樹ctroot{QueueCTree*VisitedCTreeNodes;QueueBTree*VisitedBTreeNodes;//輔助隊列CTreeNode*ctnode;BTreeNode*btnode,*p,*LastSibling;inti;btroot=(BTreeNode*)malloc(sizeof(BTreeNode));//添加開辟內存空間語句{{p=(BTreeNode*)malloc(sizeof(BTreeNode));//分配二叉樹結 }}}voidPreorder(BTreeNode{{cout<<T->data<<"";}}int{CTreeNode*Tree;BTreeNode*BTree;return0;}樹的先序遍歷結果：bac