设计二叉树,要求: 1、表示二叉树树、节点的度、树的度、分支节点、叶子节点、孩子节点、双亲节点。 2、二叉树的基本运算和各种遍历算法的实现,包括先序遍历、中序遍历、后序遍历。
时间: 2023-10-01 20:03:48 浏览: 62
(1)二叉树的建立 (2)求出二叉树的高度 (3)求出二叉树结点个数 (4)先序遍历递归实现 (5)先序遍历非递归实现 (6)求出二叉树叶子结点个数
3星 · 编辑精心推荐
首先,我们需要定义二叉树的数据结构。一个二叉树节点包含三个部分:节点值、左子节点和右子节点,我们可以用一个结构体来表示:
```
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
```
节点的度指的是该节点的子节点数目,树的度指的是所有节点度数的最大值。分支节点指的是度不为0的节点,叶子节点指的是度为0的节点。孩子节点指的是某个节点的子节点,双亲节点指的是某个节点的父节点。
二叉树的基本运算包括:创建二叉树、插入节点、删除节点、查找节点、计算二叉树深度等。这里我们只实现创建二叉树的操作,其他操作可以在此基础上进行扩展。
创建二叉树的操作可以采用递归的方式,我们可以先创建根节点,然后递归创建左子树和右子树。
```
TreeNode* createTree() {
TreeNode *root = NULL;
int val;
scanf("%d", &val);
if (val != -1) {
root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
root->left = createTree();
root->right = createTree();
}
return root;
}
```
其中,我们用-1来表示空节点。
遍历算法分为先序遍历、中序遍历和后序遍历三种。它们的区别在于遍历顺序不同。以先序遍历为例,它的遍历顺序为:根节点->左子树->右子树。
```
void preOrder(TreeNode *root) {
if (root == NULL) {
return;
}
printf("%d ", root->val);
preOrder(root->left);
preOrder(root->right);
}
```
中序遍历的遍历顺序为:左子树->根节点->右子树,后序遍历的遍历顺序为:左子树->右子树->根节点。
阅读全文