数据结构与算法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. 左子树的所有节点的数值都小于 根节点的值。
2. 右子树的所有节点的数值都大于等于根节点的值。

特点：

1、如果是一个满二叉排序树（二叉查找树），他的查找的时间复杂度是

O(log2n)O(log_2^n)O(log2n​)

二叉排序树插入和删除时不需要移动节点数据，速度快。

二叉排序树的基本操作：

1. 二叉树初始化
2. 插入数据
3. 查找数据。
4. 先序遍历
5. 中序遍历
6. 后序遍历
7. 删除数据
8. 二叉树销毁

框架代码

// 二叉排序树
#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);
  else
   return 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;  // 去左子树去找
  else
   temp = 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);
 else
     printf("not finded\n");
 tree_preorder(&bst); //8 6 7 10
 tree_inorder(&bst); // 6 7 8 10
 tree_postorder(&bst); //7 6 10 8
 int ret = tree_delete(&bst, 8);
 printf("tree_delete return:%d\n", ret); 
 tree_preorder(&bst);
    tree_destroy(&bst);
 tree_preorder(&bst);


 printf("程序退出\n");
}