数据结构和算法----二叉树

 一、说二叉树之前先说说树结构

树这种结构就像我们现实生活中的’树‘，这里面每个元素我们叫做“节点”；用来连线相邻节点之间的关系，我们叫做“父子关系”。

 

 还有一些其他的概念：

1、跟节点：树的顶端节点

2、分支节点：至少有一个子节点的节点

3、度：节点所拥有的子树个数

4、边：一个节点到另一个节点之间的连接

5、路径：连接节点和其后代的节点之间的节点和边的序列

6、节点的层数：从根结点到该节点的所有节点个数

7、 节点的深度：从根节点到该节点边的个数

8、节点的高度：节点的高度是该节点和某个叶子之间存在的最长路径上的边的个数。

9、树的高度：根节点的高度

 二、二叉树的定义

二叉树就是每个节点最多有两个子节点的树。两个子节点分别叫左子节点和右子节点（二叉树并不要求每个节点都有两个子节点）。

图中一为二叉树，二为完美二叉树也叫满二叉树，三为完全二叉树（去掉红色的节点）

完美二叉树：叶子节点全在一层，除了叶子节点之外每个节点都有左右子节点

完全二叉树：从根节点到倒数第二层满足满二叉树，最后一层可以不完全填充，其叶子节点都靠左对齐。（图三去掉红色节点才是正确的完全二叉树）

可以用栈来理解完全二叉树，加入将图二的满二叉树所有节点由右到左从叶子节点开始入栈，那么每次执行出栈操作之后栈中保存的节点对应到图二上都是一个完全二叉树。图三就是执行了错误的出栈操作，所以不是完全二叉树

三、如何表示一个二叉树

1、链式存储法(就是双链表的一种变形，让双链表的前驱指针指向左子节点，后继指针指向右子节点。)

把前后换成左右就是一个链式存储的二叉树

  2、顺序存储法

我们用特定的方法来将二叉树数据存入数组中，那么只需要知道根节点的位置就能知道整个树.例如 如果节点存入数组中的位置为i（i>0）那么他的子节点存入数组中的位置为2*i，右子节点的位置为2*i+1.这样就可以将整颗二叉树存入数组中。这种方法有个问题如果存储的不是完美二叉树或完全二叉树。就会浪费一些存储空间。

四、二叉树的遍历

实际上二叉树的遍历是一个递归的过程

前序遍历的递推公式：

preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)

中序遍历的递推公式：

inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)

后序遍历的递推公式：

postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r

1、前序遍历：中左右

2、中序遍历：左中右

3、后序遍历：左右中

 五、二叉搜素树

1、结构：树中任意一个节点，左子树中的每个节点的值，都要小于这个节点的值，右子树节点的值都大于这个节点的值。

2、查找的操作：先取根节点如果，这个数鼻根几点大则在右子树查找，如果小则在左子树查找。

3、插入的操作：插入操作都插入到叶子节点上。开始的操作与查找类似，先比较大小然后确定左右子树。与节点比较大小小左，大右。如果想要插入的位置不为空，就再遍历相应的子树，查找插入位置。

4、二叉树的删除操作：删除操作有三种情况

1、如果要删除的节点没有子节点，我们只需直接将父节点中指向要删除节点的指针设置为空

2、如果要删除只有一个子节点的节点，我们只需更新父节点中的指向要删除节点的指针指向其子节点就可以了。

3、要删除的节点有两个子节点，找到该节点中左子树中的最小节点，把它替换到要删除的节点上。

  5、搜索树排序

中序遍历二叉搜索树可以有序的输出数据序列。时间复杂度为o(n)

6、重复数据的处理

二叉搜索树重复数据的两种处理方式

1、一个节点存储多个数据，用支持动态扩容的数据结构存储数据

2、放在右子树中当作，比该节点大的数据处理（这种方法，进行增删查等操作时，就需要进行些改变。例如查找时，查找到该节点后还需要对其右子树尽行查找）

7、时间复杂度：O(height)时间复杂度视高度而定。

平衡查找书的话其时间复杂度为O（logn）原理与跳表时间复杂度计算原理类似