note:
先理解思想, 再理解代码;
如下只是最基本和核心的;
树的定义
Tree是n个结点的有限集合, 非空树遵循:
(1) 有且仅有一个特定的称为根的结点;
(2) 当n>1时, 其余结点可分为m个互不相交的有限集合T1, T2, ..., Tm, 其中每个集合本身又是一棵树, 并且称为根的子树(SubTree).
- 从定义不难看出, 树的结构先天给人以递归的方便;
树的各个名词
- 度: 结点拥有的子树的数目叫作"度"(degree);
- 度为0的节点就是叶子, 度非0的结点是内结点;
- 父节点, 祖先节点, 孩子节点, 子孙节点;
- 兄弟节点;
- 层次是从根(第一层)往下算的层数, 也叫深度;
- 高度是从最下层开始往上算;
- 有序树: 如果将节点看成从左向右有次序的, 那么该树就是有序的, 否则就是无序的;
- 森林: m棵互相不相交的树的集合;
二叉树
- 只有左子树和右子树, 而且有序;
- 完全二叉树: 除了最后一层, 其他都满;
- 满二叉树: 完全二叉树+最后一层也满;
二叉树的特性
- 性质1: 二叉树的第i层最多有2^(i-1)个节点;
- 性质2: 深度为k的二叉树最多有(2^k)-1个节点;
- 有n个节点的二叉树高度是floor(lgn)+1; //约定最下层的高度为1;
- 性质3: n0 = n2+1 //度为0的节点数n0, 度为2的节点数为n2;
证明: 利用总数和, 出入相等的关系来证明.
和等式: 二叉树中, N = n0 + n1 + n2, 不存在任何其他度(因为二叉树最大的度就是2);
出入等式: N-1(入) = n1+2*n2;
和等式代入出入等式, 则n0 = n2+1;
- 性质4: 某下标为i的非根节点的父节点是floor(i/2), 左子节点是2i, 右子节点是2i+1;
- 比如4, 5的父节点是2; 4的左子节点是8, 右子节点是9;
二叉树的存储结构
顺序存储(顺序表)
/*顺序表存储树*/
//其中parent是也可以去掉的属性;
typedef struct TreeNode{
ElemType data;
int lchild, rchild, parent;
}
typedef struct BinaryTree{
TreeNode[] tree;
int root;
}
链式存储(链表) 比较推荐
/*三叉链表*/
//如果去掉parent, 那么就是二叉链表;
typedef struct TreeNode {
ElemType data;
struct TreeNode *lchild, *rchild, *parent;
}
typedef struct BinaryTree{
TreeNode *root;
}
二叉树的遍历
深度优先
1. 先序
定义: 上左右
/*先序遍历*/
void Traverse( TreeNode T[], index ) {
if (index!=-1)
visit(Tree[index]);
Traverse( T, Tree[index].lchild]);
Traverse( T, Tree[index].rchild);
}
2. 中序
定义: 左上右
/*中序遍历*/
void Traverse( TreeNode T[], index ) {
if (index!=-1)
Traverse( T, Tree[index].lchild]);
visit(Tree[index]);
Traverse( T, Tree[index].rchild);
}
/*中序不递归*/
void Traverse(BiTree T, visit) {
Stack s = new Stack();
while (T!=null || s.isEmpty==false) {
s.push(T);
T=T.left;
} else {
T = s.pop();
visit(T);
T = T.right;
}
}
中序迭代 Python
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
def traverse(root):
S = []
node = root
while node or S:
if node:
S.append(node)
node = node.left
else:
node = S.pop()
ans.append(node.val)
node = node.right
traverse(root)
return ans
3. 后序
定义: 左右上
/*后序遍历*/
void Traverse( TreeNode T[], index ) {
if (index!=-1)
Traverse( T, Tree[index].lchild]);
visit(Tree[index]);
Traverse( T, Tree[index].rchild);
}
后序迭代法 python
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
def traverse(root):
S = []
node = root
prev = None
while node or len(S) != 0:
if node:
S.append(node)
node = node.left
else:
node = S.pop()
if not node.right or prev == node.right: # visited or empty
ans.append(node.val)
prev = node
node = None
else: # visit right
S.append(node)
node = node.right
traverse(root)
return ans
广度优先
- 广度优先就是要求从上到下, 从左到右, 在本层全部遍历后才往下一层;
void Traverse( TreeNode T[SIZE], index) {
for i = index ~ SIZE
visit T[i];
}
二叉树的线索化
对于链表表示的二叉树, 我们希望能获得每个节点在遍历顺序中的前驱和后继节点, 这就是二叉树的线索化问题.
- 解决思路:
(1) 直觉上, 直接加上fwd和bkwd指针分别指向遍历中的前驱和后继就行了;
(2) 为了优化数据结构所占用的存储空间, 我们可以利用二叉链表表示二叉树的过程中有n+1个空指针的现象, 加以利用;
(3) 我们把fwd和bkwd指针替换成一个只需要占1位bit的变量LTag和RTag, 用来指示指针lchild和rchild指针是否为空;
typdef struct TreeNode{
ElemType data;
struct TreeNode *lchild, *rchild;
pointerTag LTag, RTag;
}
普通的树和森林
普通树的存储结构
1. 父亲表示法
typedef struct {
ElemType data;
int parent;
}TreeNode;
/*整棵树*/
typdef struct {
TreeNode nodes[MAX_TREE_SIZE];
int r, n; //root的index和节点数目n;
}Tree;
2. 孩子表示法
- 孩子表示法比较费解一些, 预计使用频率不会很高
- 只要让每个结点都存储其孩子的位置信息, 那么就是孩子表示法; 此处由于普通树的孩子数目不像二叉树那样确定, 最好使用链表来存储孩子节点位置信息;
- 结构是: Tree -- TreeNode -- ChildInfo
/*孩子位置链表的结点*/
typedef struct {
int childIndex;
struct ChildInfo *next;
}ChildInfo ,*ChildList;
/*树中的结点*/
typedef struct {
ElemType data;
ChildList childs;
} TreeNode;
/*整棵树*/
typdef struct {
TreeNode nodes[MAX_TREE_SIZE];
int r, n; //root的index和节点数目n;
}Tree;
3. 孩子兄弟表示法
- 实际上已经把树转化为了二叉树;
/*Node*/
typedef struct {
ElemType data;
int firstChild, nextSibling;
} TreeNode;
/*整棵树Tree*/
typdef struct {
TreeNode nodes[MAX_TREE_SIZE];
int r, n; //root的index和节点数目n;
} Tree;
树和森林与二叉树之间的转化
1. 普通树和二叉树的相互转化(基本要求)
使用孩子兄弟法: 定义二叉树T的左子节点T->lchild是first-child, 这个左子节点的右子节点T->lchild->rchild是它的next-sibling, 而这个左子节点的左子节点则是它自己的first-child, 如此递归定义, 从而实现普通的树结构转化成二叉树;
note: 转化成的二叉树的根节点肯定没有右子节点!
2. 普通森林转化成二叉树(基本要求)
note: 这次, 跟上面不同, 二叉树的根节点有右子节点, 而且是代表森林中不同的树的根节点;
普通树和森林的遍历
1. 普通树的遍历
先根遍历普通树:
先访问根结点, 然后遍历子树
==> 如果转化为二叉树的话, 映射为先序; //画图容易看出;
后根遍历普通树:
先遍历子树, 然后才访问根结点
==> 如果转化为二叉树的话, 映射为中序; //画图容易看出;
2. 森林的遍历
先序遍历森林(类似先根) ==> 二叉树的先序:
(1) 先访问森林中第一棵树的根节点
(2) 先序访问根节点的子树;
(3) 先序访问其他树组成的森林;中序遍历森林(类似后根) ==> 二叉树的中序:
(1) 中序访问森林中第一棵树的根节点的子树;
(2) 访问第一棵树的根节点;
(3) 中序访问其他树组成的森林;
哈夫曼编码(Huffman coding)
node BuildHuffmanTree(C[]) {
n = C.length;
Q is a Minimum Priority built from C;
for ( i = 1~n-1) //到第n-1次的操作后, Q中应该只有一个元素
node z is a new node;
z.lchild = x = Q.extractMin();
z.rchild = y = Q.extractMin();
z.weight = x.weight+y.weight;
Q.insert(z);
return Q.extractMin(); //return the root of the tree;
}
Encode(C, root) {
for (i = 1~C.length) {
j = i;
if (C[j].parent != null) {
if (C is C.parent.lchild) {C[i].code = 0 + C[i].code}
if (C is C.parent.rchild) {C[i].code = 1 + C[i].code}
}
j = C[j].parent;
}
}
