一、基本概念
链式二叉树是一种常见的数据结构，它是用链表结点来存储二叉树中的每一个结点，结点结构通常包括数据域和若干个指针域。其中，指针域用于指向左孩子结点和右孩子结点。
对于那些非完全二叉树，由于顺序存储结构的空间利用率低，因此二叉树一般都采用链式存储结构。在链式二叉树中，根据指针的数量可以分为二叉链和三叉链两种结构。二叉链的结点包含存储数据的变量、存储左孩子的指针以及存储右孩子的指针；而三叉链的结点除了包含存储数据的变量、存储左孩子的指针以及存储右孩子的指针，还包含存储双亲的指针。
二叉树的遍历是指按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。根据访问根结点的顺序不同可以分为前序遍历、中序遍历和后序遍历。
链式存储概念
链式存储二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是 链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所 在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链。
二、链式二叉树的结构
链式二叉树结构
typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType _data; struct BinaryTreeNode* _left; struct BinaryTreeNode* _right; }BTNode;
构建链式二叉树
int类型 手撕构建方便前期调试
BTNode* BuyNode(BTDataType x) { BTNode* newnode = (BTNode*)malloc(sizeof(BTNode)); if (newnode == NULL) { perror("malloc err"); return NULL; } newnode->_data = x; newnode->_left = NULL; newnode->_right = NULL; return newnode; } //123nn4n5nn67nn8nn 通过前序遍历构建 BTNode* BinaryTreeCreate() { BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); BTNode* node7 = BuyNode(7); BTNode* node8 = BuyNode(8); node1->_left = node2; node1->_right = node6; node2->_left = node3; node2->_right = node4; node4->_right = node5; node6->_left = node7; node6->_right = node8; return node1; }
char数组类型
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树 BTNode* BinaryTreeCreateChar(BTDataType* a, int* pi) { if (a[(*pi)] == '#') { (*pi)++; return NULL; } BTNode* newnode = (BTNode*)malloc(sizeof(BTNode)); if (newnode == NULL) { perror("malloc err"); return NULL; } newnode->_data = a[(*pi)++]; newnode->_left = BinaryTreeCreateChar(a, pi); newnode->_right = BinaryTreeCreateChar(a, pi); return newnode; }
二叉树的遍历
前序：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
前序遍历递归图解：
// 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%d ", root->_data); BinaryTreePrevOrder(root->_left); BinaryTreePrevOrder(root->_right); }
中序：中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）
// 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } BinaryTreeInOrder(root->_left); printf("%d ",root->_data); BinaryTreeInOrder(root->_right); }
后序：后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后
// 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } BinaryTreePostOrder(root->_left); BinaryTreePostOrder(root->_right); printf("%d ",root->_data); }
层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在 层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层 上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
// 层序遍历 #include"Queue.h" void BinaryTreeLevelOrder(BTNode* root) { Queue q; QueueInit(&q); if (root) QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* Fout = QueueFront(&q); QueuePop(&q); printf("%d ",Fout->_data); if (Fout->_left) { QueuePush(&q,Fout->_left); } if (Fout->_right) { QueuePush(&q, Fout->_right); } } QueueDestroy(&q); }
判断二叉树是否是完全二叉树
// 判断二叉树是否是完全二叉树 bool BinaryTreeComplete(BTNode* root) { Queue q; QueueInit(&q); if (root) QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* Fout = QueueFront(&q); QueuePop(&q); if (Fout == NULL) { break; } QueuePush(&q, Fout->_left); QueuePush(&q, Fout->_right); } while (!QueueEmpty(&q)) { BTNode* Fout = QueueFront(&q); QueuePop(&q); if (root) { QueueDestroy(&q); return false; } } QueueDestroy(&q); return true; }
二叉树节点和高度等
1.二叉树节点个数
// 二叉树节点个数 int BinaryTreeSize(BTNode* root) { return root == NULL ? 0 : BinaryTreeSize(root->_left) + BinaryTreeSize(root->_left)+1; }
2.二叉树叶子节点个数
// 二叉树叶子节点个数 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.二叉树的最大高度
//二叉树的最大高度 int TreeHeight(BTNode* root) { if (root == NULL) return 0; int node_left=TreeHeight(root->_left); int node_right = TreeHeight(root->_right); return node_left > node_right ? node_left + 1 : node_right + 1; }
4.二叉树第k层节点个数
// 二叉树第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); }
5.二叉树查找值为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; }
二叉树销毁
// 二叉树销毁 void BinaryTreeDestory(BTNode** root) { if (*(root) == NULL) return; BinaryTreeDestory(&(*root)->_left); BinaryTreeDestory(&(*root)->_right); free(*(root)); }
三、链式二叉树的练习
相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
思路： 可以通过递归的方式同时遍历两棵树。
比较两棵树的根节点值是否相等，如果不相等则直接返回 false。
然后递归地对左子树和右子树分别进行相同的比较，只有当左右子树在相应位置上都相同的时候才返回 true。
在递归过程中，只要有一处不满足相同条件就可以立即返回 false，只有所有节点和结构都完全一致才能最终返回 true。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ 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); }
对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
思路：
采用递归的方法。
一个二叉树是轴对称的，意味着对于任意一个节点，它的左子树和右子树是镜像对称的。
具体来说，就是对于当前节点，它的左子节点和右子节点的值相等（如果都存在的话），并且左子节点的左子树和右子节点的右子树对称，左子节点的右子树和右子节点的左子树也对称。我们通过递归地比较左右子树的对应节点来判断整个二叉树是否对称。如果在递归过程中发现不满足对称条件的情况，就可以返回 false，如果递归完整棵树都满足，则返回 true。
* Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool _isSymmetric(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 _isSymmetric(p->left, q->right)&&_isSymmetric(p->right, q->left); } bool isSymmetric(struct TreeNode* root) { return _isSymmetric(root->left, root->right); }
另外一颗子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
思路
我们可以从根节点开始，对主树 root 进行先序遍历。
在遍历过程中，每当遇到一个节点，就判断以这个节点为根的子树是否与 subRoot 完全相同。
为了判断子树是否相同，可以编写一个辅助函数来比较两棵树是否完全一致，这与前面判断两棵树是否相同的思路类似，即同时递归地检查节点值以及左右子树的结构和节点值是否匹配。如果找到匹配的子树，就返回 true，否则继续遍历主树的其他节点。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ 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 && isSameTree(root,subRoot)) return true; return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot); }
二叉树前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
思路：
首先访问根节点，然后递归地对左子树进行前序遍历，最后递归地对右子树进行前序遍历。
具体来说，我们可以使用一个辅助函数，在这个函数中先输出当前节点的值，然后如果左子树存在就对左子树调用该函数进行递归遍历，接着如果右子树存在就对右子树调用该函数进行递归遍历。这样就可以按照前序遍历的顺序输出所有节点的值。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * Note: The returned array must be malloced, assume caller calls free(). */ int TreeSize(struct TreeNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; } void PrevOrder(struct TreeNode* root,int* a,int* i) { if(root==NULL) return; a[(*i)++]=root->val; PrevOrder(root->left,a,i); PrevOrder(root->right,a,i); } int* preorderTraversal(struct TreeNode* root, int* returnSize) { * returnSize=TreeSize(root); int* a=(int*)malloc(sizeof(int)*(*returnSize)); int i = 0; PrevOrder(root,a,&i); return a; }
二叉树遍历
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入描述：
输入包括1行字符串，长度不超过100。
输出描述：
可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。
思路：
1. 定义二叉树节点结构体：包含节点值以及左右子节点指针。
2. 构建二叉树函数：通过遍历输入的先序遍历字符串来构建二叉树。使用一个静态索引来跟踪当前处理的字符位置。如果遇到非'#'字符，就创建一个新节点，然后递归地构建左子树和右子树，遇到'#'则表示空节点。
3. 中序遍历函数：按照中序遍历的顺序（先左子树、当前节点、再右子树）输出节点值并添加空格。
4. 在主程序中，获取用户输入的字符串，调用构建二叉树函数得到二叉树，然后调用中序遍历函数输出结果。
#include<stdio.h> #include<stdlib.h> typedef struct Tree { struct Tree* le; struct Tree* ri; int val; } BTNode; void PrevInor(BTNode* root) { if (root == NULL) return; PrevInor(root->le); printf("%c ", root->val); PrevInor(root->ri); } BTNode* BUTree(char* a,int* pi) { if(a[*pi] =='#') { (*pi)++; return NULL; } BTNode* newnode=(BTNode*)malloc(sizeof(BTNode)); newnode->val=a[(*pi)++]; newnode->le=BUTree(a, pi); newnode->ri=BUTree(a, pi); return newnode; } int main() { char a[100]; scanf("%s",a); int i=0; BTNode* node=BUTree(a, &i); PrevInor(node); }
平衡二叉树
给定一个二叉树，判断它是否是
思路：
1. 定义一个函数来判断以某个节点为根的二叉树是否平衡。该函数需要接受节点指针和一个变量来存储当前节点的高度。
2. 对于空节点，直接返回true，因为空树是平衡的。
3. 否则，计算左子树和右子树的高度。
4. 比较左右子树的高度差，如果高度差的绝对值大于1，则返回false，表示二叉树不平衡。
5. 最后，递归地调用函数来判断左子树和右子树是否平衡，并将结果与当前节点的高度差进行比较。
6. 如果左子树和右子树都平衡，且高度差在允许范围内，则返回true，表示整个二叉树是平衡的。
int height(struct TreeNode* root) { if (root == NULL) { return 0; } else { return fmax(height(root->left), height(root->right)) + 1; } } bool isBalanced(struct TreeNode* root) { if (root == NULL) { return true; } else { return fabs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right); } }
四、完整代码
Tree.h
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType _data; struct BinaryTreeNode* _left; struct BinaryTreeNode* _right; }BTNode; // 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树 BTNode* BinaryTreeCreate();//BTDataType* a, int n, int* pi); // 二叉树销毁 void BinaryTreeDestory(BTNode** root); // 二叉树节点个数 int BinaryTreeSize(BTNode* root); // 二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root); // 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k); // 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x); // 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root); // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root); // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root); // 层序遍历 void BinaryTreeLevelOrder(BTNode* root); // 判断二叉树是否是完全二叉树 bool BinaryTreeComplete(BTNode* root); BTNode* BuyNode(BTDataType x); //求二叉树的最长高度 int TreeHeight(BTNode* root);
Tree.c
#define _CRT_SECURE_NO_WARNINGS #include"Tree.h" BTNode* BuyNode(BTDataType x) { BTNode* newnode = (BTNode*)malloc(sizeof(BTNode)); if (newnode == NULL) { perror("malloc err"); return NULL; } newnode->_data = x; newnode->_left = NULL; newnode->_right = NULL; return newnode; } /*int n,*/ // 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树 BTNode* BinaryTreeCreateChar(BTDataType* a, int* pi) { if (a[(*pi)] == '#') { (*pi)++; return NULL; } BTNode* newnode = (BTNode*)malloc(sizeof(BTNode)); if (newnode == NULL) { perror("malloc err"); return NULL; } newnode->_data = a[(*pi)++]; newnode->_left = BinaryTreeCreateChar(a, pi); newnode->_right = BinaryTreeCreateChar(a, pi); return newnode; } //123nn4n5nn67nn8nn BTNode* BinaryTreeCreate() { BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); BTNode* node7 = BuyNode(7); BTNode* node8 = BuyNode(8); node1->_left = node2; node1->_right = node6; node2->_left = node3; node2->_right = node4; node4->_right = node5; node6->_left = node7; node6->_right = node8; return node1; } // 二叉树销毁 void BinaryTreeDestory(BTNode** root) { if (*(root) == NULL) return; BinaryTreeDestory(&(*root)->_left); BinaryTreeDestory(&(*root)->_right); free(*(root)); } // 二叉树节点个数 int BinaryTreeSize(BTNode* root) { return root == NULL ? 0 : BinaryTreeSize(root->_left) + BinaryTreeSize(root->_left)+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) { 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* ret1 = BinaryTreeFind(root->_left, x); if (ret1) return ret1; BTNode* ret2 = BinaryTreeFind(root->_right, x); if (ret2) return ret2; return NULL; } // 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%d ", root->_data); BinaryTreePrevOrder(root->_left); BinaryTreePrevOrder(root->_right); } // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } BinaryTreeInOrder(root->_left); printf("%d ",root->_data); BinaryTreeInOrder(root->_right); } // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } BinaryTreePostOrder(root->_left); BinaryTreePostOrder(root->_right); printf("%d ",root->_data); } // 层序遍历 #include"Queue.h" void BinaryTreeLevelOrder(BTNode* root) { Queue q; QueueInit(&q); if (root) QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* Fout = QueueFront(&q); QueuePop(&q); printf("%d ",Fout->_data); if (Fout->_left) { QueuePush(&q,Fout->_left); } if (Fout->_right) { QueuePush(&q, Fout->_right); } } QueueDestroy(&q); } // 判断二叉树是否是完全二叉树 bool BinaryTreeComplete(BTNode* root) { Queue q; QueueInit(&q); if (root) QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* Fout = QueueFront(&q); QueuePop(&q); if (Fout == NULL) { break; } QueuePush(&q, Fout->_left); QueuePush(&q, Fout->_right); } while (!QueueEmpty(&q)) { BTNode* Fout = QueueFront(&q); QueuePop(&q); if (root) { QueueDestroy(&q); return false; } } QueueDestroy(&q); return true; } //二叉树的最大高度 int TreeHeight(BTNode* root) { if (root == NULL) return 0; int node_left=TreeHeight(root->_left); int node_right = TreeHeight(root->_right); return node_left > node_right ? node_left + 1 : node_right + 1; }
Queue.c(部分)
void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; pq->ptail = NULL; pq->size = 0; } void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->phead; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; } void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc err"); return; } newnode->data = x; newnode->next=NULL; if (pq->phead == NULL) { assert(pq->ptail == NULL); pq->phead = pq->ptail= newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->phead->next == NULL) { free(pq->phead); pq->phead = pq->ptail = NULL; } else { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; } QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->phead->data; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL && pq->ptail == NULL; }
五、总结
二叉树全面总结：
定义：
二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。
主要特点：
• 节点度最大为 2。
• 具有递归结构。
重要类型：
• 满二叉树：所有节点都有两个子节点，且叶子节点都在同一层。
• 完全二叉树：除了最后一层，其他层都是满的，最后一层的叶子节点靠左排列。
遍历方式：
• 前序遍历：先访问根节点，再遍历左子树，最后遍历右子树。
• 中序遍历：先遍历左子树，再访问根节点，最后遍历右子树。
• 后序遍历：先遍历左子树，再遍历右子树，最后访问根节点。
• 层次遍历：按照层次依次访问节点。
应用：
• 高效搜索和排序。
• 表达式树。
• 二叉堆实现优先队列等。
性质：
• 在完全二叉树中，节点编号与层次存在特定关系。
• 叶子节点数与度为 2 的节点数存在一定关系。
存储方式：
• 链式存储：通过节点指针连接。
• 数组存储：适用于完全二叉树。
常见算法：
• 构建二叉树。
• 求深度、高度。
• 查找节点。
• 平衡性判断及调整（如 AVL 树、红黑树等）。
二叉树是数据结构中的基础且重要部分，在计算机科学中有广泛的应用和研究价值。
