数据结构-链式二叉树

一、链式二叉树

因为二叉树的度是确定的，所以可以用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成: 数据域和左右指针域。左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址，其结构如下:

typedef int BTDataType;
//二叉链
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left; //指向当前结点的左孩子struct BinaryTreeNode* right; //指向当前结点的右孩子BTDataType val; //当前结点的值域
}BTNode;

1.1 链式二叉树的创建

二叉树的创建方式比较复杂, 为了更好的步入到二叉树的内容中，我们先手动创建一棵链式二叉树。

比如我们要创建如下一个二叉树：

//创建节点
BTNode* BuyBTNode(int val)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->val = val;newnode->left = NULL;newnode->right = NULL;return newnode;
}
//创建链式二叉树
BTNode* CreateBTree()
{BTNode* node1 = BuyBTNode(1);BTNode* node2 = BuyBTNode(2);BTNode* node3 = BuyBTNode(3);BTNode* node4 = BuyBTNode(4);BTNode* node5 = BuyBTNode(5);BTNode* node6 = BuyBTNode(6);BTNode* node7 = BuyBTNode(7);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;node5->left = node7;return node1;
}

1.2 根、左子树、右子树

由于这里是链式二叉树，所以后面我们看到一个二叉树，就要把树分成三个部分：根、左子树、右子树。回顾二叉树的概念：二叉树分为空树和非空二叉树，非空二叉树由根结点、根结点的左子树、根结点的右子树组成的。
根结点的左子树和右子树分别又是由子树的根结点、子树结点的左子树、子树结点的右子树组成的。因此二叉树的定义是递归式的, 后序链式二叉树的操作中基本都是按照该概念实现的。

1.3 二叉树的前中后序遍历

二叉树的操作离不开树的遍历，那二叉树的遍历有哪些方式呢？比如我们要遍历下面这个二叉树：
二叉树的遍历分为三种：前/中/后序遍历。下面我们分别讲解三种遍历。

1.3.1前(先)序遍历

▲ 前序遍历(Preorder Traversal(DLR)亦称先序遍历): 访问根结点的操作发生在遍历其左右子树之前

访问顺序为: 根结点、左子树、右子树

void PreOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}printf("%c ",root->val);PreOrder(root->left);PreOrder(root->right);
}

先看运行结果：

打印的结果为什么是上面的样子呢？这里涉及到函数的递归，所以要先理解前序遍历的顺序是根、左子树、右子树。也就是从根节点开始遍历，根遍历完了就到左子树，那左子树又可以分为根、左子树、右子树，又会按照根左右的顺序遍历；要等到左子树完完全全遍历完了，才会遍历到右子树。这里的难点就是: 理解递归递推的终止条件和每一层函数调用完毕后会返回上一层调用它的函数处继续往后执行(回归)。

前序遍历的递归过程如下：

1.3.2中序遍历

◆中序遍历(lnorder Traversal(LDR)): 访问根结点的操作发生在遍历其左右子树之中(间)

访问顺序为: 左子树、根结点、右子树

void InOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}InOrder(root->left);printf("%c ", root->val);InOrder(root->right);
}

打印结果如下：

中序遍历就是从左子树开始遍历，左子树遍历完了就遍历根，最后再遍历右子树。而其中的子树又可以分为左子树、根、右子树，又会按照左根右的顺序遍历。

1.3.3后序遍历

▼后序遍历(Postorder Traversal(LRD)): 访问根结点的操作发生在遍历其左右子树之后

访问顺序为: 左子树、右子树、根结点

void PostOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}PostOrder(root->left);PostOrder(root->right);printf("%c ", root->val);
}

打印结果如下：

后序遍历就是根要在左右子树之后访问。前\中\后续遍在历代码中的递归调用虽然只是换了个位置，但是递归调用的过程是不相同的，如不理解函数的逐层调用过程，就需要画图层层递进地来深刻剖析递归。

1.4 二叉树的节点个数

通过递归计算二叉树的节点个数：

int BTreeSize(BTNode* root)
{if (root == NULL)return 0;return BTreeSize(root->left) + BTreeSize(root->right) + 1;
}

这里要理解递归的过程是什么样, 以下图的举例来理解这里的递归：
这里递推的结束条件是：子树为空才会回归上一层; 而空树就没有节点嘛！所以return 0。在返回上一层的时候可以看到是左右子树都递归完毕而且还要加一个1之后才返回上一层，加的1其实就是加上根节点的数量。

1.5 二叉树的叶子结点个数

通过递归计算二叉树的叶子节点个数：

int BTreeLeafSize(BTNode* root)
{if (root == NULL)return 0;if (root->left == NULL && root->right == NULL)return 1;return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}

没有孩子节点的节点就是叶子节点，所以递推结束的条件就是：该节点的左右子树为空就返回1，即把该叶子节点的数量计上。而一开始的判空其实针对对根节点而言的。如果树都为空，那就没有叶子节点啦。举例递归过程：

1.6 第K层节点个数

二叉树的第K层节点个数：

int BTreeLevelKSize(BTNode* root, int k)
{assert(k > 0);if (root == NULL)return 0;if (k == 1)return 1;return BTreeLevelKSize(root->left, k - 1)+ BTreeLevelKSize(root->right, k - 1);
}

计算二叉树第K层的节点，这里需要加入一个参数k才能实现，因为我们不知道递归什么时候会到达第k层，所以传一个参数k，让它每递推一次就递减1，若根节点为第一层，则k递减到1就到达第k层了(递推终止条件)。当然还有一个递推终止条件就是还没到达第k层就已经出现了空节点，所以还没到达第k层时就遇到了空就返回。

1.7 二叉树的高度

通过递归计算二叉树的高度/深度：

int BTreeDepth(BTNode* root)
{if (root == NULL)return 0;int leftDepth = BTreeDepth(root->left);int rightDepth = BTreeDepth(root->right);return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

计算二叉树的高度也就是计算该二叉树有多少层？那就是我们要找到一个沿着其祖先路径最长的那个节点。所以左右子树之间需要通过比较返回较长的那个节点才行。每返回一层要加个1因为每个节点相较于其孩子节点都是一个根，只要不为空就要算一节长度。
注意：如果上面的代码简化写成下面的样子：

return BTreeDepth(root->left) > BTreeDepth(root->right)? BTreeDepth(root->left)+1 : BTreeDepth(root->right)+1;

这样写时间效率上会非常差。试想：如果二叉树的节点数量庞大，即层数很多时；左右子树相比较就要进行两个函数的递归调用，递归调用又是三目表达式，那时间消耗就会很大；而等比较出了大小以后，才决定三目表达式的返回值；而返回值又是一个函数的递归调用，递推进入下一层以后还是面临同样的三目表达式，同样的事情一遍又一遍地重复，就会消耗非常非常多的时间。所以这里不建议这么写，最好的方式就是将函数的返回值记录下来，这样回归的时候将记录下来的值返回去，就不会造成上面的情况。

1.8 查找指定的值(val)

在二叉树中查找指定的值x, 如果找到则返回该节点的地址, 否则返回NULL。

BTNode* BTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->val == x)return root;BTNode* ret1 = BTreeFind(root->left, x);if (ret1 != NULL)return ret1;return BTreeFind(root->right, x);
}

举如下一个例子：比如我们要找x == 3的节点，则函数的递归过程如下：
递归的难点就是返回值不是一下子返回到最上面(最外面)的函数，而是返回上一层调用它的函数处。

1.9 二叉树的销毁

销毁二叉树的销毁就比较简单了, 递归的过程采用后续遍历释放节点：

void BTreeDestroy(BTNode* root)
{if (root == NULL)return;BTreeDestroy(root->left);BTreeDestroy(root->right);free(root);
}

链式二叉树适合于数据的存储，但并不适用于数据的增删查改。所以这里只是了解链式二叉树的性质，以及怎样通过递归去求二叉树的节点、叶子结点、高度等。

二、层序遍历

2.1 二叉树的层序遍历

除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根结点所在层数为1，层序遍历就是从所在二叉树的根结点出发，首先访问第一层的树根结点，然后从左到右访问第2层上的结点，接着是第三层的结点，以此类推；自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

实现层序遍历最好的方法是借助数据结构: 队列

可以看到上图通过队列就可以实现二叉树的层序遍历，每出队一个元素就让该元素的左右孩子入队。代码实现如下：(队列的性质是先进先出)

void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root != NULL)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);printf("%c ", top->val);QueuePop(&q);if (top->left != NULL){QueuePush(&q, top->left);}if (top->right != NULL){QueuePush(&q, top->right);}}QueueDestroy(&q);
}

注意：这里队列中每个节点存放的值(data)是二叉树节点的地址。所以队列出队只是将队列的头结点释放掉了，而并没有把节点里存放的二叉树节点指针删掉。上面的代码中可以看到已经提前将队头节点的值(二叉树节点的指针)存放在top里面了。

2.2 层序遍历判断二叉树是否是完全二叉树

有了层序遍历这种方法，我们其实就可以用此方法判断一个二叉树是否是完全二叉树：

bool IsCompleteBTree(BTNode* root)
{Queue q;QueueInit(&q);if (root != NULL)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);//遇到有空指针的地方就跳出循环if (front == NULL)break;QueuePush(&q,front->left);QueuePush(&q,front->right);}//只管出队 //在出队的过程中若有不为空的指针说明不是完全二叉树while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

三、二叉树的性质(补充)

1.若规定根结点所在层数为1, 则一棵非空二叉树的第i层上最多有2^i-1个结点.
2.若规定根结点所在层数为1，则深度(层数)为h的二叉树的最大结点数是2^h-1
3.对任何一棵二叉树, 如果度为0的叶结点个数为n0, 度为2的分支结点个数为n2, 则有: n0=n2+1

解释一下第三个性质：

3.1选择题

(1) 某完全二叉树按层次输出(同一层从左到右)的列为ABCDEFGH，该完全二叉树的前序序列为 (A)
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA

(2) 某二叉树的先序遍历和中序遍历如下: 先序遍历: EFHIGJK; 中序遍历: HFIEJKG. 则二叉树根节点为 (A)
A E
B F
C G
D H

(3) 一棵二叉树的中序遍历序列为: badce，后序遍历序列为: bdeca，则该二叉树的前序历列为 (D)
A adbce
8 decab
C debac
D abcde
记住：前序序列能确定根节点在最左边，后续遍历能确定根节点在最右边，再结合中序遍历就能分割出整体的左、根、右。将该二叉树画出来。

(4) 某二叉树的后序遍历序列与中序遍历序列相同，均为ABCDEF，则按层次输出(同一层从左到右)为 (A)
A FEDCBA
B CBAFED
C DEFCBA
D ABCDEF

(5) 某二叉树共有399个结点，其中有199个度为2的结点，则该二又树中的叶子结点数为 (B)
A 不存在这样的二叉柯
B 200
C 198
D 199
通过二叉树性质可知：该二叉树的叶子节点个数为199+1 == 200

(6) 下列数据结构中，不适合采用顺序存储结构的是 (AC)
A 非完全二叉树
B 堆
C 队列
D 栈

(7) 在具有2n个结点的完全二叉树中中，叶子结点个数为(A)
A n
B n+1
C n-1
D n/2

(8) 一棵完全二又树的结点个数为531个，那么这棵树的高度为 (B)
A 11
B 10
C 8
D 12