数据结构之二叉树

数据结构之二叉树

一、树

1.概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

• 根节点没有前驱节点(没有父节点)；

• 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树；每棵子树的根结点有且只有一个前驱，可以有0个或多个后继；
• 因此，树是递归定义的；

• 子树间不能有其他交集，如果有，那它就是另一种数据结构图，而不是树。

2.相关名词

节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A节点的度为6 ；

叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点；

非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点；

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点；

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点；

兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点；

树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6；

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

树的高度或深度：树中节点的最大层次； 如上图：树的高度为4；

堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点；

节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先；

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙；

森林：由m（m>0）棵互不相交的树的集合称为森林；

3.树的定义

• 树既要求存数据，又要求存储节点间的关系
• 常用表示树的方法有：双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法以及孩子双亲表示法
• 我们就使用最常用的孩子兄弟表示法

typedef int DataType;
struct Node
{struct Node* _firstChild1; // 第一个孩子结点struct Node* _pNextBrother; // 指向其下一个兄弟结点DataType _data; // 结点中的数据域
};

如图：

二、二叉树

1.概念

• 一棵二叉树是结点的一个有限集合；
• 该集合由一个根节点加上两棵分别称为左子树和右子树的二叉树组成，该集合也可能为空；

• 特点1：二叉树不存在度大于2的结点(只有左孩子和右孩子)
• 特点2： 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

现实中的二叉树：

2.特殊的二叉树

• 满二叉树

一个二叉树，如果每一个层的结点数都达到最大值(最大值为2)，则这个二叉树就是满二叉树。

也就是说，如果一个二叉树的层数为K，且结点总数是2^K -1，则它就是满二叉树。

• 完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的；

对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树；

要注意的是满二叉树是一种特殊的完全二叉树。

3.性质

任意层数的最大节点数: 若规定根节点的层数为1，则一棵非空二叉树的第 i 层上最多有 2^(i-1) 个结点；

最大节点数: 若规定根节点的层数为1，则深度为 h 的二叉树的最大结点数是 2^h-1；

叶节点数和度为2的分支节点数的关系: 对任何一棵二叉树, 如果度为0的叶结点个数为 n , 度为2的分支结点个数为 m，则有 n = m + 1，即二叉树的叶节点数始终比度为2的分支节点数多1；

树的深度: 若规定根节点的层数为1，具有n个结点的满二叉树的深度为：h = log (n+1)； ( log以2为底)

节点数与边条数的关系： 对于任意的树都满足边的条数比节点个数少1，因为每个节点都有双亲，但是根节点没有

顺序存储中父节点和子节点的位置关系: 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于下标为 i 的结点有：

• i为0,为根节点
• i > 0 ,父节点下标为 (i-1)/2
• 左孩子为2*i + 1;右孩子为2*i + 2。
• 若2*i + 1 < n 或 2*i + 2 < n,则该节点不是叶节点。(叶节点度为0，即没有孩子)

4.性质的相关题目

1、某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为 ()

A: 不存在 B: 200 C: 198 D: 199

2、在具有 2N 个结点的完全二叉树中，叶子结点个数为 ()

A: N B: N+1 C: N-1 D: N/2

3、一棵完全二叉树的节点数位为531个，那么这棵树的高度为 ()

A: 11 B: 10 C: 8 D: 12

• B A B

1.由结论可得，叶节点树始终比度为2的分支节点多1

2.完全二叉树，只存在度为0，1，2的节点，其中度为1的节点要么只有1个要么不存在，即：n+p+m = 2N(n为度为0的节点，p度位1，m度为2)，又由叶节点始终比度为2的节点的个数多1，所以2n -1 + p = 2N, 由于需要有解，所以p只能为1不能为0，所以n == N

3.高度为h的完全二叉树节点为：N = 2^(h-1) 至 N = 2^(h)-1个，代入只有10符合

三、完整代码

1.结构定义

typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;

2.构建二叉树

由于二叉树不能进行增加和删除操作，所以一般都是给定一个字符串，该字符串中含有需要我们构建的二叉树的所有节点，我们通过读取字符串中的内容来构建二叉树。

注意：字符串中的 # 表示空树，即上一个节点没有左子树或右子树。

//通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}//创建根节点BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc fail");exit(-1);}root->data = a[*pi];(*pi)++;//创建左右子树root->left = BinaryTreeCreate(a, pi);root->right = BinaryTreeCreate(a, pi);return root;
}

3.二叉树节点个数

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL)return 0;//左子树节点个数+右子树节点个数+根节点return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

4.二叉树叶节点个数

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL)return 0;//没有子节点代表该节点为叶节点if (root->left == NULL && root->right == NULL)return 1;//左子树叶节点个数+右子树叶节点个数return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

5.二叉树第K层节点个数

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{assert(k > 0);if (root == NULL)return 0;if (k == 1)return 1;//转化为求第K-1层的节点个数return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

6.在二叉树中查找值为X的节点

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->data == x)return root;//去左子树找，找到就返回BTNode* left = BinaryTreeFind(root->left, x);if (left != NULL)return left;//去右子树找，找到就返回BTNode* right = BinaryTreeFind(root->right, x);if (right != NULL)return right;//如果左右子树都没有，就返回空return NULL;
}

7.遍历

• 前序遍历：先访问根节点，再访问左子树，最后访问右子树；

// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}//先访问根，再访问左子树，最后访问右子树printf("%c ", root->data);BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);
}

• 中序遍历：先访问左子树，再访问根节点，最后访问右子树；

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}//先访问左子树，再访问根，最后访问右子树BinaryTreeInOrder(root->left);printf("%c ", root->data);BinaryTreeInOrder(root->right);
}

• 后序遍历：先访问左子树，再访问右子树，最后访问根节点；

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}//先访问左子树，再访问右子树，最后访问根BinaryTreePostOrder(root->left);BinaryTreePostOrder(root->right);printf("%c ", root->data);
}

• 层序遍历：按照二叉树的逻辑结构，先访问第一层层的所有节点，再访问第二层的所有节点，依次向下访问。

我们使用一个模拟实现的队列进行层序遍历(非递归)

利用一个队列来存每一层的节点，每个父节点出队列时会加入他的孩子节点(没有孩子可以不入)，直到这一层节点全部出队列时，下一层刚好入队列，当最后为队列的头为空(NULL)时，就遍历了所有节点。

// 二叉树层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{if (root == NULL)return;//将节点的地址存储在队列中，取出一个节点的同时将该节点的子节点入栈Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){//取出队顶的元素BTNode* front = QueueFront(&q);QueuePop(&q);printf("%c ", front->data);//将队顶元素的左右子节点入队列if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}QueueDestory(&q);
}

8.销毁二叉树

// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{if (root == NULL)return;//通过后序遍历来销毁节点BinaryTreeDestory(root->left);BinaryTreeDestory(root->right);free(root);  //此处置空不会影响外面，需要在外面进行置空
}

9.BTNode.c

#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include "queue.h"
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
//BTNode* BinaryTreeCreate()//简易Create
//{
//	BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
//	assert(n1);
//	BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
//	assert(n2);
//	BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
//	assert(n3);
//	BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
//	assert(n4);
//	BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
//	assert(n5);
//	BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
//	assert(n6);
//	BTNode* n7 = (BTNode*)malloc(sizeof(BTNode));
//	assert(n7);
//
//	n1->_data = 1;
//	n2->_data = 2;
//	n3->_data = 3;
//	n4->_data = 4;
//	n5->_data = 5;
//	n6->_data = 6;
//	n7->_data = 7;
//
//	n1->_left = n2;
//	n1->_right = n4;
//	n2->_left = n3;
//	n2->_right = NULL;
//	n4->_left = n5;
//	n4->_right = n6;
//	n3->_left = NULL;
//	n3->_right = NULL;
//	n5->_left = NULL;
//	n5->_right = NULL;
//	n6->_left = NULL;
//	n6->_right = NULL;
//
//	n2->_right = n7;
//	n7->_left = NULL;
//	n7->_right = NULL;
//
//	return n1;
//}
//通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}//创建根节点BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc fail");exit(-1);}root->_data = a[*pi];(*pi)++;//创建左右子树root->_left = BinaryTreeCreate(a, pi);root->_right = BinaryTreeCreate(a, pi);return root;
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL) {return 0;}return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL) {return 0;}if (root->_left == NULL && root->_right == NULL) {return 1;}return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{assert(k > 0);if (root == NULL) {return 0;}if (k == 1) {return 1;}return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL) {return NULL;}if (root->_data == x) {return root;}BTNode* lt = BinaryTreeFind(root->_left, x);if (lt) return lt;BTNode* rt = BinaryTreeFind(root->_right, x);if(rt) return rt;return NULL;
}
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL) {printf("NULL ");return;}printf("%c ", root->_data);BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL) {printf("NULL ");return;}BinaryTreeInOrder(root->_left);printf("%c ", root->_data);BinaryTreeInOrder(root->_right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL) {printf("NULL ");return;}BinaryTreePostOrder(root->_left);BinaryTreePostOrder(root->_right);printf("%c ", root->_data);
}void BinaryTreeDestory(BTNode* root)
{if (root == NULL) {return ;}BinaryTreeDestory(root->_left);BinaryTreeDestory(root->_right);free(root);
}// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root != NULL) {QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->_data);if (front->_left) {QueuePush(&q, front->_left);}if (front->_right) {QueuePush(&q, front->_right);}}printf("\\n");QueueDestroy(&q);
}
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(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)) {if (QueueFront(&q) != NULL) {QueueDestroy(&q);return false;}QueuePop(&q);}return true;QueueDestroy(&q);
}int main()
{//ABD##E#H##CF##G##char arr[] = "ABD##E#H##CF##G##";int i = 0;BTNode* root = BinaryTreeCreate(arr, &i);BinaryTreePrevOrder(root);printf("\\n");BinaryTreeInOrder(root);printf("\\n");BinaryTreePostOrder(root);printf("\\n");int n = BinaryTreeSize(root);printf("%d\\n", n);int m = BinaryTreeLeafSize(root);printf("%d\\n", m);int a = BinaryTreeLevelKSize(root, 4);printf("%d\\n", a);//BTNode* ret = BinaryTreeFind(root, 7);//ret->_data *= 10;BinaryTreePrevOrder(root);printf("\\n");BinaryTreeLevelOrder(root);//BinaryTreePrevOrder(root);printf("%d\\n", BinaryTreeComplete(root));BinaryTreeDestory(root);return 0;
}

10.queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QNode* next;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);

11.queue.c

#include "queue.h"void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* del = cur;cur = cur->next;free(del);}pq->head = pq->tail = NULL;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}else{newnode->data = x;newnode->next = NULL;}if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* del = pq->head;pq->head = pq->head->next;free(del);}pq->size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL && pq->tail == NULL;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}