详解二叉树

一、树的概念和结构

树是⼀种非线性的数据结构，它是由 n（n>=0） 个有限结点组成⼀个具有层次关系的集合。把它叫做
树是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，而叶朝下的。
• 有⼀个特殊的结点，称为根结点，根结点没有前驱结点。
• 除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm ，其中每⼀个集合Ti(1 <= i <= m) ⼜是⼀棵结构与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱，可以有 0 个或多个后继。因此，树是递归定义的。

• 树形结构中，子树之间不能有交集，否则就不是树形结构。
• 除了根节点外，每个结点有且仅有一个父节点。
• 一棵N结点的树有N-1条边。

树的相关术语：

• 父节点/双亲结点：若一个结点含有子节点，则这个结点称为其子节点的父节点。
• 子结点/孩子结点：一个结点含有的子树的根节点称为该节点的子节点。
• 结点的度：一个结点有几个孩子，他的度就是多少。
• 树的度：一棵树中最大的结点的度称为树的度。
• 叶子结点/终端结点：度为0的结点称为叶子结点。
• 分支结点/非终端结点：度不为0的结点。
• 兄弟结点：具有相同父结点的结点称为兄弟结点。
• 结点的层次：从根开始定义起，根为第一层，根的子结点为第二层，以此类推。
• 树的高度或深度：树中结点的最大层次。
• 结点的祖先：从根到该结点所经分支上的所有结点。
• 路径：一条从树中任意结点出发，沿父结点-子结点连接，达到任意结点的序列。

树的表示

孩子兄弟表示法：
树结构相对线性表就比较复杂了，要储存表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际上树有很多种表示方式。这里我们就简单的了解其中最常用的孩子兄弟表示法：

struct TreeNode
{struct Node* child;  //左边开始的第一个孩子结点struct Node* brother;  //指向其右边的下一个兄弟结点int data;  //结点中的数据域
};

二、二叉树

二叉树不存在度大于2的结点
二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树、

特殊二叉树

满二叉树

一个二叉树如果每一层的结点数都达到最大值，则这个二叉树就是满二叉树。换句话说，如果一个二叉树的层数为k，则结点总数是2^k - 1，则它就是满二叉树。

完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。需要注意的是满二叉树是一种特殊的完全二叉树。

二叉树性质
根据满二叉树的特点可知：

1、若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点
2、若规定根结点的层数为1，则深度为h的二叉树的最大结点数是2^h - 1
3、若规定根结点的层数为1，具有n个结点的满二叉树的深度h=log以2为底（n+1)的对数

二叉树储存结构

二叉树一般可以使用两种结构储存，一种是顺序结构，一种是链式结构。

顺序结构

顺序结构储存就是使用数组来储存，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费，完全二叉树更适合使用顺序结构储存。

现实中我们通常把堆（是一种二叉树）使用顺序表结构的数组来储存，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

链式结构

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

三、实现顺序结构二叉树

一般堆使用顺序结构的数组来储存数据，堆是一种特殊的二叉树，具有二叉树的特性的同时，还具备其他的特性。

堆的概念和结构

如果有⼀个关键码的集合 K = {k0 , k1 , k2 , …，kn−1 } ，把它的所有元素按完全⼆叉树的顺序存储方式存储，在⼀个⼀维数中并满足： Ki <= K2∗i+1 （ Ki >= K2∗i+1 且 Ki <= K2∗i+2 ），i = 0、1、2… ，则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或⼤根堆，根结点最小的堆叫做最小堆或小根堆。

堆具有的特性
堆中某个结点的值总是不大于或不小于其父结点的值
堆总是一棵完全二叉树

二叉树特性

对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从0开始编号，则对于序号为i的结点有：
1、若i > 0，i位置结点的双亲序号：(i - 1)/2；i=0，i为根结点编号，无双亲结点。
2、若2i+1 < n,左孩子序号：2i+1,2i+1>=n否则无左孩子。
3、若2i+2<n,右孩子序号：2i+2,2i+2>=n否则无右孩子。

向上调整算法

堆的插入

在开始实现堆这个数据结构的同时我们要先来讲一下向上调整这个算法

将新数据插入到数组的尾上，再进行向上调整算法，直到满足堆。

• 先将元素插入到堆的末尾，即最后一个孩子之后
• 插入之后如果堆的性质遭到破坏，将新插入结点顺着其双亲往上调整到合适位置即可。

void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while(child > 0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}
}
void HPPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size-1);
}

向下调整算法

堆的删除

删除堆是删除堆顶的数据，将堆顶的数据跟最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

• 向下调整算法有一个前提：左右子树必须是一个堆才能调整。

将堆顶元素和堆中最后一个元素进行交换
删除堆中最后一个元素。
将堆顶元素向下调整到满足堆特性为止。

void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){// 假设法，选出左右孩⼦中⼩的那个孩⼦if (child+1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HPPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}

堆的实现

stack.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int STDataType;
//创建数组结构体
typedef struct Stack {STDataType* arr;int top;int capacity;
}ST;//初始化
void STInit(ST* ps);
//栈销毁
void STDestroy(ST* ps);//入栈
void StackPush(ST* ps, STDataType x);//判断栈是否为空
bool StackEmpty(ST* ps);
//出栈
void StackPop(ST* ps);//取栈顶数据
STDataType* StackTop(ST* ps);//获取栈的有效数据个数
STDataType* SizeTop(ST* ps);

stack.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"stack.h"//初始化
void STInit(ST* ps)
{assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;
}//栈销毁
void STDestroy(ST* ps)
{if (ps->arr != NULL){free(ps->arr);}ps->arr = NULL;ps->capacity = ps->top = 0;
}//入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);//空间不够if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}//判断栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出栈
void StackPop(ST* ps)
{assert(!StackEmpty(ps));--ps->top;
}//取栈顶元素
STDataType* StackTop(ST* ps)
{assert(ps);return ps->arr[ps->top - 1];
}//栈中有效数据个数
STDataType* SizeTop(ST* ps)
{assert(ps);return ps->top;
}

test,c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"stack.h"void test()
{//初始化ST st;STInit(&st);//入栈StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);//出栈/*StackPop(&st);StackPop(&st);StackPop(&st);StackPop(&st);*///出栈打印while (!StackEmpty(&st)){STDataType top = StackTop(&st);printf("%d ", top);StackPop(&st);}STDestroy(&st);
}int main()
{test();return 0;
}

四、实现链式结构二叉树

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

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

遍历规则

按照规则，二叉树有：前序遍历、中序遍历和后序遍历的递归结构遍历：

• 前序遍历：访问根节点的操作发生在遍历其左右子树之前

访问顺序是：根节点、左子树、右子树

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

• 中序遍历：访问根结点的操作发生在遍历其左右子树之中

访问顺序为：左子树、根节点、右子树

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

• 后序遍历：访问根节点的操作发生在遍历其左右子树之后

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

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

图解遍历：

• 层序遍历：
  除了前序遍历、中序遍历、后序遍历，还可以对二叉树进行层序遍历。假设二叉树的根结点所在的层数为1，层序遍历就是从所在二叉树的根结点出发，首先访问第一层的树根结点，然后从左到右访问第2层上的结点，接着是第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。需要注意的是层序遍历需要借助数据结构：队列。

void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);printf("%c ", top->data);QueuePop(&q);if (top->_left){QueuePush(&q, top->_left);}if (top->_right){QueuePush(&q, top->_right);}}QueueDesTroy(&q);
}

实现树

Tree.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>typedef char BTDatatype;
//创建一个二叉树的数据结构
typedef struct BinaryTreeNode {struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDatatype data;
}BTNode;//创建结点
BTNode* BTbuyNode( BTDatatype x);
//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);// ?叉树结点个数
int BinaryTreeSize(BTNode* root);
// ?叉树叶?结点个数
int BinaryTreeLeafSize(BTNode* root);
// ?叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//?叉树的深度/?度
int BinaryTreeDepth(BTNode* root);
// ?叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDatatype x);
// ?叉树销毁
void BinaryTreeDestory(BTNode** root);

Tree.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include "Tree.h"//创建结点
BTNode* BTbuyNode(BTDatatype x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->left = node->right = NULL;node->data = x;return node;
}//前序遍历(根左右）
void PreOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%c ", root->data);PreOrder(root->left);PreOrder(root->right);
}//中序遍历(左根右)
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}//后序遍历(左右根)
void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);
}// ?叉树结点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}// ?叉树叶?结点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}//左右孩子都为NULL则为叶子节点if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}// ?叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}//?叉树的深度/?度
int BinaryTreeDepth(BTNode* root)
{//二叉数的深度 == Max(左子树深度/右子树深度) + 1if (root == NULL){return 0;}return 1 + (BinaryTreeDepth(root->left) > BinaryTreeDepth(root->right) ? BinaryTreeDepth(root->left) : BinaryTreeDepth(root->right));
}// ?叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDatatype x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* LeftFind = BinaryTreeFind(root->left, x);if (LeftFind){return LeftFind;}BTNode* RightFind = BinaryTreeFind(root->right, x);if (RightFind){return RightFind;}
}// ?叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return 0;}BinaryTreeDestory(&(*root)->left);BinaryTreeDestory(&(*root)->right);free(*root);(*root) = NULL;
}

test.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include "Tree.h"BTNode* CreateTree()
{//手动创建二叉树BTNode* n1 = BTbuyNode('A');BTNode* n2 = BTbuyNode('B');BTNode* n3 = BTbuyNode('C');BTNode* n4 = BTbuyNode('D');BTNode* n5 = BTbuyNode('E');BTNode* n6 = BTbuyNode('F');BTNode* n7 = BTbuyNode('G');//连接各个节点n1->left = n2;n1->right = n3;n2->left = n4;n2->right = n5;n3->left = n6;n4->left = n7;//n1为根结点return n1;
}void test()
{BTNode* root = CreateTree();//前序遍历//PreOrder(root);//中序遍历//InOrder(root);//后序遍历//PostOrder(root);//二叉树节点个数int TreeSize = BinaryTreeSize(root);printf("二叉树节点个数：%d \n", TreeSize);//二叉树叶子节点个数int TreeLeafSize = BinaryTreeLeafSize(root);printf("二叉树叶子结点个数：%d \n", TreeLeafSize);//二叉树第k层结点的个数printf("二叉树第k层结点的个数：%d \n", BinaryTreeLevelKSize(root, 3));//二叉树的深度/高度printf("二叉树的深度/高度：%d \n", BinaryTreeDepth(root));//?叉树查找值为x的结点BTNode* find = BinaryTreeFind(&root, 'G');if (find){printf("二叉树里有这个值：%c!\n", find->data);}//二叉树的销毁BinaryTreeDestory(&root);
}int main()
{test();return 0;
}