数据结构与算法p4
树形结构
基础概念
定义 树（Tree）是n（n≥0）个节点的有限集合T，它满足两个条件：有且仅有一个特定的称为根（Root）的节点；其余的节点可以分为m（m≥0）个互不相交的有限集合T1、T2、……、Tm，其中每一个集合又是一棵树，并称为其根的子树（Subtree）。
基本概念
节点
- 度 一个节点的子树的个数称为该节点的度数，一棵树的度数是指该树中节点的最大度数。
- 度数为零的节点称为树叶或终端节点，度数不为零的节点称为分支节点，除根节点外的分支节点称为内部节点。
- 一个节点的子树之根节点称为该节点的子节点，该节点称为它们的父节点，同一节点的各个子节点之间称为兄弟节点。一棵树的根节点没有父节点，叶节点没有子节点。
- 一个节点系列k1,k2, ……,ki,ki+1, ……,kj,并满足ki是ki+1的父节点，就称为一条从k1到kj的路径，路径的长度为j-1,即路径中的边数。路径中前面的节点是后面节点的祖先，后面节点是前面节点的子孙。
- 节点的层数等于父节点的层数加一，根节点的层数定义为一。树中节点层数的最大值称为该树的高度或深度。
- m（m≥0）棵互不相交的树的集合称为森林。树去掉根节点就成为森林，森林加上一个新的根节点就成为树。
最大度为 3 的树的节点的定义。
struct tree_node {int data;struct tree_node * children[3];int children_count;
}
二叉树
定义
度为2的树称为二叉树。
二叉树（Binary Tree）是n（n≥0）个节点的有限集合，它或者是空集（n＝0），或者是由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。二叉树与普通有序树不同，二叉树严格区分左孩子和右孩子，即使只有一个子节点也要区分左右。
二叉树的特征
- 二叉树第i（i≥1）层上的节点最多为$2^{i-1} 个。
满二叉树 ：
完全二叉树 ：
二叉树的遍历
遍历 ：沿某条搜索路径周游二叉树，对树中的每一个节点访问一次且仅访问一次。
基本遍历:
- 先序遍历： 先访问树根，再访问左子树，最后访问右子树；
- 中序遍历： 先访问左子树，再访问树根，最后访问右子树；
- 后序遍历： 先访问左子树，再访问右子树，最后访问树根；
- 层次遍历: 从根节点开始，逐层从左向右进行遍历。
二叉树的存储结构
1、 二叉树顺序存储
2、 二叉树链式存储节点的定义
binary tree node->bnode
struct bnode {int data;struct bnode * left;struct bnode * right;
};
当 left 和 right 指向空NULL, 时表示此节点没有子树。
二叉树每个节点中除了存储数据的元素本身外，还需要两个变量来记录当前节点的左子树和右子树。
二叉排序树（二叉查找树）- Binary Search Tree
二叉排序树的定义
- 左子树的所有节点的数值都小于 根节点的值。
- 右子树的所有节点的数值都大于等于根节点的值。
特点：
1、如果是一个满二叉排序树（二叉查找树），他的查找的时间复杂度是
O(log2n)O(log_2^n)O(log2n)
二叉排序树插入和删除时不需要移动节点数据，速度快。
二叉排序树的基本操作：
- 二叉树初始化
- 插入数据
- 查找数据。
- 先序遍历
- 中序遍历
- 后序遍历
- 删除数据
- 二叉树销毁
框架代码
// 二叉排序树
#include <stdio.h>
#include <stdlib.h>// 二叉树的节点结构
struct bnode {int data;struct bnode * left;struct bnode * right;
};// 用于定义一棵二叉树
struct bin_tree {struct bnode * root;
};
// 1. 二叉树初始化
void tree_init(struct bin_tree * atree) {}
// 2. 插入数据
int tree_insert(struct bin_tree * atree, int value) {}
// 3. 查找数据。根据值查找制定的节点，如果找不到返回NULL.
struct bnode * tree_search(struct bin_tree * atree, int value) {}
// 4. 先序遍历
void tree_preorder(struct bin_tree *atree) {}
// 5. 中序遍历
void tree_inorder(struct bin_tree *atree) {}
// 6. 后序遍历
void tree_postorder(struct bin_tree *atree) {}
// 7. 删除数据,如果成功删除则返回1，失败返回0
int tree_delete(struct bin_tree *atree, int value) {}
// 8. 二叉树销毁
void tree_destroy(struct bin_tree *atree) {}int main(int argc, char * argv[]) {struct bin_tree binary_search_tree;tree_init(&binary_search_tree);printf("程序退出\n");
}最终实现
// 二叉排序树
#include <stdio.h>
#include <stdlib.h>// 二叉树的节点结构
struct bnode {int data;struct bnode * left;struct bnode * right;
};// 用于定义一棵二叉树
struct bin_tree {struct bnode * root;
};// 创建二叉树的节点，失败返回NULL；
struct bnode * create_node(int value) {struct bnode * temp = (struct bnode *)malloc(sizeof(struct bnode));if (NULL == temp)return NULL;temp->data = value;temp->left = temp->right = NULL;return temp;
}// 将 new_node 节点挂在 root 指针上。
void insert_node(struct bnode ** proot, struct bnode*new_node)
{if (NULL == *proot) {*proot = new_node;return;}struct bnode * temp_root = *proot;if (new_node->data < temp_root->data) {// 插入左子树insert_node(&temp_root->left, new_node);} else {// 插入右子树insert_node(&temp_root->right, new_node);}}
// 递归实现节点的删除.找到并删除返回1，失败返回0
int remove_node(struct bnode ** proot, int value) {struct bnode *temp = *proot;if (NULL == temp)return 0;if (temp->data != value) { // 进入下一层删除if (value < temp->data) return remove_node(&temp->left, value);elsereturn remove_node(&temp->right, value);}// 走到此处,temp->data一定等于value,删除temp 指向的节点// 左右都为空if (temp->left == NULL && temp->right == NULL) {*proot = NULL;free(temp);return 1;}if (temp->left != NULL && temp->right == NULL) {*proot = temp->left;free(temp);return 1;}if (temp->left == NULL && temp->right != NULL) {*proot = temp->right;free(temp);return 1;}// 左右都不为空 将右子树插入左子树，insert_node(&temp->left, temp->right);*proot = temp->left;free(temp);return 1;}
// 递归实现删除子树的节点,将指向此子树的指针置空
void free_sub_tree(struct bnode ** proot) {struct bnode * temp = *proot;if (NULL == temp)return ;// 删除左子树free_sub_tree(&temp->left);// 删除右子树free_sub_tree(&temp->right);// 删除当前节点free(temp);// 将指向此节点的指针指控*proot = NULL;
}
// 先序遍历(递归实现:根、左、右);
void preorder(struct bnode *root) {if (NULL == root)return;printf("%d ", root->data);preorder(root->left);preorder(root->right);}
// 5. 中序遍历(递归实现:左、根、右);
void inorder(struct bnode *root) {if (NULL == root)return;inorder(root->left);printf("%d ", root->data);inorder(root->right);
}
// 6. 后序遍历(递归实现:左、右、根);
void postorder(struct bnode *root) {if (NULL == root)return;postorder(root->left);postorder(root->right);printf("%d ", root->data);
}// ---------------------------------------------
// 1. 二叉树初始化
void tree_init(struct bin_tree * atree) {atree->root = NULL;
}
// 2. 插入数据,成功返回1，失败返回0
int tree_insert(struct bin_tree * atree, int value) {struct bnode *temp = create_node(value);if (NULL == temp)return 0;insert_node(&atree->root, temp);// atree->root = temp;
}
// 3. 查找数据。根据值查找制定的节点，如果找不到返回NULL.
struct bnode * tree_search(struct bin_tree * atree, int value) {struct bnode * temp = atree->root;while (NULL != temp) {if (temp->data == value)return temp;// 找到了if (value < temp->data) temp = temp->left; // 去左子树去找elsetemp = temp->right; // 去右子树去找}return NULL; // 没找到
}
// 4. 先序遍历
void tree_preorder(struct bin_tree *atree) {preorder(atree->root);printf("\n");
}
// 5. 中序遍历
void tree_inorder(struct bin_tree *atree) {inorder(atree->root);printf("\n");
}
// 6. 后序遍历
void tree_postorder(struct bin_tree *atree) {postorder(atree->root);printf("\n");
}
// 7. 删除数据,如果成功删除则返回1，失败返回0
int tree_delete(struct bin_tree *atree, int value) {return remove_node(&atree->root, value);
}
// 8. 二叉树销毁
void tree_destroy(struct bin_tree *atree) {free_sub_tree(&atree->root);
}int main(int argc, char * argv[]) {struct bin_tree bst;tree_init(&bst);tree_insert(&bst, 8);tree_insert(&bst, 6);tree_insert(&bst, 7);tree_insert(&bst, 10);struct bnode * temp = tree_search(&bst, 15);if (temp)printf("finded %d\n", temp->data);elseprintf("not finded\n");tree_preorder(&bst); //8 6 7 10tree_inorder(&bst); // 6 7 8 10tree_postorder(&bst); //7 6 10 8int ret = tree_delete(&bst, 8);printf("tree_delete return:%d\n", ret); tree_preorder(&bst);tree_destroy(&bst);tree_preorder(&bst);printf("程序退出\n");
}