1.樹節點的典型聲明

typedef struct TreeNode *PtrToNode;struct TreeNode{ElementType Element;PtrToNode FirstChild;PtrToNode NextSibling; /* 指向下一個兄弟 */}

2.而叉查找樹的實現

?

#include <stdio.h> #include <stdlib.h>struct TreeNode; typedef struct TreeNode *SearchTree; typedef struct TreeNode *Position;struct TreeNode {int Element;SearchTree Left;SearchTree Right; };/* 清空＆初始化樹 */ SearchTree MakeEmpty(SearchTree T) {if (T != NULL){ MakeEmpty(T->Left);MakeEmpty(T->Right);free(T);} return NULL; }/* 在樹中查找x */ Position Find(int x, SearchTree T) {if (T == NULL)return NULL;if (x < T->Element)return Find(x, T->Left);else if (x > T->Element)return Find(x, T->Right);elsereturn T; }/* 遞歸實現 */ Position FindMin(SearchTree T) {if (T == NULL)return NULL;else if (T->Left == NULL)return T;elsereturn FindMin(T->Left); }/* 非遞歸實現 */ Position FindMax(SearchTree T) {if (T != NULL)while (T->Right != NULL)T = T->Right;return T; }/* 將元素插入樹 */ SearchTree Insert(int x, SearchTree T) {if (T == NULL){T = malloc(sizeof(struct TreeNode));if (T == NULL)printf("Out of space!\n");else{T->Element = x;T->Left = T->Right = NULL;}}else if (x < T->Element)T->Left = Insert(x, T->Left);else if (x > T->Element)T->Right = Insert(x, T->Right);return T; }/* 在樹中查找x,并刪除 */ SearchTree Delete(int x, SearchTree T) {Position TmpCell;if (T == NULL)printf("Element not found!\n");else if (x < T->Element)T->Left = Delete(x, T->Left);else if (x < T->Element)T->Right = Delete(x, T->Right);else if (T->Left && T->Right){TmpCell = FindMin(T->Right);T->Element = TmpCell->Element;T->Right = Delete(T->Element, T->Right);}else{TmpCell = T;if (T->Left == NULL)T = T->Right;else if (T->Right == NULL)T = T->Left;free(TmpCell);}return T; }int main() {SearchTree tree = NULL;MakeEmpty(tree);/* 注意Insert返回值為樹 */tree = Insert(3, tree);tree = Insert(1, tree);tree = Insert(2, tree);tree = Insert(4, tree);Position p;p = FindMin(tree);printf("Min = %d\n", p->Element);p = FindMax(tree);printf("Max = %d\n", p->Element);p = Find(1, tree);if (p != NULL){printf("Find %d success!\n", p->Element);}else{printf("Do not find in tree!\n");}tree = Delete(1, tree);p = FindMin(tree);printf("Min = %d\n", p->Element);return 0; }

?

?

轉載于:https://www.cnblogs.com/james1207/p/3268575.html

總結

以上是生活随笔為你收集整理的树和而叉查找树的实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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