一、二叉树的遍历问题
二叉树的遍历分为：前序遍历、中序遍历、后续遍历和层序遍历；
方法：（前提：树不为空）
前序遍历：访问根结点—>遍历左子树—>遍历右子树；（根、左、右）
中序遍历：遍历左子树—>访问根结点—>遍历右子树；（左、根、右）
后续遍历：遍历左子树—>遍历右子树—>访问根结点；（左、右、根）
层序遍历：从上至下，从左至右顺序访问；
示例：
二、 二叉树链式结构实现
1.二叉树的结构设计
typedef char BTDataType; typedef struct BinaryTreeNode { BTDataType data;//结点 struct BinaryTreeNode* left;//左子树 struct BinaryTreeNode* right;//右子树 }BTNode;
2.创建二叉树及初始化
//二叉树的初始化 BTNode* BuyNode(BTDataType x) { BTNode* newnode = (BTNode*)malloc(sizeof(BTNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = x; newnode->left = newnode->right = NULL; return newnode; } //创建二叉树 BTNode* CreatBinaryTree() { BTNode* nodeA = BuyNode('A'); BTNode* nodeB = BuyNode('B'); BTNode* nodeC = BuyNode('C'); BTNode* nodeD = BuyNode('D'); BTNode* nodeE = BuyNode('E'); BTNode* nodeF = BuyNode('F'); nodeA->left = nodeB; nodeA->right = nodeC; nodeB->left = nodeD; nodeC->left = nodeE; nodeC->right = nodeF; return nodeA; }
3.二叉树的前序遍历
//二叉树的前序遍历 void PreOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%c ", root->data);//访问根结点 PreOrder(root->left);//遍历左子树 PreOrder(root->right);//遍历右子树 }
4.二叉树的中序遍历
中序递归原理和前序类似；画图分析即可；
//二叉树的中序遍历 void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left);//遍历左子树 printf("%c ", root->data);//访问根结点 InOrder(root->right);//遍历右子树 }
5.二叉树的后续遍历
后序递归原理和前序类似；画图分析即可；
//二叉树的后序遍历 void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left);//遍历左子树 PostOrder(root->right);//遍历右子树 printf("%c ", root->data);//访问根结点 }
6.二叉树的结点个数
思路:：遍历左子树的结点个数+遍历右子树的结点个数；
//方法一（最优） int BinaryTreeSize1(BTNode* root) { return root == NULL ? 0 : BinaryTreeSize1(root->left) + BinaryTreeSize1(root->right) + 1; } //方法二 void BinaryTreeSize2(BTNode* root, int* pn) { if (root == NULL) { return; } ++(*pn); BinaryTreeSize2(root->left, pn); BinaryTreeSize2(root->right, pn); }
7.二叉树叶子结点个数
叶子结点：就是度为0的点，我们通过遍历它的左子树和右子树的叶子结点个数并相加；
// 二叉树叶子节点个数 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); }
8.二叉树第k层的结点给个数
// 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k) { assert(k >= 1); if (root == NULL) { return 0; } if (k == 1) { return 1; } //root不等于空，k也不等于1，说明root这棵树的第k节点在字树里面 //转换成求左右子树的第k-1的节点数量； return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1); }
9.二叉树的深度/高度
利用递归的思想，去遍历左右子树，存在两种可能（非空树的情况），递归以后，左右子树深度相等 或者不相等（左深或右深）；
//二叉树深度/高度 int BinaryTreeDepth(BTNode* root) { if (root == NULL) { return 0; } int leftDepth = BinaryTreeDepth(root->left);//算出左子树的深度 int rightDepth = BinaryTreeDepth(root->right);//算出右子树的深度 return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;//谁大加1 }
