数据结构与算法-二叉树

一.二叉树的基本概念

1.什么是二叉树？

二叉树是 n (n>0)个结点的有限集，若n = 0，它是空集。

二叉树由一个根节点及两颗不相交的左子树和右子树组成。

2.二叉树的特点

(1)每个节点最多有2个孩子，不存在度大于2的节点                                                                 

(2)子树有左右之分，不可颠倒

(3)二叉树可以是空集合，根可以有空的左子树或空的右子树

3.二叉树的链式存储                                    

问：n各节点的二叉链表中，有 n+1 个空指针域

4.二叉树的性质

5.二叉树的特殊形式：满二叉树和完全二叉树

(1)满二叉树性质：

(2)完全二叉树性质：

6.二叉树的遍历:先序遍历(DLR)、中序遍历(LDR)、后序遍历(LRD)

(1)先序遍历：根节点->左子树->右子树

(2)中序遍历：左子树->根节点->右子树

(3)后序遍历：左子树->右子树->根节点

7.由遍历序列确定二叉树

已知先序(或后序)遍历 和 中序遍历，可以确定二叉树

例如：

先序：A B C D E F G H I J     中序:C D B F E A I H G J

(1)已知先序可确定根节点(A)

(2)确定根节点，可将中序遍历分为C D B F E A I H G J，绿色左子树，橙色右子树

(3) 先序：A B C D E F G H I J，左子树的根节点B，右子树的根节点G

(4) 中序：C D B F E A I H G J，CD为B左子树，FE为B右子树，IH为G左子树，J为G右子树

(5) 先序：A B C D E F G H I J，C为根，中序：C D B F E A I H G J，D为C的右孩子

先序：A B C D E F G H I J，E为根，中序：C D B F E A I H G J， F为E的左孩子 

先序：A B C D E F G H I J，E为根，中序：C D B F E A I H G J， J为G右孩子，H为G左孩子

先序：A B C D E F G H I J，E为根，中序：C D B F E A I H G J， I为H的左孩子

注意：先序(或后序)判断根，中序判断左右子树

二.二叉树的基本操作

1.创建二叉树链表

2.二叉树遍历：

a.先序遍历b.中序遍历：c.后序遍历：

3.层次遍历：(需要队列进行入队出队)                                                                                                   省略....

4.复制二叉树                                 

5.计算二叉树的深度

6.计数二叉树节点数

7.计算二叉树叶子结点数

三.线索二叉树

1.为什么研究线索二叉树？

答：通过遍历容易找到结点的左孩子和右孩子，但无法直接找到遍历下结点的前驱和后继结点。

解决方法：(1)再次遍历    (2) 设置指向前驱与后继的指针域    (3)利用二叉链表中的空指针域          

2.如何利用二叉链表中的空指针域

答：若某个结点的左孩子为空，则左孩子的指针域指向其前驱，若某个结点的右孩子为空，则右孩子的指针域指向其后继。---这种方式称为"线索"。

为了区分指针指向是孩子还是前驱或后继，在二叉链表中每个节点增加两个标志位  ltag 和 rtag，