ZAM'S BLOG 2.3.3

咕咕咕了这么久，终于有空好好学学树与二叉树的数据结构了。

Update 2020.04.16 :过去了半年，依旧还没有完成…… 咕咕咕，咕咕咕，咕叽咕叽咕

树的基本概念

下面是一些关于树的基本术语：

术语 中文 描述
Root 根节点 The top node in a tree.
Child 子节点 A node directly connected to another node when moving away from the Root.
Leaf 叶子节点 A node with no children
Edge 边 The connection between one node and another.
Path 路径 A sequence of nodes and edges connecting a node with a descendant.
Height 节点高度 The height of a node is the number of edges on the longest path between that node and a leaf.
Level 层级 The level of a node is defined by 1 + (the number of connections between the node and the root).
Depth 深度 The depth of a node is the number of edges from the tree’s root node to the node.
Degree 度 The number of subtrees of a node.

下面通过几个图解释树的术语

Edge、Root、Leaf
Path
Height

需要注意的是叶子节点的高度为 0，如果树只有一个节点，那么这个节点的高也是 0

Depth

需要注意的是根节点的深度（Depth）是 0.

从 Height 和 Depth 的对比，它们的方向刚好是相反的。
对于 Height 和 Depth 不用死记，我们可以把树倒过来看，也就是我们现实生活当中的树，求某个节点的 Height 那肯定是从根部往上的方向；如果是求某个节点的深度，方向肯定是向下的。

Level

节点的 Level 是从 1 开始的，Level = Depth+1，根节点的 Level=1
也有很多书籍上 Level 是从 0 开始的，这样的话 Level 就等于 Depth，根节点的 Level=0

reference:数据结构与算法（七）树和二叉树

二叉树的基本概念

二叉树是一个每个最结最多只能有两个分支的树，左边的分支称之为左子树，右边的分支称之为右子树。

也就是说二叉树节点的度最大也就是 2，而普通的树，节点的度是没有限制的。

二叉树的分类

完美/满二叉树

完美二叉树也有地方称之为满二叉树。完美二叉树满足两个特性：

  • 所有的几点都包含两个子节点
  • 所有的叶子节点的 Height 或者 Level 都相等

例如下面就是一个完美二叉树：
完美二叉树

完全二叉树

完全二叉树是 除了最后一层都是满的（都有两个子节点），并且最后一层的节点是从左往右排列的。

完全二叉树，通俗点说就是节点按层从左往右排列。如果最后一层排满了就是完美二叉树，没有满则是完全二叉树。
所以完美二叉树一定是完全二叉树，完全二叉树不一定是完美二叉树。

一个完全二叉树可以高效的使用数组来表示。

例如下面就是一个完全二叉树：
完全二叉树

完满二叉树

完满二叉树就简单了，就是每个节点都有两个子节点。也就是说它比完美二叉树少了一个条件。

例如下面就是一个完满二叉树：
完满二叉树

学习并实现树的相关操作

在这里，我们定义一个如下的二叉树数据结构：

1
2
3
4
5
6
7
typedef char BTDataType;
typedef struct BTNode
{
	struct BTNode * _pLeft;
	struct BTNode * _pRight;
	BTDataType _data;
}BTNode;

遍历二叉树

从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：

⑴ 访问结点本身（N）

⑵ 遍历该结点的左子树（L）

⑶ 遍历该结点的右子树（R）

以上三种操作有六种执行次序：

NLR、LNR、LRN、NRL、RNL、RLN。

注意：

前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。

因此，我们就可以根据访问结点操作发生位置命名：

  • NLR：前序遍历(Preorder Traversal 亦称（先序遍历）） ——访问根结点的操作发生在遍历其左右子树之前。
  • LNR：中序遍历(Inorder Traversal) ——访问根结点的操作发生在遍历其左右子树之中（间）。
  • LRN：后序遍历(Postorder Traversal) ——访问根结点的操作发生在遍历其左右子树之后。
    注意：

由于被访问的结点必是某子树的根，所以 N(Node）、L(Left subtree）和 R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR 和 LRN 分别又称为先根遍历、中根遍历和后根遍历。

先序遍历

若二叉树非空，则依次执行如下操作：
⑴ 访问根结点；
⑵ 遍历左子树；
⑶ 遍历右子树。
递归算法实现：

1
2
3
4
5
6
7
8
9
void PreOrder(BTNode* pRoot)
{
	if (pRoot)
	{
		printf("%c ", pRoot->_data);
		PreOrder(pRoot->_pLeft);
		PreOrder(pRoot->_pRight);
	}
}

中序遍历

若二叉树非空，则依次执行如下操作：
⑴ 遍历左子树；
⑵ 访问根结点；
⑶ 遍历右子树。
递归算法实现：

1
2
3
4
5
6
7
8
9
void InOrder(BTNode* pRoot)
{
	if (pRoot)
	{
		InOrder(pRoot->_pLeft);
		printf("%c ", pRoot->_data);
		InOrder(pRoot->_pRight);
	}
}

后序遍历

若二叉树非空，则依次执行如下操作：
⑴ 遍历左子树；
⑵ 遍历右子树；
⑶ 访问根结点。
递归算法实现：

1
2
3
4
5
6
7
8
9
void PostOrder(BTNode* pRoot)
{
	if (pRoot)
	{
		PostOrder(pRoot->_pLeft);
		PostOrder(pRoot->_pRight);
		printf("%c ", pRoot->_data);
	}
}

层序遍历

除了以上三种以根节点相对于它的左右孩子的访问顺序定义的遍历算法之外，二叉树还有一种遍历方式，就是层序遍历。
递归算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void LevelOrder(BTNode* pRoot)
{
	if(pRoot == NULL)
	{
		return NULL;
	}
	Queue q;
	QueueInit(&q);
	QueuePush(&q, pRoot);
	while(!QueueEmpty(&q))
	{
		pRoot = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", pRoot->_data);
		if(pRoot->_pLeft!=NULL)
			QueuePush(&q, pRoot->_pLeft);
		if(pRoot->_pRight!=NULL)
			QueuePush(&q, pRoot->_pRight);
	}
	QueueDestroy(&q);
}

reference:二叉树的前中后和层序遍历详细图解(递归和非递归写法)

新建一个树节点

C 语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
BTNode* BuyNewNode1(BTDataType data)
{
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL)
	{
		assert(0);
		return NULL;
	}
	root->_data = data;
	root->_pLeft = NULL;
	root->_pRight = NULL;
	return root;
}

创建二叉树

C 语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
BTNode * _CreateBinTree(BTDataType * array, int size, int* index,BTDataType invalid)
{
	BTNode* pRoot = NULL;
	if ((*index) < size && invalid != array[*index] )
	{
		pRoot = BuyNewNode1(array[*index]);

		//创建左子树；
		++(*index);
		pRoot->_pLeft = _CreateBinTree(array, size, index,invalid);

		//创建右子树
		++(*index);
		pRoot->_pRight = _CreateBinTree(array, size, index,invalid);
	}
	return pRoot;
}

BTNode* CreateBinTree(BTDataType* array, int size, BTDataType invalid) {
	int index = 0;
	return  _CreateBinTree(array, size, &index, invalid);
}

拷贝二叉树

C 语言实现

1
2
3
4
5
6
7
8
9
10
BTNode* CopyBinTree(BTNode* pRoot)
{
	BTNode* newpRoot = NULL;
	if (pRoot == NULL)
		return NULL;
	newpRoot = BuyBinTreeNode(pRoot->_data);
	newpRoot->_pLeft = CopyBinTree(pRoot->_pLeft);
	newpRoot->_pRight = CopyBinTree(pRoot->_pRight);
	return newpRoot;
}

删除二叉树

C 语言递归实现

1
2
3
4
5
6
7
8
9
10
11
12
void DestroyBinTree(BTNode** pRoot)
{
	if (*pRoot)
	{
		//递归删除左子树
		DestroyBinTree(&((*pRoot)->_pLeft));
		//递归删除右子树
		DestroyBinTree(&((*pRoot)->_pRight));
		free(*pRoot);
		*pRoot = NULL;
	}
}

获取二叉树全部的节点个数

C 语言递归实现

1
2
3
4
5
6
7
int GetBinTreeSize(BTNode* pRoot)
{
	if (pRoot)
		return GetBinTreeSize(pRoot->_pLeft) + GetBinTreeSize(pRoot->_pRight) + 1;
	else
		return 0;
}

获取二叉树中叶子节点个数

C 语言递归实现

1
2
3
4
5
6
7
8
9
10
11
12
int GetLeafCount(BTNode* pRoot)
{
	if (pRoot == NULL)
	{
		return 0;
	}
	if (pRoot->_pLeft == NULL && pRoot->_pRight == NULL)
	{
		return 1;
	}
	return GetLeafCount(pRoot->_pLeft) + GetLeafCount(pRoot->_pRight);
}

获取二叉树深度(高度)

C 语言递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int GetBinTreeHeight(BTNode* pRoot)
{
	if (pRoot == NULL)
	{
		return 0;
	}
	int height = 1;
	while (pRoot->_pLeft || pRoot->_pRight)
	{
		height++;
		if (pRoot->_pLeft)
			pRoot = pRoot->_pLeft;

		if(pRoot->_pRight)
			pRoot = pRoot->_pRight;
	}
	return height;
}

在二叉树中搜索值为 X 的节点

C 语言递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if(root->_data == x)
	{
		return root;
	}
	BTNode* tmp = NULL;
	//递归从左子树往下找
	if (tmp = BinaryTreeFind(root->_pLeft, x))
	{
		return tmp;
	}
	//左子树从右子树找，右子树找到直接返回
	return BinaryTreeFind(root->_pRight, x);

}

镜像翻转二叉树

C 语言递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void BinaryTreeSwap(BTNode** pleft, BTNode ** pright)
{
	BTNode * tmpNode = *pleft;
	*pleft = *pright;
	*pright = tmpNode;
}

void Mirror(BTNode* pRoot)
{
	if (pRoot == NULL)
	{
		return NULL;
	}
	BinaryTreeSwap(pRoot->_pLeft, pRoot->_pRight);
	Mirror(pRoot->_pLeft);
	Mirror(pRoot->_pRight);
}

学习并实现树的相关结构

线索二叉树

Reference:线索二叉树的创建及遍历(C 语言实现)
在使用二叉链表的普通二叉树中，对于 n 个结点的二叉树，在二叉链存储结构中有 n+1 个空链域。这些空链域放着不用，是对空间的浪费。
如果算法中多次涉及到对二叉树的遍历，普通的二叉树就需要使用栈结构做重复性的操作。
因此，如果使用二叉树中空闲的内存空间记录某些结点的前趋和后继元素的位置（不是全部）。这样在算法后期需要遍历二叉树时，就可以利用保存的结点信息，提高了遍历的效率。
使用这种方法构建的二叉树，即为“线索二叉树”。

线索二叉树中，如果结点有左子树，则 lchild 指针域指向左孩子，否则 lchild 指针域指向该结点的直接前趋；同样，如果结点有右子树，则 rchild 指针域指向右孩子，否则 rchild 指针域指向该结点的直接后继。
为了避免指针域指向的结点的意义混淆，需要改变结点本身的结构，增加两个标志域，如下图所示
线索二叉树中的结点结构

其中，LTag 和 RTag 为标志域。实际上就是两个布尔类型的变量：

  • LTag 值为 0 时，表示 lchild 指针域指向的是该结点的左孩子；为 1 时，表示指向的是该结点的直接前趋结点；
  • RTag 值为 0 时，表示 rchild 指针域指向的是该结点的右孩子；为 1 时，表示指向的是该结点的直接后继结点。
    结点结构代码实现(C):
1
2
3
4
5
6
7
8
9
10
11
12
13
#define TElemType int//宏定义，结点中数据域的类型
//枚举，Link为0，Thread为1
typedef enum PointerTag{
    Link,
    Thread
}PointerTag;
//结点结构构造
typedef struct BiThrNode{
    TElemType data;//数据域
    struct BiThrNode* lchild,*rchild;//左孩子，右孩子指针域

    PointerTag Ltag,Rtag;//标志域，枚举类型
}BiThrNode,*BiThrTree;

表示二叉树时，像以上结点结构构成的二叉链表，被称为线索链表；构建的二叉树称为线索二叉树。

将普通二叉树转化为线索二叉树

大致思路：在遍历过程中，如果当前结点没有左孩子，需要将该结点的 lchild 指针指向遍历过程中的前一个结点，所以在遍历过程中，设置一个指针（名为 pre ），时刻指向当前访问结点的前一个结点。rchlid 也同样处理
C 语言实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//中序对二叉树进行线索化
void InThreading(BiThrTree p){
    //如果当前结点存在
    if (p) {
        InThreading(p->lchild);//递归当前结点的左子树，进行线索化
        //如果当前结点没有左孩子，左标志位设为1，左指针域指向上一结点 pre
        if (!p->lchild) {
            p->Ltag=Thread;
            p->lchild=pre;
        }
        //如果 pre 没有右孩子，右标志位设为 1，右指针域指向当前结点。
        if (!pre->rchild) {
            pre->Rtag=Thread;
            pre->rchild=p;
        }
        pre=p;//线索化完左子树后，让pre指针指向当前结点
        InThreading(p->rchild);//递归右子树进行线索化
    }
}

线索二叉树的遍历

下图是一个按照中序遍历建立的线索二叉树。其中，实线表示指针，指向的是左孩子或者右孩子。虚线表示线索，指向的是该结点的直接前趋或者直接后继。

使用线索二叉树时，会经常遇到一个问题，如图 3 中，结点 b 的直接后继直接通过指针域获得，为结点 _ ；而由于结点 _ 的度为 2 ，无法利用指针域指向后继结点，整个链表断掉了。当在遍历过程，遇到这种问题是解决的办法就是：寻找先序、中序、后序遍历的规律，找到下一个结点。

在先序遍历过程中，如果结点因为有右孩子导致无法找到其后继结点，如果结点有左孩子，则后继结点是其左孩子；否则，就一定是右孩子。拿图 3 举例，结点 + 的后继结点是其左孩子结点 a ，如果结点 a 不存在的话，就是结点 * 。

在中序遍历过程中，结点的后继是遍历其右子树时访问的第一个结点，也就是右子树中位于最左下的结点。例如图 3 中结点 * ，后继结点为结点 c ，是其右子树中位于最左边的结点。反之，结点的前趋是左子树最后访问的那个结点。

后序遍历中找后继结点需要分为 3 种情况：
如果该结点是二叉树的根，后继结点为空；
如果该结点是父结点的右孩子（或者是左孩子，但是父结点没有右孩子），后继结点是父结点；
如果该结点是父结点的左孩子，且父结点有右子树，后继结点为父结点的右子树在后序遍历列出的第一个结点。
使用后序遍历建立的线索二叉树，在真正使用过程中遇到链表的断点时，需要访问父结点，所以在初步建立二叉树时，宜采用三叉链表做存储结构。
线索二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//中序遍历线索二叉树
void InOrderThraverse_Thr(BiThrTree p)
{
    while(p)
    {
        //一直找左孩子，最后一个为中序序列中排第一的
        while(p->Ltag == Link){
            p = p->lchild;
        }
        printf("%c ", p->data);  //操作结点数据
        //当结点右标志位为1时，直接找到其后继结点
        while(p->Rtag == Thread && p->rchild !=NULL){
            p = p->rchild;
            printf("%c ", p->data);
        }
        //否则，按照中序遍历的规律，找其右子树中最左下的结点，也就是继续循环遍历
        p = p->rchild;
    }
}

平衡二叉树（AVL Tree）

平衡二叉树的定义

平衡二叉树指的是要么它本身是一个空树，要么它是一个左子树和右子树的深度之差的绝对值不大于 1，并且保证左右子树都是平衡树，下图就是一个平衡二叉树。从图中我们可以看出，一个结点的高度位 1 则表明为其叶子结点到父结点的高度，整颗树的高度取决于最深叶子结点到根结点的距离。
平衡二叉树
由于 AVL 树操作中有许多的操作需要向上进行，所以数据结构应这样设计：

1
2
3
4
5
6
7
8
9
10
typedef struct treeNode{
	char key;
	int val;
	//平衡因子，-1，0，1为合理值
	int balanceFactor;
	struct treeNode *left;
	struct treeNode *right;
    //父节点，方便向上的操作进行
	struct treeNode *Parent;
}AVLTree,*PAVLTree;

平衡二叉树的操作

AVL 树的查找操作和普通的二叉树的查找基本一致，但是插入和删除操作有所不同，因为插入和删除会减少树的结点并且改变树的结构，这个时候为了使树始终保持平衡状态我们需要对树进行重构使其始终保持平衡状态，一般这个操作叫做旋转操作（rotation），旋转分为左旋转和右旋转等。我们需要使用旋转操作使得在插入和删除操作之后使二叉平衡树在插入和删除某结点之后依然保持平衡。

旋转操作

旋转的操作主要有左旋转和右旋转。旋转操作的基本原理都一样，最终目的就是为了让二叉平衡树在被操作之后再次达到平衡。

左旋转

左旋转
在上图所表示的左旋转操作中，我们假设的是 x < y < z，因为树不平衡了，我们执行左旋转，将 x 及其左子树进行左旋转，并且将原本 y 的左子树变为 x 的右子树，这里需要注意的两点，

  • ① 就是我们需要寻找到三个点，这三个点的大小是有排序的，如这此段开头所说道的 xyz 的关系，将中间那个值作为新的中心结点，然后再进行旋转操作。
  • ② 就是一定要确保所有的左右子树遵循二叉树的定义要求，既左子树一定要永远都是小于其父结点的，而右子树始终大于父结点的。
    C 语言实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
PAVLTree leftRotate(PAVLTree Node)
{
	PAVLTree Temp = Node->right;
	Node->right = Temp->left;
	Temp->left = Node;
	Temp->Parent = Node->Parent;
	if(Temp->left)
		Temp->left->Parent = Temp;
	if(Temp->right)
		Temp->right->Parent = Temp;
	if(Node->left)
		Node->left->Parent = Node;
	if(Node->right)
		Node->right->Parent = Node;
	return Temp;
}
右旋转

右旋转
上图所述的三个节点的关系为 z < x < y，因此根据左旋转所描述的我们可以知道 x 应该作为中心结点也就是父结点，然后这里需要进行两次旋转才能使二叉树最终处于平衡，首先是先对 z 进行左旋转，将 z 变为 x 的左子树，然后再对 y 进行右旋转，在这个过程中，x 的左子树变为 z 的右子树，而右子树则成为了 y 的左子树。
C 语言实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
PAVLTree rightRotate(PAVLTree Node)
{
		PAVLTree Temp = Node->left;
	Node->left = Temp->right;
	Temp->right = Node;
	Temp->Parent = Node->Parent;
	if(Temp->left)
		Temp->left->Parent = Temp;
	if(Temp->right)
		Temp->right->Parent = Temp;
	if(Node->left)
		Node->left->Parent = Node;
	if(Node->right)
		Node->right->Parent = Node;
	return Temp;
}
自旋转

在实现了左旋和右旋操作之后，我们就可以编写一个自平衡函数，来在进行插入和删除操作后自动使二叉树重新达到平衡。
在编写自旋转函数之前，我们需要明白我们在插入或者删除的时候可能导致的树的不平衡的所有情况。
四种可能情况
情况 1 和 4 是最简单的，我们只需要对结点 Z 进行一个左右的旋转即可，旋转和红黑树的旋转一样。目的是降低子树的高度差。
情况 2 和情况 3 需要先对 y 进行左或者右旋转，变成情况 1 和 4，然后再照着情况 1，和 4 处理。
其实每次插入删除的时候引起的不平衡的结点都是插入、删除的结点的父节点，不肯是其父节点的兄弟结点之类，而且我们总是通过不平衡结点加上往下的两个结点，来判断出事情况几。往下的结点怎么选取呢？
选取的规定就是，看刚插入或者删除的结点是在不平衡结点的左子树还是右子树，加入在左子树，那么继续判断刚插入或者删除的结点在该左子树的左子树还是右子树，只需要这么两步就可以判断出情况。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
//树的权值搜索函数

PAVLTree searchKey(PAVLTree t,ElemType key)
{
     PAVLTree p=t;
     while(p)
     {
          if(p->key==key)
               return p;
          else if(p->key<key)
               p=p->rchild;
          else
               p=p->lchild;
     }
     return p;
}
//树的自平衡函数,传入的参数是新插入的节点
PAVLTree AVLTreeBalance(PAVLTree *Node)
{
	if(!(*Node))
		return NULL;
	PAVLTree *BFNode;
	PAVLTree Temp = *Node;
	PAVLTree Parent;
	//0--left,1--right
	int LeftOrRight = -1;
	PAVLTree find = (*Node);
	BFNode = Node;
    //查找到不平衡的结点
	while(find)
	{
		if(find->balanceFactor == -2 || find->balanceFactor == 2)
			break;
		find = find->Parent;
	}
	//当前树平衡
	if(!find)
	{
		while(Temp->Parent)
			Temp = Temp->Parent;
		return Temp;
	}
	(*BFNode) = find;
	//如果存在父节点
	if((*BFNode)->Parent)
	{
		Parent = (*BFNode)->Parent;
		if(Parent->left == (*BFNode))
			LeftOrRight = 0;
		else
			LeftOrRight = 1;
	}
	else
		Parent = NULL;
	//辅助判断是哪种情况的变量
	int Second,Third;
	Second = searchKey((*BFNode),Temp->key,&find);
	if(Second == 0)
		Third = searchKey((*BFNode)->left,Temp->key,&find);
	else
		Third = searchKey((*BFNode)->right,Temp->key,&find);
	//情况一，左左左
	if(Second == 0 && Third == 0)
		(*BFNode) = rightRotate((*BFNode));
	//情况二，右右右
	else if(Second == 1 && Third == 1)
		(*BFNode) = leftRotate((*BFNode));
	//情况三，左左右
	else if(Second == 0 && Third == 1)
	{
		(*BFNode)->left = leftRotate((*BFNode)->left);
		(*BFNode) = rightRotate((*BFNode));
	}
	//情况四，右右左
	else
	{
		(*BFNode)->right = rightRotate((*BFNode)->right);
		(*BFNode) = leftRotate((*BFNode));
	}
	if(LeftOrRight != -1)
	{
		if(LeftOrRight == 0)
			Parent->left = (*BFNode);
		else
			Parent->right = (*BFNode);
	}
    //返回根节点
	while(Temp->Parent)
		Temp = Temp->Parent;
	return Temp;
}

一些辅助函数

其它的一些辅助函数与普通的二叉树没什么不同。

获得 AVL 树的深度

C 语言实现：

1
2
3
4
5
6
7
8
9
//获得树的深度
int GetDeepth(PAVLTree Node)
{
	if(!Node)
		return 0;
	int left = GetDeepth(Node->left);
	int right = GetDeepth(Node->right);
	return (left > right ? (left+1) : (right+1));
}
重新计算树的平衡因子

//重新计算树的平衡因子，但是只会回溯插入节点的沿途父节点,始终以左节点层数减去右节点层数
C 语言实现：

1
2
3
4
5
6
7
8
void CalculateBF(PAVLTree Node)
{
	//根节点的父节点就终止
	if(!Node)
		return;
	Node->balanceFactor = GetDeepth(Node->left)-GetDeepth(Node->right);
	CalculateBF(Node->Parent);
}

插入操作

平衡二叉树的插入操作与普通二叉查找树的操作一样，新插入的节点都发生在叶子结点，唯一不同的就如上述所说，新插入的结点致使树的结构发生改变而导致不平衡，此时需要进行旋转以达到平衡。
平衡二叉树.png
插入新的节点Key(40)
这时我们会发现此时的二叉树已经不平衡，这时我们需要寻找到树里面导致树不平衡的三个点，进行相应的操作，具体有以下两步：

  • ① 先对结点 39 以结点 42 为父结点进行左旋转，此时节点 40 变成了 39 的右结点，而 33，39，40 一起成为了结点 42 的左子树。
  • ② 对结点 53 进行右旋转，将其变成节点 42 的右子树，结点 55 依然为结点 53 的右子树。由此便完成了整棵树的重构并让新的树保持平衡。重构之后的树如下图所示：
    重构之后得到的插入树.png
    有了上边的自平衡函数，那么 AVL 树的插入和删除操作就会变得非常简单。
    C 语言实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//插入操作
PAVLTree insertKey(PAVLTree *root,char key,int val)
{
	//为空，表示应该插入的位置
	if(!(*root))
	{
		(*root) = (PAVLTree)malloc(sizeof(AVLTree));
		(*root)->key = key;
		//(*root)->Parent = (*root);
		(*root)->val = val;
		(*root)->left = (*root)->right = NULL;
		//Balance factor and primary value is 0
		(*root)->balanceFactor = 0;
		return (*root);
	}
	//如果已经存在那么修正值就行:
	else if((*root)->key == key)
	{
		(*root)->key = key;
		return (*root);
	}
	//在左子树
	else if((*root)->key > key)
		insertKey(&(*root)->left,key,val)->Parent = (*root);
	//在右子树
	else if((*root)->key < key)
		insertKey(&(*root)->right,key,val)->Parent = (*root);
	CalculateBF(*root);
	return (*root);
}

删除操作

假设在插入的基础上删除结点 22，那么此时我们从节点 19 开始遍历找到第一个导致不平衡的结点为 25 并且具有最大高度值的结点，之后往右子树进行便利寻找到第二个具有最大高度值的结点，此结点为 42（下图标注了红色边框的结点）。
过程如下图所示：
删除之后进行重构流程图.png
那么删除的策略就是：

  • 1.叶子结点那么直接删除。
  • 2.不是叶子结点，但是只有一个儿子结点，那么删除该节点，用其儿子结点顶替
  • 3.不是叶子结点，但是有两个儿子结点，那么查找该树的中序遍历情况下，要删除节点的下一个结点来顶替，（其实就是右子树的最小值结点）
    C 语言实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//删除函数
PAVLTree deleteKey(PAVLTree *root,char key)
{
	PAVLTree DeleteNode = (PAVLTree)malloc(sizeof(AVLTree));
	//查找到，那么删除
	if((*root)->key == key)
	{
		//为了调试少写一点
		DeleteNode->key = (*root)->key;
		DeleteNode->val = (*root)->val;
		//叶子节点，直接删除
		if(!(*root)->left && !(*root)->right)
			(*root) = NULL;
		else if(!(*root)->left)
			(*root) = (*root)->right;
		else if(!(*root)->right)
			(*root) = (*root)->left;
		//最复杂的情况需要寻找中序遍历的下一个点来顶替（右子树的最小结点）
		else
		{
			PAVLTree Temp = deleteMin(&(*root)->right);
			(*root)->key = Temp->key;
			(*root)->val = Temp->val;
		}
	}
	else if((*root)->key > key)
		DeleteNode = deleteKey(&(*root)->left,key);
	else
		DeleteNode = deleteKey(&(*root)->right,key);
	CalculateBF(*root);
	AVLTreeBalance(root);
	return DeleteNode;
}

Reference：AVL（自平衡二叉树）树的实现（C 语言）

哈夫曼树

赫夫曼树，别名“哈夫曼树”、“最优树”以及“最优二叉树”。学习哈夫曼树之前，首先要了解几个名词。
哈夫曼树

哈夫曼树相关的几个名词

  • 路径：
    在一棵树中，一个结点到另一个结点之间的通路，称为路径。上图中，从根结点到结点 a 之间的通路就是一条路径。
  • 路径长度：
    在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为 1 层，那么从根结点到第 i 层结点的路径长度为 i - 1 。上图中从根结点到结点 c 的路径长度为 3。
  • 节点的权：
    给每一个结点赋予一个新的数值，被称为这个结点的权。例如，上图中结点 a 的权为 7，结点 b 的权为 5。
  • 结点的带权路径长度：
    指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如，上图中结点 b 的带权路径长度为 2 _ 5 = 10 。
    树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。例如上图中所示的这颗树的带权路径长度为：WPL = 7 _ 1 + 5 _ 2 + 2 _ 3 + 4 * 3

哈夫曼树的定义

当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。

在构建哈弗曼树时，要使树的带权路径长度最小，只需要遵循一个原则，那就是：权重越大的结点离树根越近。在上图中，因为结点 a 的权值最大，所以理应直接作为根结点的孩子结点。

构建哈夫曼树的过程

对于给定的有各自权值的 n 个结点，构建哈夫曼树有一个行之有效的办法：
在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；
重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。
哈夫曼树的构建过程
上图中，（A）给定了四个结点 a，b，c，d，权值分别为 7，5，2，4；第一步如（B）所示，找出现有权值中最小的两个，2 和 4 ，相应的结点 c 和 d 构建一个新的二叉树，树根的权值为 2 + 4 = 6，同时将原有权值中的 2 和 4 删掉，将新的权值 6 加入；进入（C），重复之前的步骤。直到（D）中，所有的结点构建成了一个全新的二叉树，这就是哈夫曼树。

哈夫曼树中的节点结构

构建哈夫曼树时，首先需要确定树中结点的构成。由于哈夫曼树的构建是从叶子结点开始，不断地构建新的父结点，直至树根，所以结点中应包含指向父结点的指针。但是在使用哈夫曼树时是从树根开始，根据需求遍历树中的结点，因此每个结点需要有指向其左孩子和右孩子的指针。

1
2
3
4
5
//哈夫曼树结点结构
typedef struct {
    int weight;//结点权重
    int parent, left, right;//父结点、左孩子、右孩子在数组中的位置下标
}HTNode, *HuffmanTree;

构建哈夫曼树的算法实现

构建哈夫曼树时，需要每次根据各个结点的权重值，筛选出其中值最小的两个结点，然后构建二叉树。

查找权重值最小的两个结点的思想是：从树组起始位置开始，首先找到两个无父结点的结点（说明还未使用其构建成树），然后和后续无父结点的结点依次做比较，有两种情况需要考虑：

  • 如果比两个结点中较小的那个还小，就保留这个结点，删除原来较大的结点；
  • 如果介于两个结点权重值之间，替换原来较大的结点；
    C 语言的实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//HT数组中存放的哈夫曼树，end表示HT数组中存放结点的最终位置，s1和s2传递的是HT数组中权重值最小的两个结点在数组中的位置
void Select(HuffmanTree HT, int end, int *s1, int *s2)
{
    int min1, min2;
    //遍历数组初始下标为 1
    int i = 1;
    //找到还没构建树的结点
    while(HT[i].parent != 0 && i <= end){
        i++;
    }
    min1 = HT[i].weight;
    *s1 = i;

    i++;
    while(HT[i].parent != 0 && i <= end){
        i++;
    }
    //对找到的两个结点比较大小，min2为大的，min1为小的
    if(HT[i].weight < min1){
        min2 = min1;
        *s2 = *s1;
        min1 = HT[i].weight;
        *s1 = i;
    }else{
        min2 = HT[i].weight;
        *s2 = i;
    }
    //两个结点和后续的所有未构建成树的结点做比较
    for(int j=i+1; j <= end; j++)
    {
        //如果有父结点，直接跳过，进行下一个
        if(HT[j].parent != 0){
            continue;
        }
        //如果比最小的还小，将min2=min1，min1赋值新的结点的下标
        if(HT[j].weight < min1){
            min2 = min1;
            min1 = HT[j].weight;
            *s2 = *s1;
            *s1 = j;
        }
        //如果介于两者之间，min2赋值为新的结点的位置下标
        else if(HT[j].weight >= min1 && HT[j].weight < min2){
            min2 = HT[j].weight;
            *s2 = j;
        }
    }
}

s1 和 s2 传入的是实参的地址，所以函数运行完成后，实参中存放的自然就是哈夫曼树中权重值最小的两个结点在数组中的位置。
构建哈弗曼树的代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//HT为地址传递的存储哈夫曼树的数组，w为存储结点权重值的数组，n为结点个数
void CreateHuffmanTree(HuffmanTree *HT, int *w, int n)
{
    if(n<=1) return; // 如果只有一个编码就相当于0
    int m = 2*n-1; // 哈夫曼树总节点数，n就是叶子结点
    *HT = (HuffmanTree) malloc((m+1) * sizeof(HTNode)); // 0号位置不用
    HuffmanTree p = *HT;
    // 初始化哈夫曼树中的所有结点
    for(int i = 1; i <= n; i++)
    {
        (p+i)->weight = *(w+i-1);
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
    }
    //从树组的下标 n+1 开始初始化哈夫曼树中除叶子结点外的结点
    for(int i = n+1; i <= m; i++)
    {
        (p+i)->weight = 0;
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
    }
    //构建哈夫曼树
    for(int i = n+1; i <= m; i++)
    {
        int s1, s2;
        Select(*HT, i-1, &s1, &s2);
        (*HT)[s1].parent = (*HT)[s2].parent = i;
        (*HT)[i].left = s1;
        (*HT)[i].right = s2;
        (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
    }
}

注意，如果使用此程序，对权重值分别为 2、8、7、6、5 的节点构建哈夫曼树，最终效果如图 4(A) 所示。但其实，图 4(B) 中显示的哈夫曼树也满足条件，这两棵树的带权路径长度相同。
图 4 两种哈夫曼树
之所以使用此程序构建的哈夫曼树，是图 4(A) 而不是 4(B)，是因为在构建哈夫曼树时，结点 2 和结点 5 构建的新的结点 7 存储在动态树组中位置，比权重值为 7 节点的存储位置还靠后，所以，在程序继续选择两个权值最小的结点时，直接选择了的叶子结点 6 和 7 。
Reference:哈夫曼树（赫夫曼树、最优树）详解

字典树

字典树的定义

字典树，顾名思义，就是用树的结构去存储单词。比如，我要存储单词 ant 和 apple，就可以采取下图的多叉树结构去实现，其中可以看到，他们公用 A 节点，看是上去似乎节省了空间（实际上并没有，下面会解释），和形成了有序的分组。
字典树图解
假设我们采用的是传统的方法，也就是用一个数组，把单词存进去。那么我们可以比较以下这两个方法的时间复杂度
假设每个单词平均有 M 个字母，一共有 N 个单词。
|操作|传统算法|字典树|
|—|—|—|
|插入|O(N)|O(M)|
|查找|O(N)|O(M)|
|删除|O(N)|O(M)|
显然，当需要存储的数据量越庞大或者数据的操作越频繁，字典树的优势越明显，它的时间复杂度只与单词的长度有关。这个算法可以应用在词频分析，信息检索，字符串匹配等方面。

字典树的实现

C 语言实现

定义结构体

1
2
3
4
5
typedef struct node {
    struct node* children[SUB_NODE_COUNT];
    int flag;
    char character;
} Node;

树节点的数据包含三个部分

  • 所含的字母
  • 指向下一节点的指针
  • 是否能终结的标志位，也就是说是否能与它的祖先节点组成一个单词。

字典树的插入函数

C 语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
Node* create_node(char c, int flag) {
    Node* n = malloc(sizeof(Node));
    n->character = c;
    n->flag = flag;
    for (int i = 0; i < SUB_NODE_COUNT; i++) {
        n->children[i] = NULL;
    }
    return n;
}

int append_node(Node* n, char c) {

    Node* child_ptr =  n->children[c-'a'];
    if (child_ptr) {
        return FALSE;
    }
    else {
        n->children[c-'a'] = create_node(c, FALSE);
        return TRUE;
    }
}

int add_word(Node* root, char* str) {
    char c = *str;
    Node* ptr = root;
    int flag = TRUE;
    while(c != '\0') {
        if (!append_node(ptr, c)) {
             flag = FALSE;
        }
        ptr = ptr->children[c-'a'];
        c = *(++str);
    }
    if (!ptr->flag) {
        flag = FALSE;
        ptr->flag = TRUE;
    }
    return !flag;
}

这个函数的功能，将单词插入树中，假如目标单词已经存在于树中，则返回FALSE , 否则就能成功插入，返回TRUE。插入的过程比较简单，只要单词字母对应的节点存在，则继续往下查询，否则就创建新节点，然后在最后的一个字母的节点把flag改为FALSE;

字典树的查找函数

C 语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int check(Node* root, char* word) {
    Node* ptr = root;
    int len = strlen(word);
    for (int i = 0; i < len; i++) {
        if (!ptr) {
            printf("\"%s\" isn't in the Dictionary!\n", word);
            return FALSE;
        }
        ptr = ptr->children[word[i]-'a'];
    }
    if (ptr && ptr->flag) {
        printf("\"%s\" is in the Dictionary!\n", word);
        return TRUE;
    } else {
        printf("\"%s\" isn't in the Dictionary!\n", word);
        return FALSE;
    }

}

字典树的遍历函数

C 语言实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void traversal(Node* root, char* str) {

    if (!root) {
        return;
    }

    int len_of_str = strlen(str);
    char* new_str = malloc(len_of_str+1);
    strcpy(new_str, str);
    new_str[len_of_str] = root->character;

    if (root->flag) {
        //输出
        char* str_for_print = malloc(len_of_str+2);
        strcpy(str_for_print, new_str);
        str_for_print[len_of_str+1] = '\0';
        printf("%s\n", str_for_print);
        free(str_for_print);
    }

    for (int i = 0; i < SUB_NODE_COUNT; i++) {
        traversal(root->children[i], new_str);
    }
    free(new_str);
}

很显然，这里用深度优先遍历比较合适，因为这是根据单词字母的组成来垂直扩展多叉树的。对于深度优先算法，递归是最能偷懒的方法啦！深度遍历的过程中，只要遇到flag等于TRUE，跟祖先节点构成单词输出，那就 OK 啦。

字典树的删除函数

C 语言实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int isLeave(Node* root) {
    for (int i = 0; i < SUB_NODE_COUNT; i++) {
        if (root->children[i]) {
            return FALSE;
        }
    }
    return TRUE;
}

int delete_word(Node* root, char* word) {
    int len = strlen(word);
    int first_index = word[0] - 'a';
    if (!root->children[first_index]) {
        return FALSE;
    }
    if (len == 1) {
        if (root->children[first_index]->flag) {
            if (isLeave(root->children[first_index])) {
                free(root->children[first_index]);
                root->children[first_index] = NULL;
            } else {
                root->children[first_index]->flag = FALSE;
            }
            return TRUE;
        } else {
            return FALSE;
        }
    }
    int flag = delete_word(root->children[first_index], word+1);
    if (isLeave(root->children[first_index]) && !root->children[first_index]->flag) {
        free(root->children[first_index]);
        root->children[first_index] = NULL;
    }
    return flag;
}

其实删除一个单词最直接的方法就是把最后一个字母的flag改为FALSE就可以了。但是如果只是这么做的话，随着操作的次数增加，会产生许多多余的没必要的节点，浪费很多的空间。
因此这个函数需要完成两件事

  • 判断删除的单词是否存在，假如不存在则返回FALSE.
  • 删除多余的节点。
    节点必须同时满足以下两点才能定义为多余的节点。
  • 没有子节点（叶子节点）
  • flag 的值为 FALSE

完整实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

#define SUB_NODE_COUNT 26

typedef struct node {
    struct node* children[SUB_NODE_COUNT];
    int flag;
    char character;
} Node;

Node* create_node(char c, int flag) {
    Node* n = malloc(sizeof(Node));
    n->character = c;
    n->flag = flag;
    for (int i = 0; i < SUB_NODE_COUNT; i++) {
        n->children[i] = NULL;
    }
    return n;
}

int append_node(Node* n, char c) {

    Node* child_ptr =  n->children[c-'a'];
    if (child_ptr) {
        return FALSE;
    }
    else {
        n->children[c-'a'] = create_node(c, FALSE);
        return TRUE;
    }
}

int add_word(Node* root, char* str) {
    char c = *str;
    Node* ptr = root;
    int flag = TRUE;
    while(c != '\0') {
        if (!append_node(ptr, c)) {
             flag = FALSE;
        }
        ptr = ptr->children[c-'a'];
        c = *(++str);
    }
    if (!ptr->flag) {
        flag = FALSE;
        ptr->flag = TRUE;
    }
    return !flag;
}

void traversal(Node* root, char* str) {

    if (!root) {
        return;
    }

    int len_of_str = strlen(str);
    char* new_str = malloc(len_of_str+1);
    strcpy(new_str, str);
    new_str[len_of_str] = root->character;

    if (root->flag) {
        //输出
        char* str_for_print = malloc(len_of_str+2);
        strcpy(str_for_print, new_str);
        str_for_print[len_of_str+1] = '\0';
        printf("%s\n", str_for_print);
        free(str_for_print);
    }

    for (int i = 0; i < SUB_NODE_COUNT; i++) {
        traversal(root->children[i], new_str);
    }
    free(new_str);
}

int check(Node* root, char* word) {
    Node* ptr = root;
    int len = strlen(word);
    for (int i = 0; i < len; i++) {
        if (!ptr) {
            printf("\"%s\" isn't in the Dictionary!\n", word);
            return FALSE;
        }
        ptr = ptr->children[word[i]-'a'];
    }
    if (ptr && ptr->flag) {
        printf("\"%s\" is in the Dictionary!\n", word);
        return TRUE;
    } else {
        printf("\"%s\" isn't in the Dictionary!\n", word);
        return FALSE;
    }

}

int isLeave(Node* root) {
    for (int i = 0; i < SUB_NODE_COUNT; i++) {
        if (root->children[i]) {
            return FALSE;
        }
    }
    return TRUE;
}

int delete_word(Node* root, char* word) {
    int len = strlen(word);
    int first_index = word[0] - 'a';
    if (!root->children[first_index]) {
        return FALSE;
    }
    if (len == 1) {
        if (root->children[first_index]->flag) {
            if (isLeave(root->children[first_index])) {
                free(root->children[first_index]);
                root->children[first_index] = NULL;
            } else {
                root->children[first_index]->flag = FALSE;
            }
            return TRUE;
        } else {
            return FALSE;
        }
    }
    int flag = delete_word(root->children[first_index], word+1);
    if (isLeave(root->children[first_index]) && !root->children[first_index]->flag) {
        free(root->children[first_index]);
        root->children[first_index] = NULL;
    }
    return flag;
}

int main(void) {
    Node *root = create_node('$', FALSE);

    //测试add_ word函数
    add_word(root, "abc");
    add_word(root, "abcd");
    add_word(root, "world");
    add_word(root, "nnaiodnf");
    traversal(root, "");

    //测试check函数
    check(root, "abc");
    check(root, "abcd");

    //测试delete_word函数
    delete_word(root, "abe");
    check(root, "abe");

    return EXIT_SUCCESS;
}

Reference:用 C 语言实现字典树

线段树

直接上链接，说的贼详细
线段树详解

树状数组

直接上链接，说的贼详细
树状数组详解

最小生成树

这个不是树，是图，就直接放链接吧
最小生成树构造算法
其实是我学不动了

LeetCode 题解

LeetCode 题号: 101. 对称二叉树

话不多说，直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool isSymmetric(struct TreeNode* root){
    if (root == NULL) return true;
    return fun(root->left, root->right);
}

int fun(struct TreeNode* left,struct TreeNode* right){
    if(left == NULL&&right == NULL){
        return true;
    }
    if(left == NULL || right == NULL){
        return false;
    }
    if(left->val!=right->val){
        return false;
    }

    return fun(left->left,right->right)&&fun(left->right,right->left);
}

思路:如果同时满足下面的条件，两个树互为镜像：

  • 它们的两个根结点具有相同的值。
  • 每个树的右子树都与另一个树的左子树镜像对称。
    因此，我们就可以很自然地把上边的想法写成一个递归函数。

LeetCode 题号：96. 不同的二叉搜索树

可以使用动态规划法求解
给定一个有序序列 1 … n，为了根据序列构建一棵二叉搜索树。我们可以遍历每个数字 i，将该数字作为树根，1 … (i-1) 序列将成为左子树，(i+1) … n 序列将成为右子树。于是，我们可以递归地从子序列构建子树。
在上述方法中，由于根各自不同，每棵二叉树都肯定能保证是独特的。
C 语言实现：

1
2
3
4
5
6
7
8
9
10
11
12
int numTrees(int n){
    int * dp = (int*)malloc(sizeof(int)*(n+2));
    bzero(dp,sizeof(int)*(n+2));
    dp[0] = 1;
    dp[1] = 1;

    for(int i = 2; i <= n; i++)
        for(int j = 1; j <= i; j++){
            dp[i] += dp[j - 1] * dp[i - j];
        }
    return dp[n];
}

LeetCode 题号: 99. 恢复二叉搜索树

因为题目中说了，二叉搜索树中只有两个节点被错误地交换。并且，正常的二叉搜索树中序遍历输出应该是递增的。
所以，在遍历二叉树的过程中找到不满足递增的点（即错误交换的点），交换两者的值即可。
错误交换的点在中序遍历结果中可能是相邻的，也可能是不相邻的。
例如，若一棵树中序遍历结果 1324，错误交换的点 2 和 3 就是相邻的；使用 first 和 second 表示错误交换的两个点，在第一次遇到不递增的情况时，将 first 置为 3，second 置为 2，遍历结束后交换 first 与 second。

再如，若一棵树中序中序遍历结果 321，错误交换的点就是不相邻的。在第一次遇到不递增的情况时，将 first 设置为 3，second 设置为 2，在第二次遇到不递增的情况时，只改变 second，将 second 置为 1.遍历结束后交换 first 与 second。
将这个想法写成代码，就成了下面这个样子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* first = NULL;
struct TreeNode* second = NULL;
struct TreeNode* pre = NULL;

void inorder(struct TreeNode* root){
    if(root == NULL)
         return;
    inorder(root->left);
     if(pre != NULL && pre->val > root->val){
        if(first == NULL){//first为空,首次找到前后大小不对的点
            first = pre;
            second = root;
        }
        else{//first不为空,第二次找到前后大小不对的点,只更新second
            second = root;
        }
    }
    pre = root;
    inorder(root->right);
}
void recoverTree(struct TreeNode* root){
    inorder(root);
    int tmp = first->val;
    first->val = second->val;
    second->val = tmp;
}

然而并没有 AC，就先洗洗睡了

我保证

会把线段树、树状数组、最小生成树认真学了
就这样，先咕为敬！
有空再补！
咕咕咕
笑着看着你


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://blog.zam-meow.cn/2019/11/26/AST-Task4/

评论




博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本站使用 Zam's Blog 作为主题，总访问量为 次
字数统计：47k 载入天数...载入时分秒...

Copyright © 2019-2021 Zam