樹（二元樹）
樹表示由邊緣連線的節點。我們將要具體地討論二元樹或二元搜尋樹。
二元樹是用於資料儲存目的的特殊的資料結構。二元樹有一個特殊的情況，每個節點可以有兩個子節點。二元樹有序陣列和連結串列的兩個好處，搜尋排序在陣列插入或刪除操作一樣快的，在連結串列也是盡可能快。
術語
以下是關於樹的重要方面。
-
路徑 ? 路徑是指沿一棵樹的邊緣節點的序列。
-
根 ? 節點在樹的頂部被稱為根。有每棵樹只有一個根和一個路徑從根節點到任何節點。
-
父子點 ? 除根節點的任何一個節點都有一個邊緣向上的節點稱為父節點。
-
子節點 ? 給定節點的邊緣部分連線向下以下節點被稱為它的子節點。
-
葉子點 ? 節點不具有任何子節點被稱為葉節點。
-
子樹 ? 子樹代表一個節點的後代。
-
存取 ? 存取是指檢查某個節點的值在控制的節點上時。
-
遍歷 ? 遍歷意味著通過節點傳遞一個特定的順序。
-
層次 ? 一個節點的層次表示的節點的產生。如果根節點的級別是0，那麼它的下一子結點為1級，其孫子是2級等。
-
鍵 ? 鍵表示基於一個節點在其上的搜尋操作將被進行了一個節點的值。
二元搜尋樹表現出特殊的行為。一個節點的左子的值必須低於其父的值，節點的右子節點的值必須大於它的父節點的值。
二元搜尋樹表示
我們將使用節點物件來實現樹，並通過參照連線它們。
基本操作
以下是遵循樹的基本操作。
-
搜尋 ? 搜尋一棵樹中的元素
-
插入 ? 插入元素到一棵樹中
-
前序遍歷 ? 遍歷樹前序方法
-
中序遍歷 ? 遍歷樹在序方法
-
後序遍歷? 遍歷樹的後序方法
節點
限定了具有一些資料，參照其左，右子節點的節點。
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
搜尋操作
每當一個元素被搜尋。開始從根節點搜尋後，如果資料小於鍵值，在左子樹中搜尋元素，否則在右子樹搜尋元素。每一個節點按照同樣的演算法。
struct node* search(int data){
struct node *current = root;
printf("Visiting elements: ");
while(current->data != data){
if(current != NULL)
printf("%d ",current->data);
//go to left tree
if(current->data > data){
current = current->leftChild;
}//else go to right tree
else{
current = current->rightChild;
}
//not found
if(current == NULL){
return NULL;
}
return current;
}
}
插入操作
每當一個元素被插入。首先找到它應有的位置。從根節點開始搜尋，那麼如果資料小於鍵值，在搜尋左子樹空位置並插入資料。否則，在右子樹搜尋空位置並插入資料。
void insert(int data){
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//if tree is empty
if(root == NULL){
root = tempNode;
}else{
current = root;
parent = NULL;
while(1){
parent = current;
//go to left of the tree
if(data < parent->data){
current = current->leftChild;
//insert to the left
if(current == NULL){
parent->leftChild = tempNode;
return;
}
}//go to right of the tree
else{
current = current->rightChild;
//insert to the right
if(current == NULL){
parent->rightChild = tempNode;
return;
}
}
}
}
}
前序遍歷
這是一個簡單的三個步驟。
- 存取根結點
- 遍歷左子樹
- 遍歷右子樹
void preOrder(struct node* root){
if(root != NULL){
printf("%d ",root->data);
preOrder(root->leftChild);
preOrder(root->rightChild);
}
}
中序遍歷
這是一個簡單的三個步驟。
- 遍歷左子樹
- 存取根結點
- 遍歷右子樹
void inOrder(struct node* root){
if(root != NULL){
inOrder(root->leftChild);
printf("%d ",root->data);
inOrder(root->rightChild);
}
}
後序遍歷
這是一個簡單的三個步驟。
- 遍歷左子樹
- 遍歷右子樹
- 存取根結點
void postOrder(struct node* root){
if(root != NULL){
postOrder(root->leftChild);
postOrder(root->rightChild);
printf("%d ",root->data);
}
}
演示程式
TreeDemo.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
struct node *root = NULL;
void insert(int data){
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//if tree is empty
if(root == NULL){
root = tempNode;
}else{
current = root;
parent = NULL;
while(1){
parent = current;
//go to left of the tree
if(data < parent->data){
current = current->leftChild;
//insert to the left
if(current == NULL){
parent->leftChild = tempNode;
return;
}
}//go to right of the tree
else{
current = current->rightChild;
//insert to the right
if(current == NULL){
parent->rightChild = tempNode;
return;
}
}
}
}
}
struct node* search(int data){
struct node *current = root;
printf("Visiting elements: ");
while(current->data != data){
if(current != NULL)
printf("%d ",current->data);
//go to left tree
if(current->data > data){
current = current->leftChild;
}//else go to right tree
else{
current = current->rightChild;
}
//not found
if(current == NULL){
return NULL;
}
}
return current;
}
void preOrder(struct node* root){
if(root != NULL){
printf("%d ",root->data);
preOrder(root->leftChild);
preOrder(root->rightChild);
}
}
void inOrder(struct node* root){
if(root != NULL){
inOrder(root->leftChild);
printf("%d ",root->data);
inOrder(root->rightChild);
}
}
void postOrder(struct node* root){
if(root != NULL){
postOrder(root->leftChild);
postOrder(root->rightChild);
printf("%d ",root->data);
}
}
void traverse(int traversalType){
switch(traversalType){
case 1:
printf("\nPreorder traversal: ");
preOrder(root);
break;
case 2:
printf("\nInorder traversal: ");
inOrder(root);
break;
case 3:
printf("\nPostorder traversal: ");
postOrder(root);
break;
}
}
int main() {
/* 11 //Level 0
*/
insert(11);
/* 11 //Level 0
* |
* |---20 //Level 1
*/
insert(20);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
*/
insert(3);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
* |
* |--42 //Level 2
*/
insert(42);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
* |
* |--42 //Level 2
* |
* |--54 //Level 3
*/
insert(54);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
* |
* 16--|--42 //Level 2
* |
* |--54 //Level 3
*/
insert(16);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
* |
* 16--|--42 //Level 2
* |
* 32--|--54 //Level 3
*/
insert(32);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
* | |
* |--9 16--|--42 //Level 2
* |
* 32--|--54 //Level 3
*/
insert(9);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
* | |
* |--9 16--|--42 //Level 2
* | |
* 4--| 32--|--54 //Level 3
*/
insert(4);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
* | |
* |--9 16--|--42 //Level 2
* | |
* 4--|--10 32--|--54 //Level 3
*/
insert(10);
struct node * temp = search(32);
if(temp != NULL){
printf("Element found.\n");
printf("( %d )",temp->data);
printf("\n");
}else{
printf("Element not found.\n");
}
struct node *node1 = search(2);
if(node1 != NULL){
printf("Element found.\n");
printf("( %d )",node1->data);
printf("\n");
}else{
printf("Element not found.\n");
}
//pre-order traversal
//root, left ,right
traverse(1);
//in-order traversal
//left, root ,right
traverse(2);
//post order traversal
//left, right, root
traverse(3);
}
如果我們編譯並執行上述程式，那麼這將產生以下結果 -
Visiting elements: 11 20 42 Element found.(32) Visiting elements: 11 3 Element not found. Preorder traversal: 11 3 9 4 10 20 16 42 32 54 Inorder traversal: 3 4 9 10 11 16 20 32 42 54 Postorder traversal: 4 10 9 3 16 32 54 42 20 11