树结构相对线性表更复杂，要存储表示起来就更麻烦，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。常用的是孩子兄弟表示法（也称左孩子右兄弟表示法）。
typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};
树在实际中的应用
文件系统的目录使用的就是树结构
二叉树的概念及结构 二叉树概念一棵二叉树是结点的一个有限集合，该集合满足:
（1）或者为空
（2）由一个根节点加上两棵别称为左子树和右子树的二叉树组成
从图中可以看出：
1. 二叉树不存在度大于2的结点 2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树 满二叉树一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为k，且结点总数是 ，则它就是满二叉树。
完全二叉树完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
二叉树的性质1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有个结点.
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是.
3. 对任何一二叉树, 如果度为0的叶结点个数为 , 度为2的分支结点个数为 ,则有
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，(log以2为底，n+1为对数)。
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
（1）若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
（2）若2i+1
（3）若2i+2
二叉树性质笔试题：
1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（） A 不存在这样的二叉树 B 200 C 198 D 199 答案为B，n0表示度为0的节点个数，n1表示度为1的节点个数，n2表示度为2的节点个数。则有n0 = n2+1，n2=199，n0=200 2.下列数据结构中，不适合采用顺序存储结构的是（） A 非完全二叉树 B 堆 C 队列 D 栈 答案为B，非完全二叉树即除了最后一层叶子节点之外，其他层的节点有孩子为空的情况，如下图所示，如果采用顺序存储，那么空出来的两个节点就要存储为NULL，顺序表就不连续了
3.在具有 2n 个结点的完全二叉树中，叶子结点个数为（） A n B n+1 C n-1 D n/2 答案为A，完全二叉树中，n1的个数要么为0要么为1： n0+n1+n2 = 2n n0+n1+n0-1=2n 2n0+(n1-1)=2n，为了保证等号左右两边值都为偶数，那么n1-1=0 则n0=n 4.4.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（） A 11 B 10 C 8 D 12 答案为B，2^k-1>=531,k=10 5.一个具有767个节点的完全二叉树，其叶子节点个数为（） A 383 B 384 C 385 D 386 答案为B， n0+n1+n2 =767 n0+n1+n0-1=767 2n0+n1-1=767 2n0+n1=768 , 为了保证等号左右两边值都为偶数，那么n1=0 则n0=384二叉树的存储结构
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
（1）顺序结构
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中只有堆才会使用数组来存储，二叉树顺序存储在物理上是一个数组，在逻辑上是一棵二叉树（堆的相关概念及实现请查看）。
二叉树的顺序结构的实现请查看文章【数据结构】堆-C语言版
（2）链式存储
完全二叉树和普通二叉树可以用链表来表示，即用链来指示元素的逻辑关系：链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所 在的链结点的存储地址 。链式结构又分为二叉链和三叉链，AVL树和红黑树等会用到三叉链。 二叉树的遍历二叉树共有4种遍历方式：
深度优先遍历有3种：
(1) 前序遍历(先根遍历) 根->左->右 A B D NULL NULL NULL C E NULL NULL F NULL NULL
(2) 中序遍历(中根遍历) 左->根->右 NULL D NULL B NULL A NULL E NULL C NULL F NULL
(3) 后序遍历(后根遍历) 左->右->根 NULL NULL D NULL B NULL NULL E NULL NULL F C A
广度优先遍历有1种：
(4) 层序遍历 一层一层遍历 A B C D NULL E F NULL NULL NULL NULL NULL NULL
使用队列进行广度优先遍历的过程：
另外，普通二叉树增删改查没有意义如果是为了存储数据，应该用线性表更简单， 用二叉树反而复杂了，并且插入删除还不好定义在哪个位置进行插入删除。排序二叉树的增删改查才有意义，如如下搜索二叉树，左边比父亲小，右边比父亲大：
查找时，每次都和根节点比较，如果比根节点小，就去左子树查找，否则去右子树查找，最多查找高度次，因此查找的时间复杂度为O(N)。极端情况下，效率会退化成O(N)，和链表差不多，可以用AVL树，红黑树，平衡树来解决。
因此二叉树实现先序、中序、后序、层序遍历 ，不需要实现增删改
二叉树的遍历代码040-Queue.h修改为如下：040-Queue.c见【数据结构】队列-C语言版
#pragma once #include#include #include #include //加入树节点的前置声明，队列的节点变成树，而非原来的int struct BinaryTreeNode; typedef struct BinaryTreeNode* QDataType; //typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QueueNode; typedef struct Queue { QueueNode* head; QueueNode* tail; }Queue; //初始化 void QueueInit(Queue* pq); //销毁 void QueueDestroy(Queue* pq); //插入数据 void QueuePush(Queue* pq, QDataType x); //删除数据 void QueuePop(Queue* pq); //取队头数据 QDataType QueueFront(Queue* pq); //取队尾数据 QDataType QueueRear(Queue* pq); //判断队是否已满 bool QueueEmpty(Queue* pq); //求队列元素个数 int QueueSize(Queue* pq);
046-BinaryTree.h
#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include#include #include #include "040-Queue.h" typedef char BTDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNode* right; BTDataType data; }BTNode; //创建结点 BTNode* CreateTreeNode(BTDataType x); //先序遍历 void PreOrder(BTNode* root); //中序遍历 void InOrder(BTNode* root); //后序遍历 void PostOrder(BTNode* root); //求结点个数思路一 void TreeSize1(BTNode* root,int* psize); //求结点个数思路二 int TreeSize2(BTNode* root); //求叶子结点个数 int TreeLeafSize(BTNode* root); //求树的高度 int TreeDepth(BTNode* root); //求第k层结点个数 int TreeKLeafSize(BTNode* root,int k); //查找树中值为x的节点 BTNode* TreeFind(BTNode* root, BTDataType x); //二叉树销毁一级指针 void BinaryTreeDestroy1(BTNode* root); //二叉树销毁二级指针 void BinaryTreeDestroy2(BTNode** root); //广度优先遍历：1.根入队 2.出队头，把队头的孩子入队 //A入队，A出队，BC入队，B出队，D入队，C出队，EF入队，E出队，F出队 //广度优先遍历，需在上篇文章【数据结构】队列-C语言版的040-Queue.h开头加入树节点的前置声明：见040-Queue.h void TreeLevelOrder(BTNode* root); //判断二叉树是否是完全二叉树 bool BinaryTreeComplete(BTNode* root);
046-BinaryTree.c
#include"046-BinaryTree.h"
//创建结点
BTNode* CreateTreeNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
node->data = x;
node->left = NULL;
node->right = NULL;
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);
}
//求结点个数，思路一：遍历计数的方式
void TreeSize1(BTNode* root,int* psize)
{
if (root == NULL)
{
return;
}
(*psize)++;
TreeSize1(root->left, psize);
TreeSize1(root->right, psize);
}
//求结点个数思路二，先序遍历（1+左树结点个数+右树结点个数）
int TreeSize2(BTNode* root)
{
return root == NULL ? 0 : TreeSize2(root->left) + TreeSize2(root->right) + 1;
}
//求叶子结点个数
int TreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
//求树的高度
int TreeDepth(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return fmax(TreeDepth(root->left), TreeDepth(root->right)) + 1;
}
//求第k层结点个数
int TreeKLeafSize(BTNode* root,int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return TreeKLeafSize(root->left, k - 1) + TreeKLeafSize(root->right, k - 1);
}
//查找树中值为x的节点
BTNode* TreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
//自己不是
if (root->data == x)
{
return root;
}
//到左子树中去找
BTNode* lret = TreeFind(root->left, x);
if (lret)
{
return lret;
}
//到右子树中去找
BTNode* rret = TreeFind(root->right, x);
if (rret)
{
return rret;
}
//左右两边都没有找到
return NULL;
}
//二叉树销毁一级指针
void BinaryTreeDestroy1(BTNode* root)
{
if (root == NULL)
{
return;
}
BinaryTreeDestroy1(root->left);
BinaryTreeDestroy1(root->right);
free(root);
}
//二叉树销毁二级指针
void BinaryTreeDestroy2(BTNode** pproot)
{
if (*pproot == NULL)
{
return;
}
BinaryTreeDestroy2(&(*pproot)->left);
BinaryTreeDestroy2(&(*pproot)->right);
free(*pproot);
*pproot = NULL;
}
//广度优先遍历
void TreeLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);
//入根结点
if (root)
{
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);
}
}
QueueDestroy(&q);
}
//判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
if (root)
{
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))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front)
{
return false;
}
}
QueueDestroy(&q);
return true;
}
046-test.c
#include"046-BinaryTree.h"
int main()
{
BTNode* A = CreateTreeNode('A');
BTNode* B = CreateTreeNode('B');
BTNode* C = CreateTreeNode('C');
BTNode* D = CreateTreeNode('D');
BTNode* E = CreateTreeNode('E');
BTNode* F = CreateTreeNode('F');
A->left = B;
A->right = C;
B->left = D;
C->left = E;
C->right = F;
//先序遍历
PreOrder(A);//递归：1.子问题（根 左子树 右子树） 2.结束条件
printf("n");
//中序遍历
InOrder(A);
printf("n");
//后序遍历
PostOrder(A);
printf("n");
//求结点个数思路一调用
int size = 0;
TreeSize1(A, &size);
printf("TreeSize = %dn", size);
//求结点个数思路二调用
printf("TreeSize = %dn", TreeSize2(A));
//求叶子结点个数
printf("TreeLeafSize = %dn", TreeLeafSize(A));
//求树的高度
printf("TreeDepth = %dn", TreeDepth(A));
//第K层结点个数
printf("TreeKLeafSize = %dn", TreeKLeafSize(A, 3));
//查找结点
BTNode* ret = TreeFind(A, 'F');
printf("TreeFind = %cn", ret->data);
//层序遍历
TreeLevelOrder(A);
printf("n");
//判断二叉树是不是完全二叉树
printf("%d", BinaryTreeComplete(A));
//二叉树销毁一级指针
//BinaryTreeDestroy1(A);
//A = NULL;
//二叉树销毁二级指针
BinaryTreeDestroy2(&A);
return 0;
}
代码运行结果如下：
先序遍历的递归调用过程
中序遍历的递归调用过程
后序遍历的递归调用过程
二叉树应用1.单值二叉树 OJ链接
分析：判断所有节点的值是否相等，当根值等于左孩子的值并且根值等于右孩子的值时，需要递归判断左子树的根值是否等于其左孩子的值并且左子树的根值等于其右孩子的值，并且需要递归判断右子树的根值是否等于其左孩子的值并且右子树的根值等于其右孩子的值······
bool isUnivalTree(struct TreeNode* root){
if(root == NULL)
{
return true;
}
if((root->left) && (root->left->val != root->val))
{
return false;
}
if((root->right) && (root->right->val != root->val))
{
return false;
}
return isUnivalTree(root->left) && isUnivalTree(root->right);
}
2.二叉树的前序遍历 OJ链接
分析：要求返回数组必须是malloc的，但是需要malloc多大的空间呢？malloc树的结点总数个空间，因此要
（1）求树的节点个数
（2）递归遍历整棵树，将根节点存到数组中
//求树的大小
int TreeSize(struct TreeNode* root)
{
return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
void _preorder(struct TreeNode* root,int * arr,int* pi)
{
if(root == NULL)
{
return;
}
//将根节点保存起来
arr[(*pi)++] = root->val;
_preorder(root->left,arr,pi);
_preorder(root->right,arr,pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
*returnSize = TreeSize(root);
//申请树的节点个数大小空间
int* arr = (int*)malloc(sizeof(int)*(*returnSize));
int i = 0;
_preorder(root,arr,&i);
return arr;
}
3.相同的树 OJ链接
分析：需要结构相同且结点有相同的值
（1）结构相同可以用递归遍历左右子树的根节点是否存在来判断
（2）值是否相同可以用递归遍历左右子树的根节点值是否相等来判断
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
//左右子树都为空
if((p == NULL) && (q == NULL))
{
return true;
}
//左子树为空，右子树不为空
if((p == NULL) && (q != NULL))
{
return false;
}
//左子树不为空，右子树为空
if((p != NULL) && (q == NULL))
{
return false;
}
//左右子树都不为空
if((p != NULL) && (q != NULL))
{
if(p->val == q->val)
{
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
}
return false;
}
4.对称二叉树 OJ链接
分析：
（1）判断二叉树是否对称，需要判断左孩子和右孩子的结点值是否相等，就需要递归判断左孩子的左孩子值和右孩子的右孩子值是否相等······
（2）给出的函数只有一个入参，需要判断左右孩子值是否相等，最好重新写一个函数，同时入参左右结点
bool _isSymmetric(struct TreeNode* left,struct TreeNode* right)
{
if(left == NULL && right == NULL)
{
return true;
}
if(left == NULL && right != NULL)
{
return false;
}
if(left != NULL && right == NULL)
{
return false;
}
if(left->val == right->val)
{
return _isSymmetric(left->left,right->right) && _isSymmetric(left->right,right->left);
}
return false;
}
bool isSymmetric(struct TreeNode* root) {
if(root == NULL)
{
return true;
}
return _isSymmetric(root->left,root->right);
}
5.平衡二叉树 OJ链接
方法一：
（1）求出左右子树的高度，如果高度差<=1，则是平衡二叉树
（2）平衡二叉树要求以每个结点为根的子树都是平衡的，因此要递归判断每个子结点是否是平衡的
int TreeDepth(struct TreeNode* root)
{
if(root == NULL)
{
return 0;
}
return fmax(TreeDepth(root->left),TreeDepth(root->right))+1;
}
bool isBalanced(struct TreeNode* root) {
if(root == NULL)
{
return true;
}
return fabs(TreeDepth(root->left)-TreeDepth(root->right)) < 2
&&isBalanced(root->left)
&&isBalanced(root->right);
}
方法二：判断左子树是否平衡的同时判断右子树是否平衡，同时把高度带给上一层父亲，让父亲计算父亲为根节点的子树高度
bool _isBalanced(struct TreeNode* root,int* ph)
{
if(root == NULL)
{
*ph = 0;
return true;
}
//后序
//先判断左子树，再判断右子树
int leftHeight= 0;
if(_isBalanced(root->left,&leftHeight) == false)
{
return false;
}
int rightHeight = 0;
if(_isBalanced(root->right,&rightHeight) == false)
{
return false;
}
//同时再把高度带给上一层父亲
*ph = fmax(leftHeight,rightHeight) + 1;
return abs(leftHeight - rightHeight) < 2;
}
bool isBalanced(struct TreeNode* root) {
int height = 0;
return _isBalanced(root,&height);
}
6.另一棵树的子树 OJ链接
分析：（1）遍历root的每个结点，每个结点做根和subRoot比较是否相等
（2）如何判断树相等，前面已经已经有代码
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
//左右子树都为空
if((p == NULL) && (q == NULL))
{
return true;
}
//左子树为空，右子树不为空
if((p == NULL) && (q != NULL))
{
return false;
}
//左子树不为空，右子树为空
if((p != NULL) && (q == NULL))
{
return false;
}
//左右子树都不为空
if((p != NULL) && (q != NULL))
{
if(p->val == q->val)
{
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
}
return false;
}
bool isSubtree(struct TreeNode* root,struct TreeNode* subRoot) {
//遍历root的每个结点，每个结点做子树的根和subRoot比较是否相等
if(root == NULL)
{
return false;
}
//每个结点作为子树根和subRoot进行比较
if(isSameTree(root,subRoot))
{
return true;
}
return isSubtree(root->left,subRoot)
|| isSubtree(root->right,subRoot);
}
7.二叉树遍历 OJ链接
分析：
(1)构建树:遇到#就忽略跳到下一个字符，递归构建左右子树
(2)中序遍历
#include#include typedef struct TreeNode { struct TreeNode* left; struct TreeNode* right; char val; }TreeNode; TreeNode* CreateTree(char* str, int* pi) { if (str[*pi] == '#') { ++(*pi); return NULL; } //不是#，构造根 TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); if (root != NULL) { root->val = str[*pi]; ++(*pi); } //递归构建左子树 root->left = CreateTree(str, pi); //递归构建右子树 root->right = CreateTree(str, pi); return root; } void Inorder(TreeNode* root) { if (root == NULL) { return; } Inorder(root->left); printf("%c ", root->val); Inorder(root->right); } int main() { char str[100]; scanf("%s", str); int i = 0; TreeNode* root = CreateTree(str, &i); Inorder(root); printf("n"); return 0; }
