【数据结构】——链式二叉树

一、链式二叉树的定义结构

二、链式二叉树的遍历

2.1前序遍历

2.2中序遍历

2.3后序遍历

2.4层序遍历

三、链式二叉树的基本功能函数

3.1结点个数

3.2叶子结点个数

3.3二叉树第k层结点个数

3.4查找值为x的结点

3.5二叉树的销毁

四、基础OJ

4.1二叉树遍历

4.2左叶子的和

4.3翻转二叉树

一、链式二叉树的定义结构

<1>二叉树的结构体包含了数据和指向左右子树的指针

typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;}BTNode;

<2>二叉树结点的创建

BTNode* BuyNode(BTDataType x)
{BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc fail");return NULL;}root->data = x;root->left = NULL;root->right = NULL;return root;
}

<3>二叉树的创建

BTNode* CreatBinaryTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}

Tip：二叉树是递归定义的，都可以单独看作根、左子树、右子树

二、链式二叉树的遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的结点进行相应的操作，并且每个结点只操作一次。访问结点所做的操作依赖于具体的应用问题。

遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

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

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

2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。

3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

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

2.1前序遍历

前序遍历就是按照根、左子树、右子树的顺序实现遍历

然后左、右子树又按照新的树继续递归下去

值得注意的是不能忘记 3 这个叶子二叉树它的左子树右子树均为空但是也是需要访问的

代码实现：

<1>树为空 return结束

<2>树不为空访问结点，递归左子树、右子树

void PrevOrder(BTNode*root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);//根PrevOrder(root->left);//左子树PrevOrder(root->right);//右子树
}

逻辑分析过程：

逻辑上将一颗树的前序遍历分为根的访问和左子树的遍历和右子树的遍历。
左右子树的遍历又看成新的一棵树整体的前序遍历。所以我们递归左右子树即可。

物理过程：

函数的调用会创建函数栈帧空间

2.2中序遍历

对比前序遍历都是整体式的递归访问但是中序遍历顺序为左子树、根、右子树

代码实现：

void InOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}InOrder(root->left);//左子树printf("%d ", root->data);//根InOrder(root->right);//右子树
}

可以看到这里的访问就是打印数据前序遍历根的访问在前（因为是根左子树右子树）而中序遍历先递归到最小的整体单元（左子树根右子树）

2.3后序遍历

与前中序遍历同理，顺序为左子树右子树根

代码实现：

void PostOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}PostOrder(root->left);//左子树PostOrder(root->right);//右子树printf("%d ", root->data);///根
}

验证一下数据

2.4层序遍历

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

分析：

代码实现：

void TreeLvelOrder(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);}QueueDestory(&q);
}

BFS：广度优先遍历（层序遍历）

DFS：深度优先遍历（前中后序遍历）

三、链式二叉树的基本功能函数

3.1结点个数

<1>遍历二叉树 size++

static int size = 0;
int BinaryTreeSize1(BTNode* root)
{if (root == NULL)return 0;size++;BinaryTreeSize1(root->left);BinaryTreeSize1(root->right);return size;
}

定义全局静态的size，遍历不为空++，缺点调用必须置零size 过于繁琐

<2>分治递归思想拆成若干个单元整体

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

3.2叶子结点个数

叶子结点的特征左右子树为空 return 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);
}

3.3二叉树第k层结点个数

分析：如何找到返回条件和子问题呢？

int BinaryTreeLevelKSize(BTNode* root, int k)
{//返回条件if (root == NULL||k==0)return 0;if (k == 1)return 1;//子问题return BinaryTreeLevelKSize(root->left, k - 1) +BinaryTreeLevelKSize(root->right, k - 1);
}

3.4查找值为x的结点

找到了值为x的结点，需要层层返回给上一层

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->data == x)return root;//记录找到的值防止重复调用BTNode* ret1 = BinaryTreeFind(root->left, x);if (ret1)return ret1;BTNode* ret2 = BinaryTreeFind(root->right, x);if (ret2)return ret2;return NULL;
}

递归展开图：

3.5二叉树的销毁

树的销毁也是递归销毁的仍然是按照若干个整体单元递归销毁，但是防止找不到左、右子树所以采用后序遍历的思想（左子树右子树根）

void BinaryTreeDestory(BTNode* root)
{if (root == NULL)return;BinaryTreeDestory(root->left);//左子树的销毁BinaryTreeDestory(root->right);//右子树的销毁free(root);//根的销毁
}

四、基础OJ

4.1二叉树遍历

二叉树遍历_牛客题霸_牛客网

思路分析：

题目要求我们前序遍历字符串构建一个二叉树，之后中序遍历打印数据

我们按照前序思路遍历（根，左子树，右子树）

<1>遇到 # return NULL

<2>非空 malloc结点记录当前字符

<3>递归遍历实现

#include <stdio.h>
typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;}BTNode;
BTNode*CreateTree(char*a,int*pi)
{if(a[*pi]=='#'){(*pi)++;return NULL;}BTNode*root=(BTNode*)malloc(sizeof(BTNode));root->data=a[(*pi)++];//访问根root->left=CreateTree(a,pi);//构建左子树root->right=CreateTree(a, pi);//构建右子树return root;
}
void InOrder(BTNode* root)
{if (root == NULL){return;}InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}
int main() {char a[100];int i=0;scanf("%s",a);BTNode*root= CreateTree(a, &i);InOrder(root);return 0;
}

注意：需要同时遍历数组和递归遍历构建二叉树，遍历数组时，如果字符为 # 变量 i 也是需要++的

4.2左叶子的和

. - 力扣（LeetCode）

思路分析：

求的是左子叶的和

<1>保证是左叶子结点

<2>记录左叶子的数值

<3>递归方法返回子树左叶子结点和

int dfs(struct TreeNode* root)
{int sum=0;//记录求和数值if(root==NULL)return 0;if(root->left!=NULL)//保证左叶子{if(root->left->left==NULL&&root->left->right==NULL)//保证叶子结点{sum+=root->left->val;//加左叶子数值}}//dfs遍历sum+=dfs(root->left);//遍历左子树sum+=dfs(root->right);//遍历右子树return sum;
}int sumOfLeftLeaves(struct TreeNode* root){return dfs(root);
}

4.3翻转二叉树

. - 力扣（LeetCode）

思路分析：

dfs遍历最小的整体单元（根，左子树，右子树）

先叶子结点开始翻转交换，然后左子树，右子树交换

struct TreeNode* invertTree(struct TreeNode* root) {if (root == NULL) {return NULL;}struct TreeNode* left = invertTree(root->left);struct TreeNode* right = invertTree(root->right);root->left = right;root->right = left;return root;
}