【数据结构】二叉树链式结构详解

发布时间：2024年01月09日

1.前言

前面我们已经讲过二叉树的概念及堆的实现，而我们所学的堆其实只是二叉树的顺序结构实现，当然堆的实现只能适用于完全二叉树或者满二叉树，但如果不是完全二叉树或者满二叉树这样的结构呢？那么就必须要谈一谈二叉树的链式结构的实现了，接下来我们将对递归有着更深层次的去理解，准备好小本本吧！

2.快速创建一颗二叉树

在学习二叉树的基本操作前，需要先创建一棵二叉树，然后才能学习其相关的基本操作。
由于现在大家对二叉树结构掌握还不够深入，为了降低学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。
下面看代码：

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

TreeNode* BuyTreeNode(int x)
{
	TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
	assert(node);

	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

TreeNode* CreateTree()
{
	TreeNode* node1 = BuyTreeNode(1);
	TreeNode* node2 = BuyTreeNode(2);
	TreeNode* node3 = BuyTreeNode(3);
	TreeNode* node4 = BuyTreeNode(4);
	TreeNode* node5 = BuyTreeNode(5);
	TreeNode* node6 = BuyTreeNode(6);
	TreeNode* node7 = BuyTreeNode(7);


	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	node5->right = node7;

	return node1;
}

注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式后序详解重点讲解。

在开始二叉树的基本操作前，先回顾一下我们二叉树的概念，二叉树：

空树
非空：跟节点，根节点的左子树，根节点的右子树组成的。

所以说二叉树可以更好的理解递归，二叉树的概念就说明二叉树是递归式的，二叉树的基本操作都是递归式的。
上面我们创建的二叉树加了一个新节点，便于后面的理解。

3.二叉树的遍历

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

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

前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

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

忘了更便于我们理解，我们把空也打印出来，下面就是这几种遍历方式。

3.1前序遍历

前序遍历就是
分治思想：根左子树右子树
根据这个思想进行遍历得到前序序列。
代码实现：

void PrevOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

前序遍历结果：1 2 3 N N N 4 5 N 7 N N 6 N N

3.2中序遍历

中序遍历就是
分治思想：左子树根右子树
根据这个思想进行遍历得到中序序列。
代码实现：

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

中序遍历结果：N 3 N 2 N 1 N 5 N 7 N 4 N 6 N

3.3后序遍历

后序遍历就是
分治思想：左子树右子树根
根据这个思想进行遍历得到后序序列。
代码实现：

void BackOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	BackOrder(root->left);
	BackOrder(root->right);
	printf("%d ", root->data);

后序遍历结果：N N 3 N 2 N N N 7 5 N N 6 4 1

3.4层序遍历

层序遍历有两个版本，版本一可是直接遍历一遍二叉树并打印一行，
而版本二可以分层进行打印，一层一层的打印出数据。
对于层序遍历中的队列的使用，可以去搬来我之前写的栈和队列那一节内容的代码。
版本一:

void BinaryTreeLevelOrder(TreeNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q,root);
	while (!QueueEmpty(&q))
	{
		TreeNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);

		if (front->left)
			QueuePush(&q,front->left);
		if (front->right)
			QueuePush(&q,front->right);
	}
	QueueDestroy(&q);
}

版本二：

void BinaryTreeLevelOrder(TreeNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	int levelSize = 1;
	while (!QueueEmpty(&q))
	{
		while (levelSize--)
		{
			TreeNode* 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");

		levelSize = QueueSize(&q);
	}
	QueueDestroy(&q);
}

4.二叉树节点个数与高度

4.1二叉树节点个数

int TreeSize(TreeNode* root)
{
	return root == NULL ? 0 : 
		TreeSize(root->left) + 
		TreeSize(root->right) + 1;
}

4.2二叉树叶子节点个数

int BinaryTreeLeaf(TreeNode* root)
{
	//空树 返回0
	if (root == NULL)
		return 0;

	//左子树为空，右子树为空 是叶子，返回1
	if (!root->left && !root->right)
		return 1;
	//递归遍历，不是空也不是叶子，分治左右子树之和
	return BinaryTreeLeaf(root->left) + BinaryTreeLeaf(root->right);
}

4.3二叉树高度

int TreeHeight(TreeNode* root)
{
	if (root == NULL)
		return 0;
	return fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1;
}

一道Leetcode的一道题。
求二叉树的深度OJ链接
解题代码：

int maxDepth(struct TreeNode* root) {
	if (root == NULL)
		return 0;
	int LeftHeight = maxDepth(root->left);
	int RightHeight = maxDepth(root->right);

	return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;
}

4.4二叉树第k层节点个数

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

4.5二叉树查找值为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;
}

5.二叉树的基础oj题练习

单值二叉树。OJ链接

bool isUnivalTree(struct TreeNode* root) {
    if(root == NULL)
        return true;
    if(root->left && root->val != root->left->val)
        return false;
    if(root->right && root->val != root->right->val)
        return false;
    return isUnivalTree(root->left) 
            && isUnivalTree(root->right);
}

检查两颗树是否相同。OJ链接

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    //均为空
    if(p == NULL && q == NULL)
        return true;
    //有一个为空
    if(p == NULL || q == NULL)
        return false;
    //都不为空且不相等
    if(p->val != q->val)
        return false;
        return isSameTree(p->left,q->left)
                && isSameTree(p->right,q->right);
}

对称二叉树。OJ链接

 bool _isSymmetric(struct TreeNode* root1, struct TreeNode* root2) {
     //都为空
     if(root1 == NULL && root2 == NULL)
     {
         return true;
     }
     //其中一个为空
     if(root1 == NULL || root2 == NULL)
     {
         return false;
     }
     //都不为空
     if(root1->val != root2->val)
     {
         return false;
     }
     return _isSymmetric(root1->left,root2->right)
            && _isSymmetric(root1->right,root2->left);
}
bool isSymmetric(struct TreeNode* root) {
    return _isSymmetric(root->left, root->right);
}

二叉树的前序遍历。 OJ链接

 int TreeSize(struct TreeNode* root)
 {
     return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
 }
int* pre_order(struct TreeNode* root, int* a, int* pi)
{
    if(root == NULL)
        return NULL;
    a[(*pi)++] = root->val;
    pre_order(root->left,a,pi);
    pre_order(root->right,a,pi);
    return a;
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int n = TreeSize(root);
    int* a = (int*)malloc(sizeof(int)*n);
    *returnSize = n;
    int i = 0;
    return pre_order(root, a,&i);
}

二叉树中序遍历。OJ链接

 int TreeSize(struct TreeNode* root)
 {
     return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
 }
 int* inorder(struct TreeNode* root, int* s, int* pi)
 {
     if(root == NULL)
         return NULL;
     inorder(root->left,s,pi);
     s[(*pi)++] = root->val;
     inorder(root->right,s,pi);
     return s;
 }
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int n = TreeSize(root);
    int* s = (int*)malloc(sizeof(int)*n);
    *returnSize = n;
    int i = 0;
    return inorder(root,s,&i);
}

二叉树的后序遍历。OJ链接

int TreeSize(struct TreeNode* root)
 {
     return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
 }
 int* postorder(struct TreeNode* root, int* s, int* pi)
 {
     if(root == NULL)
         return NULL;
     postorder(root->left,s,pi);
     postorder(root->right,s,pi);
     s[(*pi)++] = root->val;
     return s;
 }
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    int n = TreeSize(root);
    int* s = (int*)malloc(sizeof(int)*n);
    *returnSize = n;
    int i = 0;
    return postorder(root,s,&i);
}

另一颗树的子树。OJ链接

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    if(p == NULL && q == NULL)
        return true;
    if(p == NULL || q == NULL)
        return false;
    if(p->val != q->val)
        return false;
    return isSameTree(p->left,q->left)
            && isSameTree(p->right,q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root == NULL)
        return false;
    if(root->val == subRoot->val)
    {
        if(isSameTree(root,subRoot))
        {
            return true;
        }
    }
    return isSubtree(root->left,subRoot)
            || isSubtree(root->right,subRoot);
}

6.二叉树的创建和销毁

二叉树的构建及遍历。OJ链接

#include <stdio.h>
#include<stdlib.h>

struct TreeNode
{
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
};
struct TreeNode* CreatBinaryTree(char* s, int* pi)
{
    if(s[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    
    root->val = s[(*pi)++];
    root->left = CreatBinaryTree(s, pi);
    root->right = CreatBinaryTree(s, pi);
    return root;
}

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

int main() {
    char s[101];
    int i = 0;
    while(scanf("%s",s)!=EOF)
    {
        struct TreeNode* root = CreatBinaryTree(s,&i);
        InOrder(root);
    }

    return 0;
}

6.1通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树

分析：
根据前序遍历，特别要注意的是pi，控制的是数组的小标，传进来的是指针。

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)++];
	root->left = BinaryTreeCreate(a, pi);
	root->right = BinaryTreeCreate(a, pi);
	return root;
}

6.2二叉树销毁

分析：
使用后序遍历的方式来销毁。

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

6.3判断二叉树是否是完全二叉树

分析：
我们知道，如果一个二叉树是完全二叉树，那么在层序遍历时，当遍历到第一个空时，如果后面的内容仍然是空的，那么这个二叉树是完全二叉树，反之则不是。

bool BinaryTreeComplete(TreeNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		TreeNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
			break;
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	while (!QueueEmpty(&q))
	{
		TreeNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front)
			return false;
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	QueueDestroy(&q);
	return true;
}

文章来源:https://blog.csdn.net/2301_78611726/article/details/135474716
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！