二叉链存储结构存储二叉树
采用二叉链存储结构存储二叉树，假设一棵二叉树的前序序列为2 3 4 5 6 7 9，中序序列为5 3 2 4 7 6 9，根据要求完成相应的操作。
1、根据前序和中序，建立该二叉树。
2、输出该二叉树。
3、输出后序序列。
4、计算二叉树的结点个数。
5、计算所有叶子结点个数
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 根据前序和中序，建立二叉树
TreeNode* CreateTree(int* preorder, int* inorder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd) {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = preorder[preStart];
int rootIndex = inStart;
while (inorder[rootIndex] != root->data) {
rootIndex++;
}
int leftSize = rootIndex - inStart;
root->left = CreateTree(preorder, inorder, preStart + 1, preStart + leftSize, inStart, rootIndex - 1);
root->right = CreateTree(preorder, inorder, preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd);
return root;
}
// 输出二叉树
void printTree(TreeNode* root, int depth) {
if (root == NULL) {
return;
}
printTree(root->right, depth + 1);
for (int i = 0; i < depth; i++) {
printf(" ");
}
printf("%d\n", root->data);
printTree(root->left, depth + 1);
}
// 输出后序序列
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->data);
}
// 计算二叉树的结点个数
int countNodes(TreeNode* root) {
if (root == NULL) {
return 0;
}
return 1 + countNodes(root->left) + countNodes(root->right);
}
// 计算所有叶子结点个数
int countLeaves(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return countLeaves(root->left) + countLeaves(root->right);
}
int main() {
int preorder[] = {2, 3, 4, 5, 6, 7, 9};
int inorder[] = {5, 3, 2, 4, 7, 6, 9};
TreeNode* root = CreateTree(preorder, inorder, 0, 6, 0, 6);
printf("二叉树：\n");
printTree(root, 0);
printf("后序序列：");
postorderTraversal(root);
printf("\n结点个数：%d\n", countNodes(root));
printf("叶子结点个数：%d\n", countLeaves(root));
return 0;
}
- 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7459515
- 这篇博客也不错, 你可以看下二叉树中完全二叉树、满二叉树、二叉排序树、平衡二叉树的区别和联系
- 除此之外, 这篇博客: 数据结构 - 搜索二叉树中的 一、搜索二叉树概念 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
搜索二叉树是一种特殊的二叉树，从根节点开始，左子树根节点的值一定当前节点值小，右子树根节点的值一定比当前节点大。
根据搜索二叉树的特点：
对搜索二叉树中序遍历，就会得到一个递增的序列。
可以类似二分查找，从根节点开始，查找值比当前节点值大去右子树找，比当前节点值小去左子树找，若值相等则查找完毕，一直到空节点则查找失败。
- 您还可以看一下 贺利坚老师的数据结构基础系列(6)：树和二叉树课程中的 二叉树的存储结构小节, 巩固相关知识点
- 以下回答由chatgpt基于相关博客总结生成:
二叉链存储结构是指在二叉树结点中增加两个指向左右孩子的指针域，来表示一棵二叉树。具体如下:
typedef char ElementType; // 以 char 数据为例 typedef struct TNode *Position; typedef Position BinTree; struct TNode { ElementType Data; BinTree Left; BinTree Right; };- 建立二叉树
参考资料中提供两种建立二叉树的方式，均为递归实现。这里给出一种非递归实现的方式。
#include <stack> using namespace std; BinTree CreateBinTree() { stack<Position> s; BinTree root = nullptr; ElementType ch; scanf("%c",&ch); if(ch != '#') { root = new struct TNode; root->Data = ch; root->Left = nullptr; root->Right = nullptr; s.push(root); } while(!s.empty()) { Position t = s.top(); s.pop(); scanf("%c",&ch); if(ch == '#') { if(!t->Left) t->Left = nullptr; if(!t->Right) t->Right = nullptr; } else { t->Left = new struct TNode; t->Left->Data = ch; t->Left->Left = nullptr; t->Left->Right = nullptr; s.push(t->Left); } scanf("%c",&ch); if(ch == '#') { if(!t->Right) t->Right = nullptr; if(!t->Left) t->Left = nullptr; } else { t->Right = new struct TNode; t->Right->Data = ch; t->Right->Left = nullptr; t->Right->Right = nullptr; s.push(t->Right); } } return root; }- 输出二叉树
二叉树的输出，可以通过递归遍历并打印每个结点实现，这里给出一个前序遍历的例子。
void PreOrderTraversal(BinTree BT) { if(BT) { printf("%c ", BT->Data); PreOrderTraversal(BT->Left); PreOrderTraversal(BT->Right); } }- 输出后序序列
同样是通过递归实现，这里给出一个递归后序遍历的例子。
void PostOrderTraversal(BinTree BT) { if(BT) { PostOrderTraversal(BT->Left); PostOrderTraversal(BT->Right); printf("%c ", BT->Data); } }- 计算二叉树的结点个数
计算二叉树的结点个数可以通过递归实现，递归到底部返回0，每次返回左右子树的结点个数加1即可。
int CountNodes(BinTree BT) { if(BT == nullptr) return 0; return CountNodes(BT->Left) + CountNodes(BT->Right) + 1; }- 计算所有叶子结点个数
计算叶子结点个数同样可以通过递归实现，同样递归到底部每次返回0，在叶子节点返回1，每次返回左右子树的叶子节点数相加即可。
int CountLeafNodes(BinTree BT) { if(BT == nullptr) return 0; if(BT->Left == nullptr && BT->Right == nullptr) return 1; return CountLeafNodes(BT->Left) + CountLeafNodes(BT->Right); }完整代码如下：
#include <iostream> #include <stack> using namespace std; typedef char ElementType; // 以 char 数据为例 typedef struct TNode *Position; typedef Position BinTree; struct TNode { ElementType Data; BinTree Left; BinTree Right; }; // 建立二叉树 BinTree CreateBinTree() { stack<Position> s; BinTree root = nullptr; ElementType ch; scanf("%c",&ch); if(ch != '#') { root = new struct TNode; root->Data = ch; root->Left = nullptr; root->Right = nullptr; s.push(root); } while(!s.empty()) { Position t = s.top(); s.pop(); scanf("%c",&ch); if(ch == '#') { if(!t->Left) t->Left = nullptr; if(!t->Right) t->Right = nullptr; } else { t->Left = new struct TNode; t->Left->Data = ch; t->Left->Left = nullptr; t->Left->Right = nullptr; s.push(t->Left); } scanf("%c",&ch); if(ch == '#') { if(!t->Right) t->Right = nullptr; if(!t->Left) t->Left = nullptr; } else { t->Right = new struct TNode; t->Right->Data = ch; t->Right->Left = nullptr; t->Right->Right = nullptr; s.push(t->Right); } } return root; } // 输出二叉树（前序遍历） void PreOrderTraversal(BinTree BT) { if(BT) { printf("%c ", BT->Data); PreOrderTraversal(BT->Left); PreOrderTraversal(BT->Right); } } // 输出后序序列 void PostOrderTraversal(BinTree BT) { if(BT) { PostOrderTraversal(BT->Left); PostOrderTraversal(BT->Right); printf("%c ", BT->Data); } } // 计算二叉树的结点个数 int CountNodes(BinTree BT) { if(BT == nullptr) return 0; return CountNodes(BT->Left) + CountNodes(BT->Right) + 1; } // 计算叶子结点个数 int CountLeafNodes(BinTree BT) { if(BT == nullptr) return 0; if(BT->Left == nullptr && BT->Right == nullptr) return 1; return CountLeafNodes(BT->Left) + CountLeafNodes(BT->Right); } int main() { BinTree BT = CreateBinTree(); printf("前序遍历："); PreOrderTraversal(BT); printf("\n后序序列："); PostOrderTraversal(BT); printf("\n结点个数：%d\n", CountNodes(BT)); printf("叶子结点个数：%d\n", CountLeafNodes(BT)); return 0; }