在线制作网站地图,外国做ppt的网站,可以看所有网站的浏览器,虎嗅wordpress文章目录 二叉树的定义和基本术语特殊的二叉树满二叉树完全二叉树二叉排序树平衡二叉树 二叉树的常考性质完全二叉树的常考性质二叉树的存储结构顺序存储链式存储 二叉树的先中后序遍历先序遍历#xff08;空间复杂度#xff1a;O#xff08;h#xff09;#xff09;中序遍… 文章目录 二叉树的定义和基本术语特殊的二叉树满二叉树完全二叉树二叉排序树平衡二叉树 二叉树的常考性质完全二叉树的常考性质二叉树的存储结构顺序存储链式存储 二叉树的先中后序遍历先序遍历空间复杂度Oh中序遍历后序遍历应用 二叉树的层序遍历由遍历序列构造二叉树线索二叉树线索二叉树的存储结构二叉树的线索化二叉树的线索化 二叉树的定义和基本术语
二叉树的基本概念 二叉树是nn0个结点的有限集合 ①或者为空的二叉树即n0 ②或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成左子树和右子树又分别是一颗二叉树 特点 1、每一个结点至多只有两棵子树 2、左右子树不能颠倒二叉树是有序树
注意区别度为2的有序树与二叉树的区别 度为2的树肯定是非空树所有结点的度2至少有一个结点的度为2 二叉树可以为空树所有的结点只要2就可
特殊的二叉树
满二叉树
定义一颗高度为n且有 2ⁿ-1 个结点的二叉树
特点 1、只有最后一层有叶子结点 2、不存在度为1的结点只存在度为0或者2的结点 3、按层序从1开始编号结点 i 的左孩子为 2i右孩子为 2i1结点 i 的父节点为 ⌊ i/2 ⌋
完全二叉树
定义当且仅当其每个结点都与高度为 h 的满二叉树中的编号为 1~n 的结点一一对应时称为完全二叉树 特点 1、只有最后两层有叶子结点 2、最多只有一个度为1的结点 3、按层序从1开始编号结点 i 的左孩子为 2i右孩子为 2i1结点 i 的父节点为 ⌊ i/2 ⌋如果有的话 4、i ⌊ n/2 ⌋ 为分支结点i ⌊ n/2 ⌋ 为叶子结点
如果某结点只有一个孩子那么这个孩子一定是左孩子
二叉排序树
定义一颗二叉树或者空二叉树具有如下性质的称为二叉排序树 1、左子树上所有结点的关键字均小于根结点的关键字 2、右子树上所有结点的关键字均大于根结点的关键字 3、左子树和右子树又各是一棵二叉排序树
二叉排序树可用于元素的排序和搜索
平衡二叉树
定义树上任一结点的左子树和右子树的深度之差不超过1
平衡二叉树能有更高的搜索效率
二叉树的常考性质
考点一设非空二叉树中度为0、1、2的结点个数分别为n0、n1、n2则 n0 n2 1; ( 叶子结点比二分支结点多一个 )
假设树中结点总数为n则 ① n n0 n1 n2 ② n n1 2*n2 1 树的结点数 总度数 1 ②-①得 n0 n2 1
考点二二叉树第 i 层至多有 2ⁱ⁻¹ 个结点i1 源于: m 叉树第 i 层至多有 mⁱ⁻¹ 个结点i1
考点三高度为 n 的二叉树至多有 2ⁿ - 1 个结点满二叉树 源于: 高度为 n 的 m 叉树至多有 mⁿ - 1/m-1 个结点
完全二叉树的常考性质 常考考点2对于完全二叉树可以由结点数 n 推出度为0、1、2的结点个数为n0、n1、n2 完全二叉树最多只有一个度为1的结点所以 n1 0或1 n0 n2 1 ---- n0 n2 2*n2 1 一定是奇数 若完全二叉树有 2k 个偶数个结点则 n n1 n2 n3由上面得 n0 n2 一定是奇数所以只有 n1 1 时 n 才会是偶数 所以 n1 1n0 kn2 k-1 若完全二叉树有 2k-1 个奇数个结点则 n n1 n2 n3由上面得 n0 n2 一定是奇数所以只有 n1 0 时 n 才会是奇数 所以 n1 0n0 kn2 k-1 二叉树的存储结构
顺序存储
定义一个长度为 MaxSize 的数组t按照从上至下从左至右的顺序依次存储完全二叉树中的各个结点
#define MaxSize 100
struct TreeNode{ElemType value; // 结点中的数据元素bool isEmpty; // 结点是否为空
}// 初始化时所有结点标记为空
for(int i 0; i MaxSize; i){t[i].isEmpty true;
}TreeNode t[MaxSize]几个重要的常考的基本操作 i 的左孩子 ———— 2i i 的右孩子 ———— 2i1 i 的父节点 ———— ⌊ i/2 ⌋ i 所在的层次 ———— 若完全二叉树中共有n个结点则 判断 i 是否有左孩子 ———— 2i n 判断 i 是否有右孩子 ———— 2i1 n 判断 i 是否是叶子/分支结点 ———— i ⌊ n/2 ⌋ 注意如果不是完全二叉树依然按照层序将各个结点顺序存储那么无法从结点编号反映出以上这些逻辑关系所以一定要把二叉树的结点编号与完全二叉树对应起来但是会导致出现很多空值的存储单元
最坏情况高度为 n 且只有 n 个结点的单支树所有结点只有右孩子也至少需要 2ⁿ - 1 个存储单元
结论二叉树的顺序存储结构只适合存储完全二叉树
链式存储
typedef struct BiTNode{ElemType data;struct BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;假设有n个结点则有2n个指针域除了根结点每一个结点头上都会连接一个指针域那么就有n-1个有值的指针域得出就会有n1个空指针域 n个结点的二叉链表共有n1个空链域 根据实际需求决定要不要加父结点指针三叉链表——方便找父结点
typedef struct BiTNode{ElemType data;struct BiTNode *lchild,*rchild; // 左右孩子指针struct BiTNode *parent; // 父结点指针
}BiTNode,*BiTree;二叉树的先中后序遍历
先序遍历根左右中序遍历左根右后序遍历左右根
其中这三种遍历方式与前中后缀表达式的关系 先序遍历——前缀表达式 中序遍历——中缀表达式需要加界限符 后序遍历——后缀表达式
先序遍历空间复杂度Oh
void PreOrder(BiTree T){if(T!NULL){visit(T); //访问根结点PreOrder(T-lchild); // 递归遍历左子树PreOrder(T-rchild); // 递归遍历右子树}
}中序遍历
void PreOrder(BiTree T){if(T!NULL){PreOrder(T-lchild); // 递归遍历左子树visit(T); //访问根结点PreOrder(T-rchild); // 递归遍历右子树}
}后序遍历
void PreOrder(BiTree T){if(T!NULL){PreOrder(T-lchild); // 递归遍历左子树PreOrder(T-rchild); // 递归遍历右子树visit(T); //访问根结点}
}应用
求树的深度
int treeDepth(BiTree T){if(T NULL)return 0;else{int l treeDepth(T-lchild);int r treeDepth(T-rchild);// 树的深度Max(左子树深度右子树深度) 1return lr ? l1 : r1;}
}二叉树的层序遍历
算法思想 ①初始化一个辅助队列 ②根结点入队 ③若队列非空则队头结点出队访问该结点并将其左、右孩子插入队尾如果有的话 ④重复③直至队列为空
// 二叉树的结点链式存储
typedef struct BiTNode{char data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;// 链式队列结点
typedef struct LinkNode{BiTNode *data; // 存指针而不是结点struct LinkNode *next;
}LinkNode;typedef struct{LinkNode *front,*rear; // 队头队尾
}LinkQueue;// 层序遍历
void LevelOrder(BiTree T){LinkQueue(Q);InitQueue(Q); // 初始化辅助队列BiTree p;EnQueue(Q,T); // 将根结点入队while(!IsEmpty(Q)){DeQueue(Q,p); // 队头结点出队visit(p); // 访问出队结点if(p-lchild!NULL)EnQueue(Q,(p-lchild); // 左孩子入队if(p-rchild!NULL)EnQueue(Q,(p-rchild); // 右孩子入队}
}由遍历序列构造二叉树
若只给出一颗二叉树的前中后序遍历序列中的一种不能唯一确定一棵二叉树 能构造二叉树的遍历序列组合 1、前序中序 2、后序中序 3、层序中序
线索二叉树
问题1如何找到指定结点在中序遍历序列中的前驱 问题2如何找到结点的中序后继 找前驱和后继很不方便遍历操作必须从根开始
还记得之前学到的n个结点的二叉树有n1个空链域可以用来记录前驱、后继的信息
线索二叉树的存储结构
typedef struct ThreadNode{ElemType data;struct ThreadNode *lchild,*rchild;int ltag,rtag; // 左右线索标志
}ThreadNode,*ThreadTree;
// tag0 表示指针指向孩子
// tag1 表示指针是线索二叉树的线索化
中序线索化
// 线索二叉树结点
typedef struct ThreadNode{ElemType data;struct ThreadNode *lchild,*rchild;int ltag,rtag; // 左右线索标志
}ThreadNode,*ThreadTree;void visit(ThreadNode *q){if(q-lchildNULL){ //左子树为空建立前驱线索q-lchildpre;q-ltag1;}if(pre!NULLpre-rchildNULL){ //前驱结点的右孩子为空建立前驱结点的后驱线索pre-rchildq;pre-rtag1;}preq;
}//中序遍历二叉树一边遍历一边线索化
void InThread(ThreadTree T){if(T!NULL){InThread(T-lchild); // 中序遍历左子树visit(T); // 访问根结点InThread(T-rchild); // 中序遍历右子树}
}// 全局变量 pre指向当前访问结点的前驱
ThreadNode *preNULL;// 中序线索化二叉树T
void CreateInThread(ThreadTree T){preNULL; // pre初始化为NULLif(T!NULL){InThread(T) //中序线索化二叉树if(pre-rchildNULL)pre-rtag1; // 处理遍历的最后一个点}
}先序线索化与中序遍历有一点不一样为了防止重复指向需要判断lchild不是前驱线索
// 线索二叉树结点
typedef struct ThreadNode{ElemType data;struct ThreadNode *lchild,*rchild;int ltag,rtag; // 左右线索标志
}ThreadNode,*ThreadTree;void visit(ThreadNode *q){if(q-lchildNULL){ //左子树为空建立前驱线索q-lchildpre;q-ltag1;}if(pre!NULLpre-rchildNULL){ //前驱结点的右孩子为空建立前驱结点的后驱线索pre-rchildq;pre-rtag1;}preq;
}//先序遍历二叉树一边遍历一边线索化
void PreThread(ThreadTree T){if(T!NULL){visit(T); // 访问根结点if(T-ltag0){ // 与中序遍历不一样的地方为了防止重复指向需要判断lchild不是前驱线索PreThread(T-lchild); // 与中序遍历不一样的地方为了防止重复指向需要判断lchild不是前驱线索PreThread(T-rchild);}
}// 全局变量 pre指向当前访问结点的前驱
ThreadNode *preNULL;// 先序线索化二叉树T
void CreateInThread(ThreadTree T){preNULL; // pre初始化为NULLif(T!NULL){InThread(T) //先序线索化二叉树if(pre-rchildNULL)pre-rtag1; // 处理遍历的最后一个点}
}后序线索化和中序差不多
// 线索二叉树结点
typedef struct ThreadNode{ElemType data;struct ThreadNode *lchild,*rchild;int ltag,rtag; // 左右线索标志
}ThreadNode,*ThreadTree;void visit(ThreadNode *q){if(q-lchildNULL){ //左子树为空建立前驱线索q-lchildpre;q-ltag1;}if(pre!NULLpre-rchildNULL){ //前驱结点的右孩子为空建立前驱结点的后驱线索pre-rchildq;pre-rtag1;}preq;
}//后序遍历二叉树一边遍历一边线索化
void InThread(ThreadTree T){if(T!NULL){InThread(T-lchild); // 后序遍历左子树InThread(T-rchild); // 后序遍历右子树visit(T); // 访问根结点}
}// 全局变量 pre指向当前访问结点的前驱
ThreadNode *preNULL;// 后序线索化二叉树T
void CreateInThread(ThreadTree T){preNULL; // pre初始化为NULLif(T!NULL){InThread(T) //后序线索化二叉树if(pre-rchildNULL)pre-rtag1; // 处理遍历的最后一个点}
}二叉树的线索化
中序线索二叉树中找到指定结点*p的中序后继next ① 若 p-rtag1, 则 next p-rchild ② 若 p-rtag0, 则 next p的右子树中最左下结点
// 找到以p为根的子树中第一个被中序遍历的结点
ThreadNode *Firstnode(ThreadNode *p){// 循环找到最左下结点不一定是叶结点while(p-ltag0) pp-lchild;return p;
}// 在中序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p){// 右子树下最左的结点if(p-rtag0) return Firstnode(p-rchild);esle return p-rchild; // rtag 1 直接返回后继线索
}// 对中序线索二叉树进行中序遍历利用线索实现的非递归算法空间复杂O1
void Inorder(TreadNode *T){for(ThreadNode *pFirstnode(T);p!NULL;pNextnode(p)){visit(p);}
}中序线索二叉树中找到指定结点*p的中序前驱pre ① 若 p-ltag1, 则 pre p-rchild ② 若 p-rlag0, 则 pre p的左子树中最右下结点
// 找到以p为根的子树中最后一个被中序遍历的结点
ThreadNode *Lastnode(ThreadNode *p){// 循环找到最左下结点不一定是叶结点while(p-rtag0) pp-rchild;return p;
}// 在中序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreadNode *p){// 左子树中最右下结点if(p-ltag0) return Lastnode(p-lchild);esle return p-lchild; // ltag 1 直接返回前驱线索
}// 对中序线索二叉树进行逆向中序遍历
void RevInorder(TreadNode *T){for(ThreadNode *pLastnode(T);p!NULL;pPrenode(p)){visit(p);}
}在先序线索二叉树中找到指定结点*p的先序后继next ① 若 p-rtag1, 则 next p-rchild ② 若 p-rtag0, 1、若p有左孩子则先序后继为左孩子 2、若p没有左孩子则先序后继为右孩子
在先序线索二叉树中找到指定结点*p的先序前驱pre ① 若 p-ltag1, 则 next p-lchild ② 若 p-ltag0, 需要从头开始遍历
在后序线索二叉树中找到指定结点*p的后序前驱pre ① 若 p-ltag1, 则 pre p-lchild ② 若 p-ltag0, 1、若p有右孩子则后序前驱为右孩子 2、若p没有右孩子则后序前驱为左孩子
在后序线索二叉树中找到指定结点*p的后序后继next ① 若 p-rtag1, 则 next p-rchild ② 若 p-rtag0, 需要从头开始遍历
