程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> C 數據結構:樹 功能:基本操作

C 數據結構:樹 功能:基本操作

編輯:關於C語言

樹的定義便是遞歸定義,所以絕大多功能采用遞歸完成


001 #include <stdio.h> 

002 #include <malloc.h> 

003 #include <stdlib.h> 

004 #define MAX 100 

005 #define ERROR 0 

006 #define OK 1 

007 #ifndef Type 

008 typedef char Type; 

009 #endif 

010   

011 typedef struct Bitree 

012 { 

013     Type data; 

014     struct Bitree *lchild; 

015     struct Bitree *rchild; 

016 }BitNode, *BiTree; 

017   

018 int InitBiTree(BiTree *T)//初始化空樹 

019 { 

020     *T = NULL; 

021     return OK; 

022 }<SPAN style="COLOR: #e53333" minmax_bound="true">//假如傳入的參數是指向BitNode的指針,也就是BiTree  由於對於樹的構建是使用遞歸的方式,所以在對子樹 

023 //因為子樹的類型也為BiTree 所以此時無法改變其實(傳值,形參),所以參數要使用指向Bitree的指針</SPAN> /* 

024 int Creat(BiTree T) 

025 { 

026     Type p; 

027   

028     scanf("%c", &p); 

029       

030     if (p == ' ') 

031         T = NULL; 

032     else 

033     { 

034         T->data = p; 

035         T->lchild = (BiTree)malloc(sizeof(BitNode)); 

036         Creat(T->lchild); 

037         T->rchild = (BiTree)malloc(sizeof(BitNode)); 

038         Creat(T->rchild); 

039     } 

040     return OK; 

041 } 

042 */ 

043   

044 int CreatBiTree(BiTree *T)//用遞歸的方式創建樹(前序輸入,空格表示子樹為空) 

045 { 

046     Type p; 

047   

048     scanf("%c", &p); 

049   

050     if (p == ' ') 

051     *T = NULL; 

052     else 

053     { 

054     *T = (BiTree)malloc(sizeof(BitNode)); 

055     (*T)->data = p; 

056     CreatBiTree(&(*T)->lchild); 

057     CreatBiTree(&(*T)->rchild); 

058     } 

059     return OK; 

060 } 

061   

062 int ClearBiTree(BiTree *T)//清除樹,同樣為遞歸的方式 

063 { 

064     if ((*T)->lchild) 

065         ClearBiTree(&((*T)->lchild)); 

066     if ((*T)->rchild)     

067         ClearBiTree(&((*T)->rchild)); 

068       

069     if ((*T)->lchild == NULL && (*T)->rchild == NULL) 

070     { 

071         free(*T); 

072         *T = NULL; 

073     } 

074     return OK; 

075 } 

076   

077 int BiTreeEmpty(BiTree T)//判斷樹是否為空 

078 { 

079     if (T == NULL) 

080     return OK; 

081     return ERROR; 

082 } 

083   

084 int BiTreeDepth(BiTree T)//樹的深度 

085 { 

086     int hl, hr; 

087     if (T == NULL) 

088     return 0; 

089     else 

090     { 

091     hl = BiTreeDepth(T->lchild); 

092     hr = BiTreeDepth(T->rchild); 

093     if (hl > hr) 

094         return hl + 1; 

095     else 

096         return hr + 1; 

097     } 

098 } 

099   

100 BitNode Root(BiTree T)//返回樹的根(節點) 

101 { 

102     if (T == NULL) 

103     { 

104         printf("No Root"); 

105         exit(0); 

106     } 

107     return *T; 

108 } 

109   

110 int InserInc(BiTree *T, Type e)//按照字母序插入節點 (小於該節點的為其左子樹,大於該節點的為其右子樹) 

111 { 

112     BiTree temp; 

113       

114     temp = (BiTree)malloc(sizeof(BitNode)); 

115     temp->data = e; 

116       

117     if (*T == NULL) 

118     { 

119     temp->lchild = NULL; 

120     temp->rchild = NULL; 

121     *T = temp; 

122     } 

123     else 

124     { 

125     if (e < (*T)->data) 

126         InserInc(&((*T)->lchild), e); 

127     else 

128         InserInc(&((*T)->rchild), e); 

129     } 

130     return OK; 

131 } 

132   

133   

134 BiTree Search(BiTree T, Type p)//返回值為p的節點,否則為空 

135 { 

136     BiTree temp; 

137     if (T == NULL) 

138     return ERROR; 

139     else 

140     { 

141     if (T->data == p) 

142         return T; 

143     else 

144     { 

145         temp = Search(T->lchild, p); 

146         if (temp == NULL) 

147         temp = Search(T->rchild, p); 

148     } 

149     } 

150     return temp; 

151 } 

152   

153 int DeleteChild(BiTree *T, BiTree p, int flag)//刪除值為p的節點的子樹,flag=1刪除右子樹,flag=0刪除左子樹 

154 { 

155     BiTree tar; 

156   

157     tar = Search(*T, p->data); 

158     if (tar == NULL) 

159         return ERROR; 

160     if (flag == 0) 

161     { 

162         ClearBiTree(&(tar->lchild)); 

163         tar->lchild = NULL;      

164     } 

165     else 

166     { 

167         ClearBiTree(&(tar->rchild)); 

168         tar->rchild = NULL;      

169     } 

170     return OK; 

171 } 

172   

173   

174 BiTree Parent(BiTree T, Type e)//返回值為e的節點的父母 

175 { 

176     BiTree cur; 

177       

178     if (T == NULL) 

179     return NULL; 

180     else 

181     { 

182     if ((T->lchild)->data == e || (T->rchild)->data == e) 

183         cur = T; 

184     else 

185     { 

186         cur = Parent(T->lchild, e); 

187         if (cur == NULL) 

188         cur = Parent(T->rchild, e); 

189     } 

190     } 

191     return cur; 

192 } 

193   

194 BiTree LeftChild(BiTree T, Type e)//返回左孩子 

195 { 

196     BiTree result; 

197   

198     if (T == NULL) 

199     return NULL; 

200     else 

201     { 

202     if (T->data == e) 

203         return T->lchild; 

204     else 

205     { 

206         result = LeftChild(T->lchild, e); 

207         if (result == NULL) 

208         result = LeftChild(T->rchild, e); 

209     } 

210     } 

211     return result; 

212 } 

213   

214 BiTree LeftSibling(BiTree T, Type e)//返回左兄弟 

215 { 

216     BiTree result; 

217   

218     if (T->lchild == NULL || T->rchild == NULL) 

219     return NULL; 

220     else 

221     { 

222     if (T->lchild->data == e && T->rchild) 

223         return T->rchild; 

224     else 

225     { 

226         result = LeftSibling(T->lchild, e); 

227         if (result == NULL) 

228         result = LeftSibling(T->rchild, e); 

229     } 

230     } 

231     return result; 

232 } 

233   

234 int main() 

235 { 

236     BiTree T; 

237     BitNode root; 

238     BiTree temp; 

239     int depth; 

240       

241     CreatBiTree(&T); 

242     //ClearBiTree(&T); 

243     //depth = BiTreeDepth(T); 

244     //root = Root(T); 

245     //InserInc(&T, 'd'); 

246     //temp = Search(T, 'a'); 

247     //Delete(&T, 'd'); 

248     //DeleteChild(&T, temp, 1); 

249     //temp = Parent(T, 'c'); 

250     temp = LeftSibling(T, 'a'); 

251     return 0; 

252 }


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved