树！！！

课件😊

树的性质

$$1.除根节点没有父亲点外，其余节点有且仅有一个父亲点。$$ $$2.n个节点的树，有且仅有n-1条边。$$ $$3.树中任意两个节点之间有且仅有一条简单路径。$$

二叉树

概念: 度数为二，即每个节点至多两个子节点

二叉树的遍历以及顺序

$$先序遍历:根节点→左子树→右子树$$ $$后序遍历:左子树→右子树→根节点$$ $$中序遍历:左子树→根节点→右子树$$ $$层次遍历:左→右(每层)$$

二叉树性质

性质一、

$$在二叉树第i层上最多有2^{i-1}个节点(i>=1)$$

性质二、

$$深度为k的二叉树至多有2^k-1个节点(k>=1)$$

性质三、

$$对任意一棵二叉树，如果其叶节点数为n_0，度为2的节点数为n_2，则一定满足:n_0=n_2+1。$$

性质四、

$$具有n个节点的完全二叉树的深度为floor({log_2}^n)+1$$

可写作:

$$具有n个节点的完全二叉树的深度为⌊log_{2}n⌋+1$$

性质五、

$$具有n个节点的二叉树的高度至少为log_2(n+1)$$

性质六、

$$对于一棵n个结点的完全二叉树的任一个结点(编号为i)，有$$ $$1.如果i=1，则结点i为根，无父节点；如果i>1，则其父节点编号为i/2。$$ $$2.如果2*i>n，则结点i无左孩子，否则左孩子编号为2*i。如果2*i+1>n，则结点i无右孩子，否则右孩子编号为2*i+1。 $$

性质七(补充)

$$在二叉树中，度为2的节点数 = 叶子节点数 - 1。对于n个节点的二叉树，最大度为2的节点数为floor((n-1)/2) $$

可写作:

$$在二叉树中，度为2的节点数 = 叶子节点数 - 1。对于n个节点的二叉树，最大度为2的节点数为⌊(n-1)/2⌋ $$

哈夫曼编码！！！