已知二叉树采用二叉链表存储结构,且数据域为int型,试写一个递归算法(函数)求数据域的最大值。函数首部为:void Find_maxval(BiTree BT, int &maxval)
时间: 2023-06-13 22:02:34 浏览: 64
int Find_maxval(BiTree BT) {
int root_val, left_val, right_val, max_val;
if(BT == NULL) {
return INT_MIN; // 如果二叉树为空,则返回最小值
}
root_val = BT->data; // 获取根节点的值
left_val = Find_maxval(BT->lchild); // 递归求左子树的最大值
right_val = Find_maxval(BT->rchild); // 递归求右子树的最大值
max_val = root_val > left_val ? root_val : left_val; // 比较根节点和左子树的最大值
max_val = max_val > right_val ? max_val : right_val; // 比较之前的结果和右子树的最大值
return max_val; // 返回最大值
}
调用方式:int max_val = Find_maxval(root); // root为二叉树的根节点
相关问题
采用递归方法建立一颗含有n个节点的二叉树,采用二叉链表存储
二叉树的递归建树算法如下:
1. 如果n为0,返回NULL。
2. 新建一个节点p。
3. 递归建立左子树,将左子树的根节点赋值给p的左指针。
4. 递归建立右子树,将右子树的根节点赋值给p的右指针。
5. 返回p。
代码实现如下:
```
typedef struct node {
int data;
struct node* left;
struct node* right;
} Node;
Node* buildTree(int n) {
if (n == 0) {
return NULL;
}
Node* p = (Node*)malloc(sizeof(Node));
p->data = n;
p->left = buildTree(n-1);
p->right = buildTree(n-1);
return p;
}
```
其中,n为节点数目,buildTree函数返回一颗含有n个节点的二叉树的根节点。在此基础上,我们可以采用二叉链表存储二叉树,即每个节点包含数据域和左右指针域,指向其左右子节点。
(1)采用二叉链表存储结构,完成二叉树的层次遍历,先序遍历的非递归算法和中序遍历的非递归算法。
二叉链表存储结构是二叉树的常见存储方式,每个节点包括数据域、左子节点指针和右子节点指针。以下是二叉树的层次遍历、先序遍历和中序遍历的非递归算法实现。
1. 层次遍历
层次遍历需要借助队列来实现。从根节点开始,先将根节点入队,然后不断从队列中弹出节点,输出其数据域,同时将其左右子节点入队,直到队列为空。
```
void levelOrderTraversal(BiTree T){
if(T == NULL) return;
queue<BiTree> q;
q.push(T);
while(!q.empty()){
BiTree node = q.front();
q.pop();
cout << node->data << " ";
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
}
```
2. 先序遍历
先序遍历的非递归实现需要借助栈来实现。从根节点开始,将其压入栈中。然后不断从栈中弹出节点,输出其数据域,并将其右子节点压入栈中,再将其左子节点压入栈中。由于栈是先进后出的数据结构,所以先压入左子节点,保证左子节点先被访问。
```
void preOrderTraversal(BiTree T){
if(T == NULL) return;
stack<BiTree> s;
s.push(T);
while(!s.empty()){
BiTree node = s.top();
s.pop();
cout << node->data << " ";
if(node->right) s.push(node->right);
if(node->left) s.push(node->left);
}
}
```
3. 中序遍历
中序遍历的非递归实现也需要借助栈来实现。从根节点开始,将其压入栈中,然后不断将其左子节点压入栈中,直到最左子节点。然后从栈中弹出节点,输出其数据域,并将其右子节点压入栈中,进行下一轮循环。
```
void inOrderTraversal(BiTree T){
if(T == NULL) return;
stack<BiTree> s;
BiTree node = T;
while(node != NULL || !s.empty()){
while(node != NULL){
s.push(node);
node = node->left;
}
node = s.top();
s.pop();
cout << node->data << " ";
node = node->right;
}
}
```