一、二叉樹回憶
上一篇我們對資料結構中常用的樹做了介紹，本篇部落客要以二叉樹為例，講解一下樹的資料結構和代碼實作。回顧二叉樹：二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）
二、二叉樹比連結清單好在哪裡？
看看如下的資料：使用連結清單形式存放
我們要向查找資料6，需要從頭開始查找，找到最後一個，查找比較麻煩。再來看看使用二叉樹的形式存儲
顯然，我們很清楚自己要查找的目标大緻會在那裡出現；
例如查找的目标是6，那麼我知道6小于9是以根本不會去看右邊的資料；
我們繼續看6大于5是以找到啦目标；
換句話說我們隻對比了兩次找到啦目标；
而對于連結清單，我們發現6排在了連結清單的尾部；到此為止我們知道這樣的二叉樹的确是高效的；
三、二叉樹的節點定義（C語言版）
typedef struct N
{
int data;
struct N *left_node;
struct N *right_node;
}Node; 四、定義一個二叉樹（C語言版）
typedef struct tree
{
struct node *root;
}Tree; 我們的樹定義得更加簡單，注意我們是先定義節點，再定義樹；
因為樹的定義需要用到節點結構體；
接下來我們需要初始化我們的樹
五、初始化樹（C語言版）
Tree * init_tree()
{
Tree *tree = (Tree *)malloc(sizeof(Tree));
if (tree)
{
tree->root = NULL;
}
return tree;
} 六、建立節點（C語言版）
Node *make_node(int data)
{
Node *node = (Node *)malloc(sizeof(Node));
node->left_node = NULL;
node->right_node = NULL;
node->data = data;
return node;
} 七、插入節點（C語言版）
// 插入節點
Node* insert_node(Tree *tree,int data)
{
// 判斷根節點是否存在
if (tree->root == NULL)
{
// 不存在就建立
tree->root = make_node(data);
}
else
{
Node *current = tree->root;
// 一直循環知道找到準确的插入資料的位置
while (1)
{
// 我們的二叉樹不允許重複數字插入,相等直接退出
if (current->data == data)
{
return tree->root;
}
// 如果要插入的資料比根節點大，就放在右邊的子樹中
else if(current->data<data)
{
if (current->right_node == NULL)
{
// 建立右節點
current->right_node = make_node(data);
break;
}
current = current->right_node;
}
else
{
// 如果要插入的資料比根節點小，就放在左邊的子樹中
if (current->left_node == NULL)
{
// 建立左節點
current->left_node = make_node(data);
break;
}
current = current->left_node;
}
}
}
return tree->root;
} 八、樹的周遊（C語言版）
void print_inorder(Node *root)
{
if (root)
{
print_inorder(root->left_node);
printf("data:%d\n",root->data);
print_inorder(root->right_node);
}
} 九、樹的删除（C語言版）
樹的删除比較麻煩，整體分為二種情況：
一、要删除的節點左右都有子節點
二、要删除的節點隻有一個或者0個節點（即有左節點或者右節點或者一個都沒有）
其中第一種情況又分幾種小情況。例如：我們要删除節點6
1.1 我們現在要删除的是節點6，這時候6節點下面的右節點隻有一個7，并且7下面沒有節點，有一個也一樣的，隻需要将其右邊的節點7替代他的位置即可。
1.2 我們現在要删除的是節點6，現在7下面5和8兩個節點，如果還是按照上面的思路删除的話，删除之後7下面就有1，5，8三個節點，明顯不對
正确的做法應該是找到要删除的節點6的右節點7，這時候在找到7的做節點5，去繼承删除節點6的位置
1.3、以要删除節點6的右節點7為樹的左邊分支的最小子節點是左節點的情況（很繞口）
1.4、以要删除節點6的右節點7為樹的左邊分支的最小子節點是右節點的情況（很繞口）
樹删除代碼的實作
int remove_node(Tree *tree,int data)
{
if (tree->root != NULL)
{
Node *p = NULL;
Node *s ;
Node *current = tree->root;
while (1)
{
// 根節點都沒有直接傳回
if (current == NULL)
{
return 0;
}
// 要删除的節點就是跟節點
else if(current->data == data)
{
break;
}
// 要删除的節點在根節點的右邊
else if(current->data<data)
{
p = current;
current = current->right_node;
}
// 要删除的節點在根節點的左邊
else
{
p=current;
current = current->left_node;
}
}
/**********************上面的代碼片段是找到要删除的節點**************************/
if (current->left_node != NULL && current->right_node != NULL)
{
p = current;
// 找到要删除節點的右節點
s = current->right_node;
while (s->left_node != NULL)
{
// p = s當current要深入到下一個分叉時，給自己留一個後路；是以儲存了自己的前一個備份；
p = s;
// 沿着左邊一直找到最小的節點
s = s->left_node;
}
current->data = s->data;
// 最小值在分支的右邊
if ( p->right_node == s)
{
p->right_node = s->right_node;
}
free(s);
}
/***************上面的代碼片段是根據要删除節點左右都有子節點的情況**************/
else
{
// 左子節點為空，隻有右子節點
if (current->left_node == NULL)
{
// 而且要删除的節點是跟節點
if (p==NULL)
{
// 直接将跟節點的右節點設定為跟節點
tree->root = current->right_node;
}
else
{
if (p->right_node == current)
{
p->right_node = current->right_node;
}
else
{
p->left_node = current->right_node;
}
}
}
// 右子節點為空，隻有左子節點
else
{
// 而且要删除的節點是跟節點
if (p == NULL)
{
tree->root = current->left_node;
}
else
{
if (p->right_node == current)
{
p->right_node = current->left_node;
}
else
{
p->left_node = current->left_node;
}
}
}
}
/***************上面的代碼片段是根據要删除節點左右隻有一個或者沒有子節點的情況**********/
}
return 1;
} 十、樹的查找（C語言版）
int find_node(Node *root,int data)
{
if (root == NULL)
{
return 0;
}
else if(root->data == data)
{
return 1;
}
else
{
if (root->data <data)
{
return find_node(root->right_node, data);
}
else
{
return find_node(root->left_node, data);
}
}
} 十一、樹的前序周遊（C語言版）
void preOrder(Node *root)
{
if (root != NULL)
{
printf("%d ",root->data);
preOrder(root->left_node);
preOrder(root->right_node);
}
} 十二、樹的中序周遊（C語言版）
void inOrder(Node *root)
{
if (root != NULL)
{
inOrder(root->left_node);
printf("%d ",root->data);
inOrder(root->right_node);
}
} 十三、樹的後序周遊(C語言版)
void postOreder(Node *root)
{
if (root != NULL)
{
postOreder(root->left_node);
postOreder(root->right_node);
printf("%d ",root->data);
}
} 十四、樹的廣度周遊（C語言版）
void level_order(Tree *tree)
{
Node *node = tree->root;
Node *queue[10];
int current = 0;
int after_current = 0;
if (node == NULL)
{
return;
}
queue[current++] = node;
while (current!=after_current)
{
node = queue[after_current++];
printf("%d ",node->data);
if (node->left_node != NULL)
{
queue[current++] = node->left_node;
}
if (node->right_node != NULL)
{
queue[current++] = node->right_node;
}
}
} 十五、樹的python代碼實作
由于C語言版寫的很詳細了，python就簡單的實作排序，思路完全一樣。
# coding:utf-8
class Node(object):
""""""
def __init__(self, item):
self.elem = item
self.lchild = None
self.rchild = None
class Tree(object):
"""二叉樹"""
def __init__(self):
self.root = None
def add(self, item):
node = Node(item)
if self.root is None:
self.root = node
return
queue = [self.root]
while queue:
cur_node = queue.pop(0)
if cur_node.lchild is None:
cur_node.lchild = node
return
else:
queue.append(cur_node.lchild)
if cur_node.rchild is None:
cur_node.rchild = node
return
else:
queue.append(cur_node.rchild)
def breadth_travel(self):
"""廣度周遊"""
if self.root is None:
return
queue = [self.root]
while queue:
cur_node = queue.pop(0)
print(cur_node.elem, end=" ")
if cur_node.lchild is not None:
queue.append(cur_node.lchild)
if cur_node.rchild is not None:
queue.append(cur_node.rchild)
def preorder(self, node):
"""先序周遊"""
if node is None:
return
print(node.elem, end=" ")
self.preorder(node.lchild)
self.preorder(node.rchild)
def inorder(self, node):
"""中序周遊"""
if node is None:
return
self.inorder(node.lchild)
print(node.elem, end=" ")
self.inorder(node.rchild)
def postorder(self, node):
"""後序周遊"""
if node is None:
return
self.postorder(node.lchild)
self.postorder(node.rchild)
print(node.elem, end=" ")
if __name__ == "__main__":
tree = Tree()
tree.add(5)
tree.add(2)
tree.add(3)
tree.add(7)
tree.add(4)
tree.add(8)
tree.add(6)
tree.preorder(tree.root)
print(" ")
tree.inorder(tree.root)
print(" ")
tree.postorder(tree.root)
print(" ")
tree.breadth_travel() 運作結果為：
5 2 7 4 3 8 6
7 2 4 5 8 3 6
7 4 2 8 6 3 5
5 2 3 7 4 8 6 寫到此處以吐血，你看到次數也吐血了吧。
侯哥語錄：我曾經是一個職業教育者，現在是一個自由開發者。我希望我的分享可以和更多人一起進步。分享一段我喜歡的話給大家："我所了解的自由不是想幹什麼就幹什麼，而是想不幹什麼就不幹什麼。當你還沒有能力說不得時候，就努力讓自己變得強大，擁有說不得權利。"