交换二叉树的所有节点的左右子树算法（C语言）

二叉树最好使用递归的算法，假设二叉树节点定义如下：

typedef struct node{

int a;

node left;

node right;

};

可以定义交换左右子树的函数如下：

void changeleaf(node anode)

{

if(anode!=0)

{

node tnode=anode->left;

anode->left=anode->right;

anode->right=tnode;

changeleaf(anode->left);

changeleaf(anode->right);

}

};

性质

二叉树是一个有根树，并且每个节点最多有2个子节点。非空的二叉树，若树叶总数为 n0，分支度为2的总数为 n2，则 n0 = n2 + 1。

满二叉树与完全二叉树

二叉堆：非常适合用数组进行存储，对于数组中的元素 a[i]，其左子节点为 a[2i+1]，其右子节点为 a[2i + 2]，其父节点为 a[(i-1)/2]，其堆序性质为，每个节点的值都小于其左右子节点的值。二叉堆中最小的值就是根节点。

性质

性质

平衡树是对二叉查找树的 改进 。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升。平衡树是使得所有叶子的深度趋于平衡。

各种平衡树

注：AVL树得名于它的发明者 G M Adelson-Velsky 和 Evgenii Landis，他们在1962年的论文An algorithm for the organization of information中公开了这一数据结构。

注：鲁道夫·拜尔(德语：Rudolf Bayer，1939年5月7日－)，自1972年以来一直是慕尼黑工业大学信息技术系的名誉教授。他因发明数据结构而出名: B-树（与Edward M McCreight合作）和UB-树（与Volker Markl合作）以及 红黑树 。他是2001年美国计算机协会SIGMOD Edgar F Codd年度创意大奖得主。

在树的结构中，树的定义如下。

树（tree）是n（n>=0）个节点的有限集，当n=0时，称为空树。在任意一个非空树中，有如下特点：

1、有且仅有一个特定的称为根的节点。

2、当n>1时，其余节点可分为m(m>0)个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。

相关节点

树的最大层级树，被称为树的高度或深度。

树的每个节点最多有2个孩子节点。

树的一种特殊形式。树的每个节点 最多有2个孩子节点 。

二叉树的两个孩子节点，一个被称为 左孩子 ，一个被称为 右孩子 。这两个孩子节点的顺序是固定的。

二叉树有两种特殊形式：满二叉树、完全二叉树。

满二叉树 ：一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层接上。简言之，满二叉树的每一个分支都是满的。

完全二叉树 ：对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。

一棵树，若为满二叉树，那么一定是完全二叉树。反之，不一定。

在内存中存储 ：

为什么这么设计？可以更方便的定位孩子节点、父节点。

若父节点的下标是parent，那么左孩子节点下标是2 parent+1，右孩子节点下标是2 parent+2。

反之，若左孩子节点下标是leftChild,那么父节点下标是(leftChild - 1)/2。

稀疏二叉树，用数组表示会很浪费空间。

二叉树的应用：查找操作、维持相对顺序。

1、查找

二叉查找树在二叉树的基础上增加了以下几个条件：

如果左子树不为空，则左子树上所有节点的值均小于根节点的值；

如果右子树不为空，则右子树上所有节点的值均大于根节点的值；

左、右子树也都是二叉查找树。

对于一个节点分布相对均衡的二叉查找树来说，如果节点总数是n，那么搜索节点的 时间复杂度都是O(logn) ，和树的深度是一样的。

2、维持相对顺序（插入）

二叉查找树的特性保证了二叉树的有序性，因此还有另外一个名字：二叉排序树。

插入的过程中，可能会出现需要二叉树进行自平衡，例如下图的情况：

如图所示，不只是树的外观看起来怪异，查询节点的时间复杂度也退化成了O(n)。

二叉树的自平衡的方式有很多种，如红黑树、AVL树、树堆等。

二叉树的遍历：

从节点之间位置关系的角度：

前序遍历：输出顺序：根节点、左子树、右子树

中序遍历：输出顺序：左子树、根节点、右子树

后序遍历：输出顺序：左子树、右子树、根节点

层序遍历：按照从根节点到叶子节点的层级关系，一层一层横向遍历各个节点。

从更宏观的角度:

深度优先遍历(前、中、后序遍历，前中后是相对根节点)

广度优先遍历(层序遍历)

二叉堆：本质上是一种完全二叉树。

二叉堆本质上是一种完全二叉树，分为2个类型：

最大堆 ：任何一个父节点的值，都大于或等于它左、右孩子节点的值；

最小堆 ：任何一个父节点的值，都小于或等于它左、右孩子节点的值。

二叉堆的根节点，叫作 堆顶 。最大堆的堆顶是整个堆中最大元素，最小堆的堆顶是整个堆中最小元素。

二叉堆虽然是一个完全二叉树，但它的存储方式并不是链式存储，而是顺序存储，如下图所示：

假设父节点的下标是parent，那么它的左孩子的下标就是 2 parent + 1 ，右孩子的下标就是 2 parent + 2 。

二叉堆的3种操作（假设是最小堆）：

1、插入节点：时间复杂度O(logn)

插入节点是通过“上浮”操作完成的：当二叉堆插入节点时，插入位置是完全二叉树的最后一个位置，将该节点与它的父节点进行比较，如果该节点小于它的父节点，那么该与它的父节点交换位置，直到比较到堆顶位置。

2、删除节点：时间复杂度O(logn)

删除节点是通过“下沉”操作完成的：将要删除的节点看作是堆顶，只看该节点及它下面的部分。因为堆顶元素要进行删除，将最后一个节点元素替换堆顶元素，将替换后的元素与它的左、右子树进行比较，如果左、右孩子节点中最小的一个比该节点小，那么该节点“下沉”，直到叶子节点。

3、构建二叉堆：时间复杂度O(n)

构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆，本质就是让所有非叶子节点一次“下沉”。

优先队列不再遵循先入先出的原则，而是分为两种情况：

最大优先队列 ，无论入队顺序如何，都是当前最大的元素优先出队；

最小优先队列 ，无论入队顺序如何，都是当前最小的元素优先出队。

二叉堆节点的“上浮”和“下沉”的时间复杂度都是O(logn)，所以优先队列入队和出队的时间复杂度也是O(logn)。

https://blogcsdnnet/qq_28958301/article/details/91590545