二叉樹定義
在計(jì)算機(jī)科學(xué)中吕嘀，二叉樹是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實(shí)現(xiàn)二叉查找樹和二叉堆。
一棵深度為k羡洛，且有2^k-1個(gè)結(jié)點(diǎn)的二叉樹，稱為滿二叉樹藕漱。這種樹的特點(diǎn)是每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)欲侮。而在一棵二叉樹中崭闲，除最后一層外，若其余層都是滿的威蕉，并且或者最后一層是滿的刁俭，或者是在右邊缺少連續(xù)若干結(jié)點(diǎn)，則此二叉樹為完全二叉樹韧涨。具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為floor(log2n)+1薄翅。深度為k的完全二叉樹，至少有2k-1個(gè)葉子結(jié)點(diǎn)氓奈，至多有2k-1個(gè)結(jié)點(diǎn)。（轉(zhuǎn)自百度百科）
- 完整的有注釋代碼放一份在我的github
1.二叉樹節(jié)點(diǎn)
- 宏定義數(shù)據(jù)結(jié)構(gòu)入口鼎天。這種定義方式可以很方便地修改數(shù)據(jù)結(jié)構(gòu)
在結(jié)構(gòu)體_bstree_node里舀奶，使用BSTREE_ENTRY定義入口的數(shù)據(jù)結(jié)構(gòu) - 為什么要這樣寫？將業(yè)務(wù)與數(shù)據(jù)結(jié)構(gòu)分離
// 宏定義數(shù)據(jù)結(jié)構(gòu)的入口
#define BSTREE_ENTRY(name, type) \
struct name { \
struct type *left; \
struct type *right; \
}
struct bstree_node {
KEY_VALUE data; // 宏定義數(shù)據(jù)類型斋射，可以是自定義的數(shù)據(jù)結(jié)構(gòu)
BSTREE_ENTRY(, _bstree_node) bst; // 樹節(jié)點(diǎn)定義
};
struct bstree { // 樹定義育勺，包含一個(gè)根節(jié)點(diǎn)
struct bstree_node *root;
};
2.創(chuàng)建一個(gè)節(jié)點(diǎn)
malloc分配內(nèi)存，將參數(shù)key設(shè)為節(jié)點(diǎn)的值罗岖，并將左右子樹置空涧至。
struct bstree_node *bstree_create_node(KEY_VALUE key) {
struct bstree_node *node = (struct bstree_node*)malloc(sizeof(struct bstree_node));
if (node == NULL) {
assert(0);
}
node->data = key;
node->bst.left = node->bst.right = NULL;
return node;
}
3.往樹中插入節(jié)點(diǎn)
先找到插入的父節(jié)點(diǎn)，后再判斷插入到左還是右桑包。
int bstree_insert(struct bstree *T, int key) {
assert(T != NULL);
if (T->root == NULL) {
T->root = bstree_create_node(key); // 創(chuàng)建一個(gè)節(jié)點(diǎn) 以key為值
return 0;
}
struct bstree_node *node = T->root; // 待插入位置的父節(jié)點(diǎn)
struct bstree_node *tmp = T->root; // 待插入位置
while (node != NULL) {
tmp = node;
if (key < node->data) {
node = node->bst.left;
} else {
node = node->bst.right;
}
}
if (key < tmp->data) { // 找到插入左還是右
tmp->bst.left = bstree_create_node(key);
} else {
tmp->bst.right = bstree_create_node(key);
}
return 0;
}
4.中序遍歷
int bstree_traversal(struct bstree_node *node) {
if (node == NULL) return 0;
bstree_traversal(node->bst.left);
printf("%4d ", node->data);
bstree_traversal(node->bst.right);
}
5.完整代碼
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define ARRAY_LENGTH 20
typedef int KEY_VALUE;
#define BSTREE_ENTRY(name, type) \
struct name { \
struct type *left; \
struct type *right; \
}
struct bstree_node {
KEY_VALUE data;
BSTREE_ENTRY(, bstree_node) bst;
};
struct bstree {
struct bstree_node *root;
};
struct bstree_node *bstree_create_node(KEY_VALUE key) {
struct bstree_node *node = (struct bstree_node*)malloc(sizeof(struct bstree_node));
if (node == NULL) {
assert(0);
}
node->data = key;
node->bst.left = node->bst.right = NULL;
return node;
}
int bstree_insert(struct bstree *T, int key) {
assert(T != NULL);
if (T->root == NULL) {
T->root = bstree_create_node(key); // 創(chuàng)建一個(gè)節(jié)點(diǎn) 以key為值
return 0;
}
struct bstree_node *node = T->root; // 待插入位置的父節(jié)點(diǎn)
struct bstree_node *tmp = T->root; // 待插入位置
while (node != NULL) {
tmp = node;
if (key < node->data) {
node = node->bst.left;
} else {
node = node->bst.right;
}
}
if (key < tmp->data) { // 找到插入左還是右
tmp->bst.left = bstree_create_node(key);
} else {
tmp->bst.right = bstree_create_node(key);
}
return 0;
}
int bstree_traversal(struct bstree_node *node) {
if (node == NULL) return 0;
bstree_traversal(node->bst.left);
printf("%4d ", node->data);
bstree_traversal(node->bst.right);
}
int main() {
int keyArray[ARRAY_LENGTH] = {24,25,13,35,23, 26,67,47,38,98, 20,13,17,49,12, 21,9,18,14,15};
struct bstree T = {0};
int i = 0;
for (i = 0;i < ARRAY_LENGTH;i ++) {
bstree_insert(&T, keyArray[i]);
}
bstree_traversal(T.root);
printf("\n");
return 0;
}
2020.5.27 16:21 深圳
