有序二叉树
之前研究的都是 – 一对一的结构
现实存在很多一对多的情况 – 研究一对多的数据结构 – 树
树中的每个元素称为节点(node)
每个节点都有零个或者多个子节点
没有父结点的节点称为根节点,
每一个非根节点有且仅有一个父结点
根节点左侧的部分可以看做是一颗新的树, 这棵树就是属于根节点的左子树.
同样, 根节点右侧的部分就是其右子树
一个节点的子节点(子树)的数量称为节点的度
节点的层次 – 节点的层次从根节点开始定义, 根为第一层, 根的子节点为第二层, 依次向下分
有序二叉树
每个节点最多含有两个子树的树称为二叉树
一般来说, 当左子树不为空的时候, 左子树的元素值小于根节点, 当右子树不为空的时候, 右子树的
元素值大于根节点.
一句话, 不管站在哪个节点上, 左边总是小于右边
有序二叉树的遍历
三种方式:
先序遍历 处理节点自身的数据 – 处理左子节点 – 处理右子结点 (自-左-右)
中序遍历 处理左子节点 – 处理节点本身数据 – 处理右子节点 (左-自-右)
从小到大 – 中序
后序遍历 处理左子节点 – 处理右子结点 – 处理节点本身数据 (左-右-自)
当做的树的递归
树
根节点
左子树 右子树
树 – 左子节点 – 根节点 – 右子结点
左子树 – 排序
根节点
右子树 – 排序
一对多就是树 – 不一定
有序二叉树涉及的两个结构体
描述节点属性的结构体
struct node{
int data;//数据
//两个指针
struct node* left;//保存左子结点地址
struct node* right;//保存右子结点地址
};
描述整棵树属性的结构体
struct tree{
struct node* root;//保存根节点的首地址
int cnt;//保存有效节点个数
};
mkdir tree
vim tree.h
vim tree.c
vim main.c
左子结点 – 地址就是NULL
一个节点通过指针来找到子节点
struct node{
int data;//数据
//两个指针
struct node* next;
struct node* prev;
};
struct node{
int data;//数据
//两个指针
struct node* left;//保存左子结点地址
struct node* right;//保存右子结点地址
};
typedef struct tree{
struct node* root;//根节点
int cnt;
}tree_t;
void insert(node_t** pproot, node_t* pnew)
高级指针 – 二级指针
修改一级指针内容 – 函数传递参数的过程中 – 传递的是二级指针
修改p的指向 – 修改一级指针的指向 – 参数 必定是二级指针
将新的结点插入到有序二叉树中
pnew
1.判断有序二叉树的根节点是否为空 – 为空, 直接插入即可; 非空, 比较
2.比较
新的结点的数据和根节点的数据相比
新的结点数据小于根节点的数据 插入到左子树
将左子树当做一颗新的树插入
否则 插入到右子树
将右子树当做一颗新的树插入
删除某个节点
查找节点的递归函数
1.判断有序二叉树是否为空
为空, 不再寻找; 直接结束
2.非空
2.1.和根节点匹配
2.2.查找的数据 > 根节点数据
右子树查找
2.3.查找的数据 < 根节点数据
左子树查找
=======================
基本排序和查找算法
