树
专业术语 中 文 描 述
Root 根节点 一棵树的顶点
Child 孩子节点 一个结点含有的子树的根结点称为该结点的子结点
Leaf 叶子节点 没有孩子的节点
Degree 度 一个节点包含的子树的数量
Edge 边 一个节点与另外一个节点的连接
Depth 深度 根节点到这个节点经过的边的数量
Height 节点高度 从当前节点到叶子节点形成路径中边的数量
Level 层级 节点到根节点最长路径的边的总和
Path 路径 一个节点和另一个节点之间经过的边和 Node 的序列二叉树常见性质
(1) 在非空二叉树中，第 i-1 层的结点总数不超过2^(i-1) , i>=1；
(2) 深度为 h-1 的二叉树最多有 2^h - 1个结点(h>=1)，最少有 h 个结点；
(3) 对于任意一棵二叉树，如果其叶结点数为 N0，而度数为 2 的结点总数为 N2，则 N0=N2+1；常见二叉树分类：
（1）完全二叉树 — 若设二叉树的高度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层有叶
子节点，并且叶子结点都是从左到右依次排布，这就是完全二叉树（堆就是完全二叉树）
（2）满二叉树 — 除了叶结点外每一个结点都有左右子节点且叶子结点都处在最底层的二叉树
（3）平衡二叉树 — 又被称为 AVL 树，它是一颗空树或左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都
是一棵平衡二叉树。
（4）二叉搜索树
又称二叉查找树、二叉排序树（Binary Sort Tree）。它是一颗空树或是满足下列性质的二叉树：
1）若左子树不空，则左子树上所有节点的值均小于或等于它的根节点的值；
2）若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；
3）左、右子树也分别为二叉排序树。
（5）红黑树
是每个节点都带有颜色属性（颜色为红色或 01111
黑
色）的自平衡二叉查找树，满足下列性质：
1）节点是红色或黑色；
2）根节点是黑色；
3）所有叶子节点都是黑色；
4）每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节
点。)
5）从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
二叉搜索树
base_tree.h
#ifndef BIT_TREE_MINE_BASE_TREE_H
#define BIT_TREE_MINE_BASE_TREE_H
#define IsLess(a, b) (a<b)
#define IsEqual(a, b) (a==b)
typedef struct BNode {
int data;
struct BNode *lchild, *rchild;
} Bitree;
#endif //BIT_TREE_MINE_BASE_TREE_H
main.c
#include "cstdio"
#include "cstdlib"
#include "base_tree.h"
bool InsertTree(Bitree **root, Bitree *node) {
Bitree *temp;
Bitree *parent;
if (!node) {
return false;
} else {
//清空新节点的左右子树
node->lchild = NULL;
node->rchild = NULL;
}
if (*root) {
//存在根节点
temp = *root;
} else {
//不存在根节点
*root = node;
return true;
}
while (temp != NULL) {
//保存父节点
parent = temp;
if (IsLess(node->data, temp->data)) {
temp = temp->lchild;
} else {
temp = temp->rchild;
}
}
//若该树为空树,则直接将 node 放置在根节点上
if (IsLess(node->data, parent->data)) {
//找到空位置后，进行插入
parent->lchild = node;
} else {
parent->rchild = node;
}
return true;
}
/************************
* 采用递归方式实现前序遍历
*************************/
void PreOrderTree(Bitree *root) {
if (root == NULL) {
return;
}
printf("%d, ", root->data);
PreOrderTree(root->lchild);
PreOrderTree(root->rchild);
}
/************************
* 采用二叉搜索树上最大的结点
*************************/
int findMax(Bitree *root) {
if (root->rchild == NULL) {
return root->data;
}
return findMax(root->rchild);
}
/************************
* 采用递归方式查找结点
*************************/
Bitree *DeleteNodeTree(Bitree *root, int value, Bitree *&deletenode) {
if (root == NULL)return NULL;
if (root->data > value) {
root->lchild = DeleteNodeTree(root->lchild, value, deletenode);
return root;
}
if (root->data < value) {
root->rchild = DeleteNodeTree(root->rchild, value, deletenode);
return root;
}
deletenode = root;
//删除节点不存在左右子节点，即为叶子节点，直接删除
if (root->lchild == NULL && root->rchild == NULL)return NULL;
//删除节点存在左子节点，直接用左子节点取代删除节点
if (root->lchild != NULL && root->rchild == NULL) return root->lchild;
//删除节点存在右子节点，直接用右子节点取代删除节点
if (root->lchild == NULL && root->rchild != NULL) return root->rchild;
//删除节点存在左右子节点，直接用左子节点最大值取代删除节点
int num = findMax(root->lchild);
root->data = num;
root->lchild = DeleteNodeTree(root->lchild, num, deletenode);
return root;
}
/************************
* 采用递归方式查找结点
*************************/
Bitree *QueryByRec(Bitree *root, int e) {
if (IsEqual(root->data, e) || root == NULL) {
return root;
} else if (IsLess(e, root->data)) {
return QueryByRec(root->lchild, e);
} else {
return QueryByRec(root->rchild, e);
}
}
/**
* 使用非递归方式查找结点
*/
Bitree *QueryByLoop(Bitree *root, int e) {
while (NULL != root && !IsEqual(root->data, e)) {
if (IsLess(e, root->data)) {
root = root->lchild;
} else {
root = root->rchild;
}
}
return root;
}
int main() {
int arr[] = {17, 12, 19, 10, 15, 18, 25, 8, 11, 13, 16, 22};
int length = sizeof(arr) / sizeof(arr[0]);
Bitree *root = NULL, *node = NULL;
node = new Bitree;
node->data = arr[0];
//插入根节点
InsertTree(&root, node);
for (int i = 1; i < length; i++) {
node = new Bitree;
node->data = arr[i];
if (InsertTree(&root, node)) {
printf("%d插入成功!\n", arr[i]);
}
}
printf("开始前序遍历:\n");
PreOrderTree(root);
printf("\n开始进行删除操作\n");
Bitree *deletenode = NULL;
//二叉搜索树删除
root = DeleteNodeTree(root, 15, deletenode);
printf("二叉搜索树删除节点 15, %s\n", deletenode ? "删除成功" : "删除不成功，节点不存在");
if (deletenode) delete deletenode;
printf("删除以后的前序遍历结果:\n");
PreOrderTree(root);
printf("\n通过二叉树查找节点\n");
int value1 = 18;
//二叉搜索树查找节点
Bitree *node1 = QueryByLoop(root, value1);
printf("节点%d : %s\n", value1, node1 ? "YES" : "NO");
int value2 = 187;
Bitree *node2 = QueryByLoop(root, value2);
printf("节点%d: %s\n", value2, node2 ? "YES" : "NO");
return 0;
}
