数据结构与算法--树
概念：一种数据结构，每个结点有且只有唯一的前驱结点，但可以具有多个后继结点
类别：
- （无）有序树
- （完全、满、扩充）二叉树
- 森林
相关：（父、子、兄弟、叶子、分支、祖先、子孙）结点、边、路径、度、层数、高度
二叉树的抽象数据类型定义（C++）：
1. template<class T>
2. class BinaryTreeNode{
3. friend class BinaryTree<T>;
4. private:
5. T element; //结点的数据域
6. BinaryTreeNode<T> * leftChild; //结点的左孩子指针域
7. BinaryTreeNode<T> * rightChild; //结点的右孩子指针域
8. public:
9. BinaryTreeNode();
10. BinaryTreeNode(const T & ele);
11. BinaryTreeNode(const T & ele, BinaryTreeNode<T> * l, BinaryTreeNode<T> * r);
12. BinaryTreeNode<T> * getLeftChild() const;
13. BinaryTreeNode<T> * getRightChild() const;
14. void setLeftChild(BinaryTreeNode<T> * l);
15. void setRightChild(BinaryTreeNode<T> * r);
16. T getValue() const;
17. void setValue(const T & val);
18. bool IsLeaf() const; //判断该结点是否是叶子结点，若是，则返回true
19. };
20.
21. template<class T>
22. class BinaryTree{
23. private:
24. BinaryTreeNode<T> * root; //二叉树根结点指针
25. public:
26. BinaryTree();
27. ~BinaryTree();
28. bool IsEmpty() const; //判断二叉树是否为空树
29. BinaryTreeNode<T> * getRoot() const;
30. BinaryTreeNode<T> * getParent(BinaryTreeNode<T> * current) const;
31. BinaryTreeNode<T> * getLeftSibling(BinaryTreeNode<T> * current) const;
32. BinaryTreeNode<T> * getRightSibling(BinaryTreeNode<T> * current) const;
33.
34. void breadthFirstOrder(); //广度优先遍历
35. void preOrder(); //先序遍历
36. void inOrder(); //中序遍历
37. void postOrder(); //后序遍历
38. void levelOrder(); //层次遍历
39. void deleteBianryTree();
40. };
二叉树的存储
• 顺序存储（完全二叉树，存在空间浪费）
• （三）二叉链表（指针域，存在空间浪费）
二叉树的遍历
• 广度优先遍历（用队列，先从上往下，再从左往右）
• 深度优先遍历（先序、中序、后序[先、中、后指的是根结点的访问顺序，递归定义]）
○ 先序遍历（左子树非空||栈非空，将右根压栈）
○ 中序遍历（左子树非空||栈非空，将根压栈）
○ 后序遍历（pre指向上一个访问过的结点，两层循环，将次根压栈）
线索二叉树
• 定义：利用二叉链表的空指针域（n+1个）来存放指向结点在某种遍历次序下的前驱和后继结点的指针
• 线索化（pre指向上一个访问过的结点，先建立前驱线索，再建立后继线索）
• 遍历（最左，右）
• [删除]插入[左]右孩子（修改前驱&后继）
二叉搜索树
• 定义：左子树所有结点关键码小于根结点关键码，右子树的大于根结点的
• 查找（二分）&插入（作为叶子结点）
• 删除（子树数目<=1，子树数目==2[合并删除{左子最右下}&复制删除{左子最右下||右子最左下}]）
平衡二叉树
• 定义：二叉搜索树的一种特殊情况，即每个结点的平衡因子（右子树高度与左子树高度之差）的绝对值不超过1或者是空树
• 查找（同二叉搜索树）
• 插入（[左、右]单旋转{回溯取三个结点，折中}、[左右、右左]双旋转{回溯取三个结点，折变直，再变折，左右子树分开}）
• 删除（回溯修改平衡因子（失衡则调整），子树高度变化则继续回溯，反之停止）
堆
• 定义：[最小]最大堆=完全二叉树+[最小]最大树（每个结点的关键码大于或等于其子结点的关键码）
• 插入（层次最末尾，比较交换）&删除（交换+插入逆过程）
• 构建（筛选法[从第一个分支结点开始调整]）
优先队列：堆是一种优先队列，能访问和删除的元素具有最高优先级
Huffman树（最优二叉树）
• 定义：叶子结点带权，带权外部路径长度（根结点到扩充二叉树的外部结点的路径长度）WPL最小
• 构建：合并两根结点权重（子结点权重之和）最小的树，将新树加入集合，删除旧树，直至集合只剩一棵树
• 应用：Huffman编码
二叉树、树、森林
• 转换 ：一一对应（假设树和森林都是有序树，兄弟连心、父子断绝<–>右父重聚、父右断绝）
• 遍历：广度优先遍历、深度优先遍历（先根次序、后根次序）
• 存储：孩子表示法、孩子-兄弟表示法、双亲表示法