赞
踩
我们前面介绍过完全二叉树以及堆(一种完全二叉树),并且实现了堆用顺序结构存储的数据结构。还介绍了两个基本算法:向上调整算法、向下调整算法。在此基础上使用堆解决了 Top-K 问题,以及堆排序。我们通过完全二叉树的规律可以发现,完全二叉树如果不看最后一层,那么它是一棵满二叉树;最后一层的节点必须是上一层连续节点并且依次是左孩子、右孩子。那么现在要介绍的是普通二叉树。普通二叉树只满足二叉树的基本定义,它不满足完全二叉树的定义。那么普通二叉树的结构可能是下面这几种:
可以发现普通二叉树的结构没有规律,如果用顺序结构存储的话那么物理空间不一定是连续的。
如果是这样,那么数据的存储就没有意义。我们可以试想一下,当我们真正进行数据存储的时候,我们会把数据不连续的存储起来吗?这样做的意义只有增加工作量、难度而已。 不单单是存储数据没有意义,就连删除也没有意义。我们想要访问二叉树的节点时候也是一个难题。所以普通二叉树我们一般使用链式结构,即用链表串联起来,需要注意,这样做的目的不是赋予它适合增删查改的能力,而是使用链式结构可以实现我们从来没有接触过的功能。例如二叉搜索树:
我们使用百科上面的例子做一个分析:
当然我们现在是简单的举一些普通二叉树的应用,本篇介绍的目的是为了打好基础,做好铺垫,为以后的学习打下地基。
我们实现过堆用顺序结构存储的数据结构,里面也涉及到了不少的二叉树性质。那么现在将详细介绍二叉树的性质。
1.若规定根节点的层数为1,那么一颗非空二叉树的第k层最多有 2^(k-1) 个节点
2.若规定根节点的层数为1,那么深度(高度)为h的二叉树最多一共有 2^h-1 个节点
3.对任意一颗二叉树而言,如果度为2的节点个数为n2,度为0的节点个数为n0,那么有n0=n2+1
4.如果规定根节点的层数为1,那么总共有n个节点的满二叉树的深度就为h=log(n+1)
对应这条性质的解释就是数学公式,总节点数为 2^h-1 ,在这个表达式上计算 h ,就用到了对数。
5.在用顺序结构存储的完全二叉树中有下面几个规律:
1.如果 child != 0 ,那么 parent = (child-1)/2 ;如果 child = 0,那么这个节点为根节点
2.如果总节点个数为 n,假设 parent*2+1<n ,那么 parent*2+1 的值就是左孩子的下标
3.如果总节点个数为 n,假设 parent*2+2<n ,那么 parent*2+2 的值就是右孩子的下标
这三条性质在我们实现堆的顺序结构的时候使用过,当然也是基于数学上得来的公式。
1. 某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为( )A 不存在这样的二叉树B 200C 198D 199答案: A 。根据公式 n0=n2+1 可知,度为 0 的节点个数比度为 2 的节点个数多一个。
2. 下列数据结构中,不适合采用顺序存储结构的是()A 非完全二叉树B 堆C 队列D 栈答案:A。即使队列不推荐使用顺序结构存储,但即使使用,也比非完全二叉树效率高。
3. 在具有 2n 个结点的完全二叉树中,叶子结点个数为()A nB n+1C n-1D n/2答案: A 。在二叉树中,节点的分类只有三种,即度为2的节点,度为1的节点和度为0的节点。那么表达式就为 2n = n2+n1+n0 ,又因为 n2=n0+1 ,所以 2n = 2n0-1+n1;又因为 2n 的结果只能是整数,所以 n1 必须等于 1。故n0 = n。
4. 一棵完全二叉树的节点数位为 531 个,那么这棵树的高度为()A 11B 10C 8D 12答案: B 。完全二叉树的节点个数在 [2^(h-1),2^h-1] 这个区间内。那么将 10 带入这个表达式之中,那么区间就为 [512,1023] ,恰好 531 在这个区间之内,所以高度为 10。
5. 一个具有 767 个节点的完全二叉树,其叶子节点个数为()A 383B 384C 385D 386答案: B 。n2+n1+n0=767,因为n2=n0+1,所以得 2n0-1+n1=767,即2n0+n1=768,因为 2n0 的结果必为偶数,所以n1必为0( 完全二叉树特性,度为1的节点个数要不为0要不为1 ),所以n0=384。
我们再回顾一下二叉树的性质,我们提到过二叉树是递归定义的。
在任意一颗二叉树中,只有两种可能:要不为空;要不就为根节点、左子树和右子树组成。
了解了递归定义之后,我们就着手前序遍历、中序遍历和后序遍历。
注意我的用词,在每一颗树中。每一颗树,相当于左子树是一棵树,左子树当中又分为根节点、左子树和右子树,左子树的左子树又是一颗树,它又分为根节点、左子树和右子树……
我们先画一下前序遍历的顺序图。
就像这样层层递归,就可以完成遍历。那么中序遍历、后序遍历和前序遍历一样,那么这里的顺序图就省略了,我们直接看结果:
清楚了遍历顺序之后,就可以开始着手代码。这里注意,因为现在的部分是为了后续学习打基础,所以在这里手动构造与例子相同的二叉树。
- #include <stdlib.h>
- #include <assert.h>
- #include <stdio.h>
-
- typedef int BinaryData;
- typedef struct Node
- {
- BinaryData val;
- struct Node* left;
- struct Node* right;
- }Node;
-
- Node* CreateNode()
- {
- Node* n1 = (Node*)malloc(sizeof(Node));
- assert(n1);
- Node* n2 = (Node*)malloc(sizeof(Node));
- assert(n2);
- Node* n3 = (Node*)malloc(sizeof(Node));
- assert(n3);
- Node* n4 = (Node*)malloc(sizeof(Node));
- assert(n4);
- Node* n5 = (Node*)malloc(sizeof(Node));
- assert(n5);
- Node* n6 = (Node*)malloc(sizeof(Node));
- assert(n6);
-
- n1->val = 1;
- n2->val = 2;
- n3->val = 3;
- n4->val = 4;
- n5->val = 5;
- n6->val = 6;
-
- n1->left = n2;
- n1->right = n4;
- n2->left = n3;
- n2->right = NULL;
- n3->left = NULL;
- n3->right = NULL;
- n4->left = n5;
- n4->right = n6;
- n5->left = NULL;
- n5->right = NULL;
- n6->left = NULL;
- n6->right = NULL;
-
- return n1;
- }
-
- //前序遍历
- void PreTraval(Node* root)
- {
- if (root == NULL)
- {
- printf("NULL ");
- return;
- }
- printf("%d ", root->val);
- PreTraval(root->left);
- PreTraval(root->right);
- }
-
- //中序遍历
- void MidTraval(Node* root)
- {
- if (root == NULL)
- {
- printf("NULL ");
- return;
- }
- MidTraval(root->left);
- printf("%d ", root->val);
- MidTraval(root->right);
- }
-
- //后序遍历
- void PosTraval(Node* root)
- {
- if (root == NULL)
- {
- printf("NULL ");
- return;
- }
- PosTraval(root->left);
- PosTraval(root->right);
- printf("%d ", root->val);
- }
-
- int main()
- {
- Node* root = CreateNode();
- PreTraval(root);
- printf("\n");
- MidTraval(root);
- printf("\n");
- PosTraval(root);
- printf("\n");
- return 0;
- }

了解了遍历之后,现在有很多衍生问题:怎么求节点个数?怎么求第k层的节点个数?如何求叶节点个数?如何查找值为x的节点?
我们逐个分析,如何求节点个数。求个数呢,通用方法是计数法,那么计数法在我们的递归上面也可以使用。
- //求节点个数
- int count = 0;//使用全局变量
- int NodeSize(Node* root)
- {
- if (root == NULL)
- {
- return 0;
- }
- //static int count = 0;//使用static修饰的静态变量
- count++;
- NodeSize(root->left);
- NodeSize(root->right);
- return count;
- }
-
- int main()
- {
- Node* root = CreateNode();
- /*PreTraval(root);
- printf("\n");
- MidTraval(root);
- printf("\n");
- PosTraval(root);
- printf("\n");*/
-
- printf("NodeSize = %d\n", NodeSize(root));
- printf("NodeSize = %d\n", NodeSize(root));
- return 0;
- }

可以看到我们使用计数法是可以帮助我们完成任务的,但是当我们第二次调用这个函数就出现了问题。原因是全局变量和static修饰的静态变量只能被初始化一次。所以我们的计数方法是不够好的,那我们就要着手递归的方法了。
- //求节点个数
- int NodeSize(Node* root)
- {
- if (root == NULL)
- {
- return 0;
- }
- return NodeSize(root->left) + NodeSize(root->right) + 1;
- }
- //int count = 0;//使用全局变量
- //int NodeSize(Node* root)
- //{
- // if (root == NULL)
- // {
- // return 0;
- // }
- // //static int count = 0;//使用static修饰的静态变量
- // count++;
- // NodeSize(root->left);
- // NodeSize(root->right);
- // return count;
- //}
-
- int main()
- {
- Node* root = CreateNode();
- /*PreTraval(root);
- printf("\n");
- MidTraval(root);
- printf("\n");
- PosTraval(root);
- printf("\n");*/
-
- printf("NodeSize = %d\n", NodeSize(root));
- printf("NodeSize = %d\n", NodeSize(root));
- return 0;
- }

可以看到,递归的方式完美的解决了计数的"BUG"。
通过公式我们就可以发现,k是一定要被减1的,那么在递归当中也不例外。既然是要求某一层的节点个数,我们只要加一个条件:即递归到了指定层数的时候,才有返回值。
- //求第k层的节点个数
- int KSize(Node* root,int k)
- {
- assert(k > 0);//层数大于0才有意义
- if (root == NULL)
- {
- return 0;
- }
- //加一个特定条件,必须在这一层才具有返回值
- if (k == 1)
- {
- return 1;
- }
- //否则继续往下递归找到指定层数
- return KSize(root->left,k-1) + KSize(root->right,k-1);
- }
-
- int main()
- {
- Node* root = CreateNode();
- /*PreTraval(root);
- printf("\n");
- MidTraval(root);
- printf("\n");
- PosTraval(root);
- printf("\n");*/
-
- //printf("NodeSize = %d\n", NodeSize(root));
- //printf("NodeSize = %d\n", NodeSize(root));
-
- printf("KSize = %d\n", KSize(root, 3));
- printf("KSize = %d\n", KSize(root, 1));
-
- return 0;
- }

叶节点的特征为度为0,即左右孩子都为空。不言而喻,需要添加一个条件来具有返回值。
- //求叶节点的个数
- int LeafSize(Node* root)
- {
- if (root == NULL)
- {
- return 0;
- }
- if (root->left == NULL && root->right == NULL)
- {
- return 1;
- }
- return LeafSize(root->left) + LeafSize(root->right);
- }
-
- int main()
- {
- Node* root = CreateNode();
- /*PreTraval(root);
- printf("\n");
- MidTraval(root);
- printf("\n");
- PosTraval(root);
- printf("\n");*/
-
- //printf("NodeSize = %d\n", NodeSize(root));
- //printf("NodeSize = %d\n", NodeSize(root));
-
- //printf("KSize = %d\n", KSize(root, 3));
- //printf("KSize = %d\n", KSize(root, 1));
-
- printf("LeafSize = %d\n", LeafSize(root));
- return 0;
- }

很明显,我们需要添加一个条件来限定返回值。那么其难点在于,如果左子树当中找到了节点,那么右子树就不要遍历了;如果左子树当中没有找到指定节点才需要遍历右子树。如果左右子树都找不到指定节点才返回空。这时就要用到分治的思想。
- //查找值为x的节点
- Node* NodeFind(Node* root, int x)
- {
- if (root == NULL)
- {
- return NULL;
- }
- if (root->val == x)
- {
- return root;
- }
- Node* LeftRet = NodeFind(root->left, x);
- if (LeftRet != NULL)
- {
- return LeftRet;
- }
- Node* RightRet = NodeFind(root->right, x);
- if (RightRet != NULL)
- {
- return RightRet;
- }
- return NULL;
- }
-
- int main()
- {
- Node* root = CreateNode();
- /*PreTraval(root);
- printf("\n");
- MidTraval(root);
- printf("\n");
- PosTraval(root);
- printf("\n");*/
-
- //printf("NodeSize = %d\n", NodeSize(root));
- //printf("NodeSize = %d\n", NodeSize(root));
-
- //printf("KSize = %d\n", KSize(root, 3));
- //printf("KSize = %d\n", KSize(root, 1));
-
- //printf("LeafSize = %d\n", LeafSize(root));
-
- printf("NodeFind = %p\n", NodeFind(root, 1));
- printf("NodeFind = %p\n", NodeFind(root, 3));
- printf("NodeFind = %p\n", NodeFind(root, 100));
-
- return 0;
- }

二叉树的销毁,就是销毁所有的节点。后序遍历是非常契合的。
- //二叉树销毁
- void BinaryDestroy(Node* root)
- {
- if (root == NULL)
- {
- return;
- }
- BinaryDestroy(root->left);
- BinaryDestroy(root->right);
- free(root);
- }
我们可以发现,上面提到的前序、中序、后序遍历好像都在往深的地方走,走到无路可走再退回到上一层继续往深的地方走。由此我们可以总结,前序、中序、后序遍历它们都是一种深度优先遍历(DFS)。现在我们要介绍二叉树的非递归遍历,即层序遍历。层序遍历是一种广度优先遍历(BFS)。
那么层序遍历实现的思路是怎么样的呢?我们需要借助一个工具——队列。我们看图:
那么我们上手代码时要注意,在C语言的库中没有队列这个数据结构,所以我们需要将实现队列的代码CV过来。这个问题在C++中会得到解决。那么代码我们就可以这么写:
- //层序遍历
- void LayerTraval(Node* root)
- {
- HeadTail q;
- QueueInit(&q);
-
- //为空则为空树
- if (root == NULL)
- {
- return;
- }
- //非空则入队列
- QueuePush(&q, root);
-
- while (!QueueEmpty(&q))
- {
- Node* tmp = QueueHead(&q);
- QueuePop(&q);
- printf("%d ", tmp->val);
-
- if (tmp->left != NULL)
- {
- QueuePush(&q, tmp->left);
- }
- if (tmp->right != NULL)
- {
- QueuePush(&q, tmp->right);
- }
- }
- QueueDestroy(&q);
- }
-
- int main()
- {
- Node* root = CreateNode();
- /*PreTraval(root);
- printf("\n");
- MidTraval(root);
- printf("\n");
- PosTraval(root);
- printf("\n");*/
-
- //printf("NodeSize = %d\n", NodeSize(root));
- //printf("NodeSize = %d\n", NodeSize(root));
-
- //printf("KSize = %d\n", KSize(root, 3));
- //printf("KSize = %d\n", KSize(root, 1));
-
- //printf("LeafSize = %d\n", LeafSize(root));
-
- //printf("NodeFind = %p\n", NodeFind(root, 1));
- //printf("NodeFind = %p\n", NodeFind(root, 3));
- //printf("NodeFind = %p\n", NodeFind(root, 100));
-
- LayerTraval(root);
- return 0;
- }

碰到问题我们大胆地去想,首先便是通过节点个数能不能确定二叉树是否为完全二叉树。答案很明显不可能,因为完全二叉树的最后一层需要保证节点是连续的。但是这个方法是可以确定满二叉树的。
既然我们要通过层序遍历,那我们试着遍历任意几颗完全二叉树寻找规律:
我们遍历两颗普通二叉树:
可以发现一个非常明显的规律,即完全二叉树使用层序遍历的结果 NULL 总为连续的;而普通二叉树使用层序遍历的结果 NULL 是不连续的。
那么这个规律,便是我们代码的突破口。
- //判断是否为完全二叉树
- bool FuncTree(Node* root)
- {
- HeadTail q;
- QueueInit(&q);
- if (root == NULL)
- {
- return;
- }
- QueuePush(&q, root);
- while (!QueueEmpty(&q))
- {
- Node* tmp = QueueHead(&q);
- QueuePop(&q);
- //一旦拿到空,就跳出循环进行判断
- //此时队列后面要不有节点,要不为空
- //不用担心二叉树的所有节点是否完全存放在队列里面
- if (tmp == NULL)
- {
- break;
- }
- QueuePush(&q, tmp->left);
- QueuePush(&q, tmp->right);
-
- }
- while (!QueueEmpty(&q))
- {
- Node* tmp = QueueHead(&q);
- QueuePop(&q);
- if (tmp != NULL)
- {
- return false;
- }
- }
- QueueDestroy(&q);
- return true;
- }
-
-
- int main()
- {
- Node* root = CreateNode();
- /*PreTraval(root);
- printf("\n");
- MidTraval(root);
- printf("\n");
- PosTraval(root);
- printf("\n");*/
-
- //printf("NodeSize = %d\n", NodeSize(root));
- //printf("NodeSize = %d\n", NodeSize(root));
-
- //printf("KSize = %d\n", KSize(root, 3));
- //printf("KSize = %d\n", KSize(root, 1));
-
- //printf("LeafSize = %d\n", LeafSize(root));
-
- //printf("NodeFind = %p\n", NodeFind(root, 1));
- //printf("NodeFind = %p\n", NodeFind(root, 3));
- //printf("NodeFind = %p\n", NodeFind(root, 100));
-
- //LayerTraval(root);
- printf("FuncTree = %d\n", FuncTree(root));
- return 0;
- }

为了方便,我把完整代码放在这里(队列各接口除外)。
- //队列的声明
- #include <stdlib.h>
- #include <assert.h>
- #include <stdbool.h>
- #include <stdio.h>
-
- typedef int BinaryData;
- typedef struct Node
- {
- BinaryData val;
- struct Node* left;
- struct Node* right;
- }Node;
-
-
- //链表的结点
- typedef Node* QueueData;
- typedef struct QueueNode
- {
- QueueData val;
- struct QueueNode* next;
- }QueueNode;
- //存储头、尾结点地址的指针
- typedef struct HeadTail
- {
- QueueNode* head;
- QueueNode* tail;
- int size;//记录队列有几个元素
- }HeadTail;
-
- void QueueInit(HeadTail* p);//初始化队列
- void QueuePush(HeadTail* p,QueueData x);//进入队列
- QueueData QueueHead(HeadTail* p);//获取队头元素
- QueueData QueueTail(HeadTail* p);//获取队尾元素
- void QueuePop(HeadTail* p);//删除操作,出队
- bool QueueEmpty(HeadTail* p);//检查队列是否为空
- int QueueSize(HeadTail* p);//获取队列元素个数
- void QueuePopTail(HeadTail* p);
- void QueueDestroy(HeadTail* p);//销毁队列

- #include "Queue.h"
-
-
- Node* CreateNode()
- {
- Node* n1 = (Node*)malloc(sizeof(Node));
- assert(n1);
- Node* n2 = (Node*)malloc(sizeof(Node));
- assert(n2);
- Node* n3 = (Node*)malloc(sizeof(Node));
- assert(n3);
- Node* n4 = (Node*)malloc(sizeof(Node));
- assert(n4);
- Node* n5 = (Node*)malloc(sizeof(Node));
- assert(n5);
- Node* n6 = (Node*)malloc(sizeof(Node));
- assert(n6);
-
- n1->val = 1;
- n2->val = 2;
- n3->val = 3;
- n4->val = 4;
- n5->val = 5;
- n6->val = 6;
-
- n1->left = n2;
- n1->right = n4;
- n2->left = n3;
- n2->right = NULL;
- n3->left = NULL;
- n3->right = NULL;
- n4->left = n5;
- n4->right = n6;
- n5->left = NULL;
- n5->right = NULL;
- n6->left = NULL;
- n6->right = NULL;
-
- return n1;
- }
-
- //前序遍历
- void PreTraval(Node* root)
- {
- if (root == NULL)
- {
- printf("NULL ");
- return;
- }
- printf("%d ", root->val);
- PreTraval(root->left);
- PreTraval(root->right);
- }
-
- //中序遍历
- void MidTraval(Node* root)
- {
- if (root == NULL)
- {
- printf("NULL ");
- return;
- }
- MidTraval(root->left);
- printf("%d ", root->val);
- MidTraval(root->right);
- }
-
- //后序遍历
- void PosTraval(Node* root)
- {
- if (root == NULL)
- {
- printf("NULL ");
- return;
- }
- PosTraval(root->left);
- PosTraval(root->right);
- printf("%d ", root->val);
- }
-
- //求节点个数
- int NodeSize(Node* root)
- {
- if (root == NULL)
- {
- return 0;
- }
- return NodeSize(root->left) + NodeSize(root->right) + 1;
- }
- //int count = 0;//使用全局变量
- //int NodeSize(Node* root)
- //{
- // if (root == NULL)
- // {
- // return 0;
- // }
- // //static int count = 0;//使用static修饰的静态变量
- // count++;
- // NodeSize(root->left);
- // NodeSize(root->right);
- // return count;
- //}
-
- //求第k层的节点个数
- int KSize(Node* root,int k)
- {
- assert(k > 0);//层数大于0才有意义
- if (root == NULL)
- {
- return 0;
- }
- //加一个特定条件,必须在这一层才具有返回值
- if (k == 1)
- {
- return 1;
- }
- //否则继续往下递归找到指定层数
- return KSize(root->left,k-1) + KSize(root->right,k-1);
- }
-
- //求叶节点的个数
- int LeafSize(Node* root)
- {
- if (root == NULL)
- {
- return 0;
- }
- if (root->left == NULL && root->right == NULL)
- {
- return 1;
- }
- return LeafSize(root->left) + LeafSize(root->right);
- }
-
- //查找值为x的节点
- Node* NodeFind(Node* root, int x)
- {
- if (root == NULL)
- {
- return NULL;
- }
- if (root->val == x)
- {
- return root;
- }
- Node* LeftRet = NodeFind(root->left, x);
- if (LeftRet != NULL)
- {
- return LeftRet;
- }
- Node* RightRet = NodeFind(root->right, x);
- if (RightRet != NULL)
- {
- return RightRet;
- }
- return NULL;
- }
-
- //层序遍历
- void LayerTraval(Node* root)
- {
- HeadTail q;
- QueueInit(&q);
-
- //为空则为空树
- if (root == NULL)
- {
- return;
- }
- //非空则入队列
- QueuePush(&q, root);
-
- while (!QueueEmpty(&q))
- {
- Node* tmp = QueueHead(&q);
- QueuePop(&q);
- printf("%d ", tmp->val);
-
- if (tmp->left != NULL)
- {
- QueuePush(&q, tmp->left);
- }
- if (tmp->right != NULL)
- {
- QueuePush(&q, tmp->right);
- }
- }
- QueueDestroy(&q);
- }
-
- //二叉树销毁
- void BinaryDestroy(Node* root)
- {
- if (root == NULL)
- {
- return;
- }
- BinaryDestroy(root->left);
- BinaryDestroy(root->right);
- free(root);
- }
-
- //判断是否为完全二叉树
- bool FuncTree(Node* root)
- {
- HeadTail q;
- QueueInit(&q);
- if (root == NULL)
- {
- return;
- }
- QueuePush(&q, root);
- while (!QueueEmpty(&q))
- {
- Node* tmp = QueueHead(&q);
- QueuePop(&q);
- //一旦拿到空,就跳出循环进行判断
- //此时队列后面要不有节点,要不为空
- //不用担心二叉树的所有节点是否完全存放在队列里面
- if (tmp == NULL)
- {
- break;
- }
- QueuePush(&q, tmp->left);
- QueuePush(&q, tmp->right);
-
- }
- while (!QueueEmpty(&q))
- {
- Node* tmp = QueueHead(&q);
- QueuePop(&q);
- if (tmp != NULL)
- {
- return false;
- }
- }
- QueueDestroy(&q);
- return true;
- }
-
-
- int main()
- {
- Node* root = CreateNode();
- /*PreTraval(root);
- printf("\n");
- MidTraval(root);
- printf("\n");
- PosTraval(root);
- printf("\n");*/
-
- //printf("NodeSize = %d\n", NodeSize(root));
- //printf("NodeSize = %d\n", NodeSize(root));
-
- //printf("KSize = %d\n", KSize(root, 3));
- //printf("KSize = %d\n", KSize(root, 1));
-
- //printf("LeafSize = %d\n", LeafSize(root));
-
- //printf("NodeFind = %p\n", NodeFind(root, 1));
- //printf("NodeFind = %p\n", NodeFind(root, 3));
- //printf("NodeFind = %p\n", NodeFind(root, 100));
-
- //LayerTraval(root);
- printf("FuncTree = %d\n", FuncTree(root));
- return 0;
- }

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。