数据结构笔记——06树和二叉树

文章目录

• • • 一、树的基本概念
    • • 1.树的定义
      • 2.树的逻辑表示方法
      • 3.树的基本术语
      • 4.树的性质
      • 5.树的基本运算
      • 6.树的存储结构
      • • 1)双亲存储结构
        • 2)孩子链存储结构
        • 3)孩子兄弟链存储结构
    • 二、二叉树的概念和性质
    • • 1.二叉树的定义
      • 2.二叉树的性质
      • 3.二叉树与树、森林之间的转换
      • • 1)森林、树转换为二叉树
        • 2)二叉树还原为树\森林
    • 三、二叉树的存储结构
    • • 1.二叉树的顺序存储结构
      • 2.二叉树的链式存储结构
    • 四、二叉树的基本运算及其实现
    • • 1.二叉树的基本运算的概述
      • 2.二叉树的基本运算算法的实现
      • • 1)创建二叉树CreateBTree(*b,*str)
        • 2)销毁二叉树DestroyBTree(&b)
        • 3)查找结点FindNode(b,x)
        • 4)找孩子结点LchildNode(p )或RchildNode(p )
        • 5)求高度BTHeight(b)
        • 6)输出二叉树DispBTree(b)
    • 五、二叉树的遍历
    • • 1.二叉树遍历的概念
      • 2.先序、中序和后序遍历递归算法
      • 3.先序、中序和后序遍历非递归算法
      • • 1)先序遍历非递归算法
        • 2)中序遍历非递归算法
        • 3)后序遍历非递归算法
      • 4.层次遍历算法
    • 六、二叉树的构造
    • 七、线索二叉树
    • • 1.线索二叉树的概念
      • 2.线索化二叉树
      • 3.遍历线索化二叉树
    • 八、哈夫曼树
    • • 1.哈夫曼树概述
      • 2.哈夫曼树的构造算法
      • 3.哈夫曼编码
    • 九、用并查集求解等价问题
    • • 1.并查集的定义
      • 2.并查集的算法实现
      • • 1）并查集的初始化
        • 2）查找一个结点所属的子集树
        • 3）两个结点所属子集树的合并