二叉樹的數據結構

typedef char SearchTreeType; typedef struct SearchTreeNode
{ SearchTreeType key; // 關鍵碼 struct SearchTreeNode* lchild; struct SearchTreeNode* rchild; 
} SearchTreeNode; 

二叉樹的初始化

由于我們是用一個指向根節點的指針表示一個二叉樹, 所以初始化的時候就是讓這個指針指向空, 表示一個空樹

void SearchTreeInit(SearchTreeNode** root)
{if(root == NULL){return;//非法輸入}*root = NULL;
}

二叉樹的查找

將要查找的元素的值和根節點的值進行比較, 如果相等直接返回, 如果不相等, 就將要查找的元素的值和根節點的值比較, 如果根節點小于要查找的值, 就在左子樹中去查找, 如果大于根節點的值, 就在右子樹上查找

SearchTreeNode* SearchTreeFind(SearchTreeNode* root, SearchTreeType to_find)
{if(root == NULL){return NULL;}if(root -> key == to_find){return root;}else if(root -> key < to_find){return SearchTreeFind(root -> rchild, to_find);}return SearchTreeFind(root -> lchild, to_find);
}

二叉樹的插入

插入分為兩種情況, 當數為空的時候就直接創建一個結點然后將其直接插入. 當二叉樹不為空的時候, 此時就定義一個 parent 指針指向根節點, 然后判斷 parent 指針指向的結點的值和要插入值的值 key 比較. 如果 parent 指針指向的結點的值小于 key, 就遞歸地在左子樹中插入, 如果大于就遞歸在右子樹上插入.

void SearchTreeInsert(SearchTreeNode** root, SearchTreeType key)
{if(root == NULL){return;}SearchTreeNode* new_node = Creat(key);if(*root == NULL){*root = new_node;return;}SearchTreeNode* parent = *root;if(parent -> key < key){SearchTreeInsert(&parent -> rchild, key);}else{SearchTreeInsert(&parent -> lchild, key);}
}