链式二叉树--前序中序后序遍历，高度，节点个数问题

目录

 前言：

一：链式二叉树的结构定义

 二：链式二叉树的遍历--->前序，中序，后序

1.前序

 递归展开图分析

2.中序 

递归展开图分析 

3.后序 

三：二叉树结点的求解 

1.二叉树总结点

递归展开分析 

2.二叉树叶子结点数 

递归展开分析 

3.二叉树第k层节点个数 

递归展开分析 

四：二叉树的高度 

五：总结语

---

接下来的日子会顺顺利利，万事胜意，生活明朗-----------林辞忧

 前言：

链式二叉树作为后续AVL树，B系列树的雏形，理解掌握链式二叉树的各种操作很重要，此处就需要用递归来实现链式二叉树的各种操作，相信认真学习过后会对递归有更深刻的理解，接下来我们就开始上菜

一：链式二叉树的结构定义

链式二叉树的结构由指针域和数值域组成，况且链式二叉树并不都是完全二叉树，还有普通二叉树，每个节点最多两个孩子

 二：链式二叉树的遍历--->前序，中序，后序

1.前序

BTNode* Buynode(int x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail\n");return NULL;}newnode->left = NULL;newnode->right = NULL;newnode->data = x;return newnode;
}BTNode* CreatTree()
{BTNode* n1 = Buynode(1);BTNode* n2 = Buynode(2);BTNode* n3 = Buynode(3);BTNode* n4 = Buynode(4);BTNode* n5 = Buynode(5);BTNode* n6 = Buynode(6);BTNode* n7 = Buynode(7);n1->left = n2;n1->right = n3;n2->left = n4;n2->right = n5;n3->left = n6;n3->right = n7;return n1;
}
void PrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return ;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}

 递归展开图分析

2.中序 

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

递归展开图分析 

3.后序 

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

后续递归展开图同上展开即行

三：二叉树结点的求解 

1.二叉树总结点

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL)//递归结束条件{return 0;}return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;//从左子树和右子树中分别计数
}

递归展开分析 

2.二叉树叶子结点数 

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL)//空树返回0return 0;if (root->left == NULL && root->right == NULL)//叶子节点无孩子return 1;return BinaryTreeLeafSize(root->left)//递归往下寻找 + BinaryTreeLeafSize(root->right);
}

递归展开分析 

3.二叉树第k层节点个数 

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 1)//循环走到k==1时停止，且不为空return 1;//分治思想：转化为求k-1层的节点数return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root, k - 1);
}

递归展开分析 

四：二叉树的高度 

//二叉树的高度
int BinaryTreeHeight(BTNode* root)
{if (root == NULL)return 0;//记录左右长度，再进行比较int leftHeight = BinaryTreeHeight(root->left);int rightHeight = BinaryTreeHeight(root->right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

 此图递归展开图就省略了昂

五：总结语

学会二叉树得学会画图，实在不懂时，画画递归展开图会好很多的