（二叉）树中，一个节点，你也要把他看做成树。子树。一个节点都没有叫做空树。所以说：树具有递归性。

树是非线性结构，有一个直接前驱，但是可能有很多直接后继。

树中，应用最多的还是二叉树。

二叉树的遍历

先（根）序遍历DLR，中（根）序遍历LDR，后（根）序遍历LRD。

无论哪种：首要顺序都是“先左后右”。

DLR先根序遍历：先序遍历，即先根再左再右。

LDR中根序遍历：中序遍历，即先左再根再右。

LRD后根序遍历：后序遍历，即先左再右再根。

说白了，就是说，你什么时候访问中间的根，如果先访问根，再左右，那么就是先序，把根放在中间，就是中序，如果先左后右最后跟，就是后序。

树是递归的，所以说上面的这个规则也是你递归的法则。

每次递归到一棵子树，规则仍然如此。

，

先序遍历：第一棵树是A，然后到第二棵树，B子树，B为先，然后左右，AB,CDE，FGH。

中序遍历：先左后中。中序先看左边，左边是B子树，B子树也要按照中序来。左边没有所以就到了中间，所以先是B，然后右边又是一棵树，也要按照中序来，所以是BDCE，然后左边完事了，到中间，BDCE然后A，到右边了，右边也要按照中序排序。F没有左，所以直接F，F完事到右边了，右边是棵子树，先左H后G，所以：BDCE,A,FHG

后序遍历：先左再右再根。根树的话，先B，但是B是子树，所以也要按照先左再右最后根的顺序。所以B子树，先左，左为空，所以到右，右边C是子树，所以先DE然后DEC。然后再DECB。左边子树完成了，看右边，右边也是一颗子树，所以继续递归。F左空，右子树，是HGF，最后是根节点A。DECB，HGF，A。

永远牢记一点：树是递归的，树遍历的递归法法则是有三种顺序，这三种方法也是递归的规则。

现在开始编程实现：

首先是定义二叉树数据结构：二叉树结构体

二叉树有两个节点，左节点和右节点。我们分别用指针来代替。

因为它是递归的，所以也是node节点。结构体嵌套自身。

struct BiNode
{char ch;struct BiNode *lchild;struct BiNode *rchild;
};

对树来说，拿到根节点，相当于拿到整个树。所以遍历时，只要输入根节点即可。

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#includestruct BiNode
{char ch;struct BiNode *lchild;struct BiNode *rchild;
};//二叉树递归遍历
void recursion(struct BiNode *root)
{if (NULL == root){return;}//递归遍历左子树recursion(root->lchild);//递归遍历右子树recursion(root->rchild);printf("%c ", root->ch);}void test()
{struct BiNode nodeA = { 'A', NULL, NULL };struct BiNode nodeB = { 'B', NULL, NULL };struct BiNode nodeC = { 'C', NULL, NULL };struct BiNode nodeD = { 'D', NULL, NULL };struct BiNode nodeE = { 'E', NULL, NULL };struct BiNode nodeF = { 'F', NULL, NULL };struct BiNode nodeG = { 'G', NULL, NULL };struct BiNode nodeH = { 'H', NULL, NULL };nodeA.lchild = &nodeB;nodeA.rchild = &nodeF;nodeB.rchild = &nodeC;nodeC.lchild = &nodeD;nodeC.rchild = &nodeE;nodeF.rchild = &nodeG;nodeG.lchild = &nodeH;recursion(&nodeA);}int main(){test();system("pause");return EXIT_SUCCESS;
}

递归的输出条件是什么呢？

二叉树的递归结束标识是左右递归子树为空。即可。

上面是后序遍历。我们把它改为中序。

//二叉树递归遍历
void recursion(struct BiNode *root)
{if (NULL == root){return;}//递归遍历左子树recursion(root->lchild);// 中序遍历printf("%c ", root->ch);//递归遍历右子树recursion(root->rchild);}

先序如下：

//二叉树递归遍历
void recursion(struct BiNode *root)
{if (NULL == root){return;}// 先序遍历printf("%c ", root->ch);	//递归遍历左子树recursion(root->lchild);//递归遍历右子树recursion(root->rchild);}

计算叶节点数

遍历需求如上完成。

涉及二叉树有时还需要输出叶节点数。

叶节点，就是左右节点都为空即可。上面我已经可以遍历了，所以，每一次遍历节点都看看其左右节点情况即可。如果为空则输出即可。

int num = 0;
void cuculateLeafNum(struct BiNode *root)
{if (NULL == root){return;}if (root->lchild == NULL && root->rchild == NULL){num++;}cuculateLeafNum(root->lchild);cuculateLeafNum(root->rchild);
}

还是输入根节点。相当于输入了整个树，然后逐级递归即可。

有一个问题，我们在实际编程中，很少使用全局变量num，因为就为一个功能，而引入一个全局变量看起来并不划算。所以为此，为此，我们采用指针的形式。

void cuculateLeafNum(struct BiNode *root,int *p)
{if (NULL == root){return;}if (root->lchild == NULL && root->rchild == NULL){(*p)++;}cuculateLeafNum(root->lchild, p);cuculateLeafNum(root->rchild, p);
}

在实际C语言编程中，尽量少使用全局变量。

求二叉树高度

 我们求A的高度，只要求出B子树，和F子树的高度加上1即可，也就是递归的话，我们把所有子树的高度加上1即是当前子树的高度。递归，就是一级级子树去计算高度，直到当前子树高度为1则终止。最后高度等于=MAX(左子树高度，右子树高度) + 1。

int getTreeHeight(struct BiNode *root)
{if (NULL == root){return 0;}//求树的左子树高度int lheight = getTreeHeight(root->lchild);//求树的右子树高度int rheight = getTreeHeight(root->rchild);int height = lheight > rheight ? lheight + 1 : rheight + 1;return height;
}

 递归终止条件为子树为空。

最后三目运算符输出高度。

int height = lheight > rheight ? lheight + 1 : rheight + 1;

二叉树的拷贝

拷贝肯定也是一个递归的过程；就是把所有层级的子树左右节点输出挂到新的根节点下面。

//先拷贝左子树
struct BiNode *lchild = copyBiTree(root->lchild);
//拷贝右子树
struct BiNode *rchild = copyBiTree(root->rchild);

因为最后需要输出一份新的二叉树，所以我们需要建立一个新的二叉树根节点。

struct BiNode *newnode = malloc(sizeof(struct BiNode));

先获取左右，然后挂到根节点下。最后返回根节点。

struct BiNode *copyBiTree(struct BiNode *root)
{if (NULL == root){return NULL;}//先拷贝左子树struct BiNode *lchild = copyBiTree(root->lchild);//拷贝右子树struct BiNode *rchild = copyBiTree(root->rchild);struct BiNode *newnode = malloc(sizeof(struct BiNode));newnode->lchild = lchild;newnode->rchild = rchild;newnode->ch = root->ch;return newnode;
}

查看二叉树

void showBiTree(struct BiNode *root)
{if (NULL == root){return;}printf("%c ",root->ch);showBiTree(root->lchild);showBiTree(root->rchild);
}

二叉树的内存释放

释放也是先左右子节点，然后根节点，因为如果先释放根节点，左右就找不到了，造成内存泄漏。

void freeSpace(struct BiNode *root)
{if (NULL == root){return;}//释放左子数内存freeSpace(root->lchild);//释放右子树freeSpace(root->rchild);printf("%c 被释放!\n", root->ch);free(root);
}

测试代码 

void test()
{struct BiNode nodeA = { 'A', NULL, NULL };struct BiNode nodeB = { 'B', NULL, NULL };struct BiNode nodeC = { 'C', NULL, NULL };struct BiNode nodeD = { 'D', NULL, NULL };struct BiNode nodeE = { 'E', NULL, NULL };struct BiNode nodeF = { 'F', NULL, NULL };struct BiNode nodeG = { 'G', NULL, NULL };struct BiNode nodeH = { 'H', NULL, NULL };nodeA.lchild = &nodeB;nodeA.rchild = &nodeF;nodeB.rchild = &nodeC;nodeC.lchild = &nodeD;nodeC.rchild = &nodeE;nodeF.rchild = &nodeG;nodeG.lchild = &nodeH;//1. 求二叉树的叶子节点数目int num = 0;cuculateLeafNum(&nodeA, &num);printf("叶子节点数目:%d\n", num);//2. 求二叉树的高度int height = getTreeHeight(&nodeA);printf("树的高度:%d\n",height);//3. 拷贝二叉树struct BiNode *root = copyBiTree(&nodeA);showBiTree(root);printf("\n");showBiTree(&nodeA);freeSpace(root);
}int main(){test();system("pause");return EXIT_SUCCESS;
}