基本操作函數：

InitTree(Tree &T) 參數T，樹根節點 作用：初始化樹，先序遞歸創建
InsertNode(Tree &T, TElemType node) 插入樹的結點 參數：樹T,結點node 作用：在雙親數組中插入結點，增加樹的結點值
InsertParent(Tree &T, TElemType node1, TElemType node2)//插入雙親數組的雙親域 參數：樹T ，結點node1,結點node2
?????????????????????????????????????????????????????????????????????????????????? //作用：使雙親數組中,node2對應的雙親域為node1的下標
GetIndegree(Tree &T, TElemType node)?????????????????? //得到某結點入度 參數：樹T，結點node 結點不存在返回-1
GetOutdegree(Tree &T, TElemType node)????????????????? //得到某結點出度 參數：樹T，結點node 結點不存在返回-1
PreOrder(Tree T)? 參數：樹T,根節點下標 作用：先序遍歷樹
PostOrder(Tree T) 參數：樹T,根節點下標 作用：后序遍歷樹
LevelOrder(Tree T)參數：樹T??????????? 作用：層序遍歷樹

功能實現函數：

CreateTree(Tree &T) 參數T，樹根節點 作用：創建樹，調用InsertNode,InsertParent
Traverse(Tree T)??? 參數T，樹根節點 作用：PreOrder InOrder PostOrder LevelOrder遍歷樹

實驗所用樹：

實驗所用樹

創建及遍歷截圖：

創建及遍歷截圖

代碼：

/* Project: Tree_parent(樹-雙親表示法) Date: 2019/02/25 Author: Frank Yu 基本操作函數： InitTree(Tree &T) 參數T，樹根節點 作用：初始化樹，先序遞歸創建 InsertNode(Tree &T, TElemType node) 插入樹的結點 參數：樹T,結點node 作用：在雙親數組中插入結點，增加樹的結點值 InsertParent(Tree &T, TElemType node1, TElemType node2)//插入雙親數組的雙親域 參數：樹T ，結點node1,結點node2//作用：使雙親數組中,node2對應的雙親域為node1的下標 GetIndegree(Tree &T, TElemType node) //得到某結點入度 參數：樹T，結點node 結點不存在返回-1 GetOutdegree(Tree &T, TElemType node) //得到某結點出度 參數：樹T，結點node 結點不存在返回-1 PreOrder(Tree T) 參數：樹T,根節點下標 作用：先序遍歷樹 PostOrder(Tree T) 參數：樹T,根節點下標 作用：后序遍歷樹 LevelOrder(Tree T)參數：樹T 作用：層序遍歷樹 功能實現函數： CreateTree(Tree &T) 參數T，樹根節點 作用：創建樹，調用InsertNode,InsertParent Traverse(Tree T) 參數T，樹根節點 作用：PreOrder InOrder PostOrder LevelOrder遍歷樹 */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<string> #include<stack> #include<queue> #include<algorithm> #include<iostream> #define TElemType char #define Max 100 using namespace std; //樹的結點數據結構 typedef struct TNode {TElemType data;//數據域int parent; //雙親 }TNode; //樹的數據結構 typedef struct Tree {TNode parent[Max];int NodeNum;}Tree; //********************************基本操作函數********************************// //初始化樹函數 參數：樹T 作用：規定數據域為#，則為空，雙親為-1,則為空 void InitTree(Tree &T) {for (int i=0;i<Max;i++){T.parent[i].data = '#';T.parent[i].parent = -1;}T.NodeNum = 0; } //插入樹的結點 參數：樹T,結點node 作用：在雙親數組中插入結點，增加樹的結點值 bool InsertNode(Tree &T, TElemType node) {if (node != '#'){T.parent[T.NodeNum++].data = node;//插入到雙親數組中return true;}return false; } //插入雙親數組的雙親域 參數：樹T ，結點node1,結點node2 //作用：使雙親數組中,node2對應的雙親域為node1的下標 bool InsertParent(Tree &T, TElemType node1, TElemType node2) {int place1, place2;place1 = -1;place2 = -1;for (int i=0;i<T.NodeNum;i++)//查找兩點是否存在{if (node1 == T.parent[i].data)place1 = i;if (node2 == T.parent[i].data)place2 = i;}if (place1 != -1 && place2 != -1)//兩點均存在{T.parent[place2].parent = place1;return true;}return false; } //得到某結點入度 參數：樹T，結點node 結點不存在返回-1 int GetIndegree(Tree &T, TElemType node) {int place = -1;for (int i = 0;i<T.NodeNum;i++){if (T.parent[i].data == node)place = i;}if (place!=-1)//結點存在{if(T.parent[place].parent!=-1)return 1;//雙親只能有一個else return 0; //根節點沒有雙親，即沒有入度}return -1; } //得到某結點出度 參數：樹T，結點node 結點不存在返回-1 int GetOutdegree(Tree &T, TElemType node) {int place = -1;int outdegree = 0;for (int i = 0;i<T.NodeNum;i++){if (T.parent[i].data == node)place = i;}if (place != -1){for (int i = 0;i < T.NodeNum;i++){if (T.parent[i].parent == place)outdegree++;}return outdegree;}return -1; } //先序遍歷 參數：樹T,根節點下標 void PreOrder(Tree T,int i) {if (T.NodeNum != 0){cout << T.parent[i].data << " ";for(int j=0;j<T.NodeNum;j++){if(T.parent[j].parent==i)PreOrder(T,j);//按左右先序遍歷子樹}} } //后序遍歷 參數：樹T,根節點下標 void PostOrder(Tree T,int i) {if (T.NodeNum != 0){for (int j = 0;j<T.NodeNum;j++){if (T.parent[j].parent == i)PostOrder(T, j);//按左右先序遍歷子樹}cout << T.parent[i].data << " ";} } //層序遍歷 參數：樹T void LevelOrder(Tree T) {queue<TNode> q;//借助隊列if (T.NodeNum!=0){TNode temp;//暫存要出隊的結點q.push(T.parent[0]);//根結點入隊while (!q.empty())//隊列非空{temp = q.front();q.pop();cout<<temp.data<<" ";for (int j = 0;j<T.NodeNum;j++){if (T.parent[T.parent[j].parent].data == temp.data)//當前結點的父節點的數據域與彈出的相同 //因為temp沒有保存下標，只能按這種方式比較，默認結點名稱不同q.push(T.parent[j]);//隊列先進先出，先入左孩子}}} } //**********************************功能實現函數*****************************// //創建樹，調用InsertNode,InsertParent void CreateTree(Tree &T) {int nodenum = 0;int parent;TElemType node,node1,node2;printf("請輸入樹的結點個數:");cin >> nodenum;parent = nodenum - 1;printf("請輸入樹的結點名稱（空格隔開）:");while (nodenum--){cin >> node;InsertNode(T,node);}printf("請輸入樹的結點間的雙親關系（一對為一雙親關系，A B表示A為B的雙親）:\n");while (parent--){cin >> node1>>node2;InsertParent(T,node1,node2);}printf("\n"); } //入度 void Indegree(Tree &T) {TElemType node;int indegree;printf("請輸入結點名稱:\n");cin >> node;indegree = GetIndegree(T, node);if (-1 != indegree)cout << "該結點入度為：" << indegree << endl;elsecout << "結點不存在。" << endl; } //出度 void Outdegree(Tree &T) {TElemType node;int outdegree;printf("請輸入結點名稱:\n");cin >> node;outdegree = GetOutdegree(T, node);if (-1 != outdegree)cout << "該結點出度為：" << outdegree << endl;elsecout << "結點不存在。" << endl; } //遍歷功能函數 調用PreOrder InOrder PostOrder LevelOrder void Traverse(Tree T) {int choice;while (1){printf("********1.先序遍歷 2.后序遍歷*********\n");printf("********3.層次遍歷 4.返回上一單元*********\n");printf("請輸入菜單序號：\n");scanf("%d", &choice);if (4 == choice) break;switch (choice){case 1: {printf("樹先序遍歷序列:");PreOrder(T,0);printf("\n");}break;case 2: {printf("樹后序遍歷序列:");PostOrder(T,0);printf("\n");}break;case 3: {printf("樹層序遍歷序列:");LevelOrder(T);printf("\n");}break;default:printf("輸入錯誤！！！\n");break;}} } //菜單 void menu() {printf("********1.創建 2.某點入度*********\n");printf("********3.某點出度 4.遍歷*************\n");printf("********5.退出\n"); } //主函數 int main() {Tree T;int choice = 0;InitTree(T);while (1){menu();printf("請輸入菜單序號：\n");scanf("%d", &choice);if (5 == choice) break;switch (choice){case 1:CreateTree(T);break;case 2:Indegree(T);break;case 3:Outdegree(T);break;case 4:Traverse(T);break;default:printf("輸入錯誤！！！\n");break;}}return 0; }

更多數據結構與算法實現：數據結構（嚴蔚敏版）與算法的實現（含全部代碼）

有問題請下方評論，轉載請注明出處，并附有原文鏈接，謝謝！如有侵權，請及時聯系。

總結

以上是生活随笔為你收集整理的树-双亲表示法（含全部代码）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。