首页 > 代码库 > 002.深入浅出理解[二叉树的构建、先中后序遍历、树的深度、左右子树互换]
002.深入浅出理解[二叉树的构建、先中后序遍历、树的深度、左右子树互换]
二叉树本来就是递归定义的,如果对递归还不是特别了解,建议看一下《001.深入浅出解释[递归]》
写一个递归函数很简单,只需要记住下面2点:
1、递归中止条件:对于二叉树来说一般是node==null的时候判断到了叶子结点
2、递归函数:;描述一个中间过程,然后用代码实现,调用自身的时候传递的参数就是你想要递归的方式。
下面的代码就是一个二叉树的创建、先中后序遍历、树的深度、左右子树的互换的过程
#include<stdio.h>
//定义二叉树的结点
struct treeNode{
char data;
treeNode *left; // 指向左孩子结点
treeNode *right; // 指向右孩子结点
};
//创建一颗二叉树
treeNode*creatBinaryTree(char a[],int pos,int length){
treeNode *node =NULL;
// 边界条件
if(pos > length|| a[pos] ==‘0‘){
return NULL;
}
node =new treeNode;
node->data = a[pos];
// 递归创建
node->left =creatBinaryTree(a,2*pos, length);
node->right =creatBinaryTree(a,2*pos +1, length);
return node;
}
//前序遍历二叉树
voidpreOrderScanBinary(treeNode *node){
// 边界条件(直到结点不存在)
if(node) {
// 打印根结点
printf("%c ",node->data);
// 递归打印左右子树
preOrderScanBinary(node->left);
preOrderScanBinary(node->right);
}
}
//中序遍历
voidinOrderScanBinary(treeNode *node){
if(node) {
inOrderScanBinary(node->left);
printf("%c ",node->data);
inOrderScanBinary(node->right);
}
}
//后序遍历
voidpostOrderScanBinary(treeNode *node){
if(node) {
postOrderScanBinary(node->left);
postOrderScanBinary(node->right);
printf("%c ",node->data);
}
}
//求二叉树的深度
int binaryDepth(treeNode *node){
if(!node)
return 0;
int nLeft =binaryDepth(node->left); // 左子树的深度
int nRight =binaryDepth(node->right); // 有子树的深度
return nLeft>nRight ? (nLeft +1) : (nRight +1); // 树的深度 = max(左子树深度,右子树深度) + 1
}
//左右子树的交换
void exchangeSubTree(treeNode *node){
treeNode *tempSubTree;
if(!node) {
tempSubTree = node->left;
node->left = node->right;
node->right = tempSubTree;
exchangeSubTree(node->left);
exchangeSubTree(node->right);
}
}
int main(int argc,const char * argv[])
{
int length;
printf("请输入数组的长度以及数组元素:");
scanf("%d",&length);
char *a =new char[length+10];
for (int i =1; i <= length; i++) {
scanf("%c",&a[i]);
}
// 创建一颗二叉树
treeNode *head =creatBinaryTree(a,1,length);
// 先序遍历
printf("先序遍历:");
preOrderScanBinary(head);
// 中序遍历
printf("\n中序遍历:");
inOrderScanBinary(head);
// 后序遍历
printf("\n后序遍历:");
postOrderScanBinary(head);
// 树的深度
printf("\n树的深度:%d\n",binaryDepth(head));
return 0;
}
002.深入浅出理解[二叉树的构建、先中后序遍历、树的深度、左右子树互换]