【数据结构】树的基本内容总结

因为普通的树应用价值不大而且不用以表示，所以现在只讨论二叉树。

1.内存中的表示方法：

（1）数组。主要用来表示完全二叉树，这样对于寻找父节点和子节点很容易。某个节点i，它的父节点是i/2 取下整。左子节点是2i，右节点的2i+1.如果存在的话。

（2）链表。这个更常用一些吧。一个节点有三个域，data，leftChild，rightChild.当然了，为了便于寻找父节点方便，可以增加一个域，用于指向父节点的位置所在。

2二叉树的抽象数据结构：

*********************************************************************************

structure BinaryTree；

objects：节点的有限集合。

functions：

（1）BinTree Create() //创建一个树

（2）Boolean IsEmpty（bt） //是否是空

（3）BinTree MakeBT(btleft,item,btright)//生成一个树，左子树为btleft，右子树为btright，item作为跟节点

（4）BinTree Lchild(bt) //返回左子树或者NULL

（5）BinTree Rchild（bt）//返回右子树或者NULL

（6）element Data（bt）//返回根节点的数据

*********************************************************************************

3二叉树的若干性质。这个比较偏理论，基本不怎么用吧，先不写了

4二叉树的遍历

以前总是觉得这个有点难，发现也没有什么。顶多是非递归的要复杂一点，递归的很容易啊。

（1）中序遍历 前序遍历和后序遍历的递归版本。

********************************

中序遍历

void inorder（tree ptr）

{

if（ptr）

{

inorder（ptr->left）

visit（ptr->data）

inorder(ptr->right)

}

}

********************************

（2）使用栈的迭代的中序遍历参考P129的程序。很简单。

（3）层次遍历。也就是说广度优先搜索，使用队列实现。至于是循环队列还是其他队列，可以自己考虑。效果是：使树中的节点按照层次依次输出。

（4）其他操作：二叉树的复制，二叉树的判断相等。

复制是一个递归的实现过程。分配内存，然后左子树递归复制，右子树递归进行复制。

判断是否相等主要是先检查空树条件。然后递归的判断左右子树是否分别相等。如果有任何一个地方不同，即可返回False。程序结束。

5线索二叉树

在二叉树中，叶子节点基本都是指向空的，而我们如果把这些点都弄起来，发现共有n+1个空闲的指针。那么，就可以用这些空闲的指针来进行一些使用，从而方便我们的一些操作。在中序遍历中，主要是用这些指针来指向某个节点的前驱节点和后继节点。这样的话，我们就不用递归的进行遍历了，而是可以跟据这个线索，一步一步的完成遍历。为了便于区分某个节点的左右指针是指向了自己的孩子节点还是指向了自己的前驱和后继节点，需要对数据结构中的表示方法进行一些更改，以便区分。新的结构如下所示：

****************************

struct threadedTree

{

short int leftThread;

threadTree * leftChild;

char data;

short int rightThread;

threadTree * rightChild；

}

****************************

(1)向线索二叉树中插入新的节点。分为两类：插入左儿子和插入右儿子

插入右儿子：有个节点p，其右子树为空，想要插入节点child，步骤如下：

1把parent->rightThread 置为false

2把child的leftThread 和rightthread置为true

3把child的leftthread指向p

4把child的rightChild指向p的rightChild

5修改parten的rightChild，使他指向child

插入右儿子，有个节点p，它的右子树不为空，想要插入child节点：

插入后，child变成原来p节点的右子树。原来p节点的右子树成为新的child节点的右子树。另外需要对线索进行更改。因为原来parent节点的的后继节点的中序前驱节点变成了child。

但是上面两种空与非空的情况都可以用同一个程序进行统一的处理。程序就不在这里列出了。后者主要是比前者多一个找后续节点直到为空的语句，别的基本按照上面的五步走。

6 堆

（1）定义：最大堆就是跟节点为整个树的最大值的完全二叉树，对，是完全二叉树。

（2）为什么用堆？

因为与数组和链表相比，堆进行插入和删除的操作可能更方便一些。插入和 删除，堆的复杂度都是lgn，而数组和链表（不管是有序的还是无序的）基本一个复杂度是O1，另外一个复杂对是On的。

（3）最大堆的插入

可以用一个数组来表示这个最大堆。先将新的节点插入到末尾，然后只管树中的这个分支，领用i/2找到父节点，进行比较，然后换位，最终可以讲该id按插入到合适的位置。

（4）最大堆的删除操作

删除最顶的最大元素。保存在一个新的节点中，方便函数返回

将末尾的最小元素放到顶层，并从尾部删除该元素。

然后重建堆，比较跟节点和其孩子节点的大小（+1即右节点了），然后进行位置的交换。直到顶端的这个元素找到自己合适的位置了，即可跳出循环了。（在此期间，可将末尾那个东西保存在一个节点中，模拟将其放入到头节点中，然后parent从1开始算，child从2开始算。不断的进行迭代，注意，parent每次都换成下一个child的值，child每次都换成新的parent的child的值（即乘以2就可），注意，最后的迭代中，child的计数不能超过堆中数据的总个数）。

7二叉查找树

（1）二叉查找树特点：

可以为空

没有重复的元素

左子树一定小于根节点

右子树一定大于跟节点

（2）二叉查找树的查找

两种方式：递归和非递归。递归就是三句话。==返回根。< 递归查询左子树,>递归查询右子树。

非递归查询：就是不同按着树杈走。走到头即可知道是否找到。

（3）二叉查找树的插入

在插入之前，首先要在树中查找这个节点，看是否已经存在，如果已经存在，返回错我。如果没有存在，会指向一个树中的某个叶子节点。然后将新的节点插入到这个被指向的叶子节点的尾部就好了。

（4）二叉查找树的删除

分为三种情况讨论：1删除叶子节点，容易。2删除仅有单个子节点的，容易，令其子节点取代被删除的及诶单即可。3删除有两个儿子的节点，稍微麻烦。用左子树中的最大节点或者右子树中的最小节点代替这个节点，然后将这个节点删除。然后，如果用左中的最大和右中的最小进行替代时，也需要删除这个节点，此时就需要再继续对该节点子节点进行调整。但是可以证明，一个树中的最大节点或者最小节点一定是度为0或者1的节点。

8选择树

对多路进行归并的排序时，可以使用这个。如果不用，多路归并的复杂度应该是n*n，而如果用了这个，复杂度应该是n*logn。能够有一定的提高。

总体的思想就是：先从各路归并K中选出分别一个元素，从而形成k个节点，然后两两进行锦标赛，得到k/2个优胜的节点，迭代进行锦标赛，最终得到了一个节点，就是将要在归并中选择的节点。然后，从该节点的出生地队列中再拿下一个树，重建选择树，重建过程和ilogn。这个是优胜树，也有失败树的，我不是太明白这个。

二叉树的基本内容就包括上面这些内容。深入的内容，应该是在以后的章节中继续深入探讨。这个部分就到此为止。

下面再简单说一下森林，这个也不太常用。森林主要是可以用来表示集合。其中，表示方式有所改变，之前是父指子，现在是子指父，对于查找操作比较方便。集合中主要涉及到并查操作。这个，等以后用到的时候再看吧。