设计一个非递归算法，从一棵二叉树中查找出所有节点的最大值并返回。

设计一个非递归算法 从一棵二叉树中查找出所有节点的最大值并返回~

用广度搜索
创建队列
创建初始MAX值 0
将树跟放入队列
将树根取出队列和MAX对比 比MAX大则替换MAX
然后将取出节点的左右子节点放入队列
如上遍历队列
依次类推
最后得出MAX值

1. 递归算法
void getBranchNum(TreeNode *root)
{
if (root == NULL)
return 0;
if (root->left != NULL || root->right != NULL)
return 1 + getBranchNum(root->left) + getBranchNum(root->right);
return 0;
}
2. 非递归算法：
typedef struct Link
{
TreeNode * root;
struct Link * next;
}Queue;

int getBranchNum(TreeNode *root)
{
Queue *head = (Queue *)malloc(sizeof(Queue));
Queue *tail = head;
head->root = root;
head->next = NULL;
int nNum = 0;

while(head != NULL)
{
Queue *temp;
int degree = 0;
if (head->root->left != NULL)
{
temp = (Queue *)malloc(sizeof(Queue));
temp->root = head->root->left;
temp->next = NULL;
tail->next = temp;
tail = temp;
degree++;
}

if (head->root->right != NULL)
{
temp = (Queue *)malloc(sizeof(Queue));
temp->root = head->root->right;
temp->next = NULL;
tail->next = temp;
tail = temp;
degree++;
}

if (degree > 0)
nNum ++;

temp = head;
head = head->next;
free(temp);
}
return nNum;
}

给个思路：

    找最大值的关键是树的遍历，而递归的遍历方式，就是利用函数调用，参数的入栈出栈，来达到回溯的目的，同理，不用递归调用，我们也可以采用这个思想

1. 创建一个栈式的数据结构

2. 将根节点指针压入栈中，访问其值，假如我们采用广度优先的遍历方式，就遍历其子节点

3. 在访问子节点的同时，依次将访问过的节点指针压入栈中，而最上面的节点就是最后访问的节点

4. 如最上面的节点是叶子节点，则弹栈，否则继续遍历其子节点，并如3步所说，依访问顺序压栈

5. 对于所有子节点都已遍历（压栈）的父节点，做标记，则当弹栈后，栈的最上面是一个带有标记的非叶子节点，亦将其弹出栈

6. 循环3-5步，直到栈空为止

深度优先搜索，也可以用类似的方式实现

java实现 :

import java.util.Scanner;
import java.util.Vector;
/** BinaryTree .java
*
*/

public class BinaryTree{
public BinaryTree (Node root){
root.left=construct(root.left);
}
public Node construct(Node node){
System.out.println("input next node id(num):");
int id = Integer.parseInt(new Scanner(System.in).nextLine());
if(id!=-1) node=new Node(id);
else return null;
node.left=construct(node.left);
node.right=construct(node.right);
return node;
}
public int visitMax(Node root){
Vector<Node> tasks=new Vector<Node>();
Node tmp = root.left;
tasks.add(tmp);
int max=-1;
while(!tasks.isEmpty()){
while(tmp!=null){
if(max<tmp.visitMax())
max=tmp.visitMax();
tasks.add(tmp);
tmp=tmp.left;
}
tmp=tasks.lastElement();
tasks.remove(tmp);
tmp=tmp.right;
}
return max;
}
public static void main(String[] args) {
Node root=new Node(0);
BinaryTree bt=new BinaryTree(root);
System.out.println("max num is:"+bt.visitMax(root));
}
}
//BinaryTree .java

class Node{
int num;
Node left,right;
Node(int num){
this.num=num;
}
public int visitMax(){
System.out.println("visited:"+this.num);
return num;
}
};

直接for循环遍历？二叉树节点信息是装在数组里面的直接for遍历数组不就行了？当然如果不是数组，直接遍历类似的。

---

灵丘县19645647509： 设计一个非递归算法,从一棵二叉树中查找出所有节点的最大值并返回. - ？
康承冰珍： 给个思路:找最大值的关键是树的遍历,而递归的遍历方式,就是利用函数调用,参数的入栈出栈,来达到回溯的目的,同理,不用递归调用,我们也可以采用这个思想 创建一个栈式的数据结构将根节点指针压入栈中,访问其值,假如我们采用广度优先的遍历方式,就遍历其子节点在访问子节点的同时,依次将访问过的节点指针压入栈中,而最上面的节点就是最后访问的节点如最上面的节点是叶子节点,则弹栈,否则继续遍历其子节点,并如3步所说,依访问顺序压栈对于所有子节点都已遍历(压栈)的父节点,做标记,则当弹栈后,栈的最上面是一个带有标记的非叶子节点,亦将其弹出栈循环3-5步,直到栈空为止深度优先搜索,也可以用类似的方式实现

灵丘县19645647509： 已知一颗具有n个结点的完全二叉树以向量作为存储结构,设计一个非递归算法,实现对该树的先序遍历. - ？
康承冰珍：[答案] public class haha { public haha(int tree[]) { int p = 0; int k = 0; while(k != tree.length){ if(p解析看不懂?免费查看同类题视频解析查看解答

灵丘县19645647509： 跪求!!10分奉上!统计二叉树结点个数的算法 非递归 - ？
康承冰珍： 一般情况下,涉及二叉树的很多操作都包含两个方面.一方面,由于二叉树本身的递归定义,因此用递归的思想设计其很多操作是顺理成章的;另一方面,为了控制过程的深度和节约栈空间,我们有时也会考虑用非递归的思想设计很多关于二叉...

灵丘县19645647509： 二叉树中序遍历非递归算法(c语言实现) - ？
康承冰珍： 把递归拆开,自己弄个栈来模拟递归就是了 貌似这种技巧没什么实际意义,不过还是写了吧#include <stdio.h> #define MAXN 100 /*节点的最大数量,姑且定为100*/ struct Node//二叉树节点 { int data; Node *left,*right; };Node *root;void Load(...

灵丘县19645647509： 请问怎么用非递归算法建立一棵二叉树? - ？
康承冰珍： 我是用C++模板写的,希望可以帮助你.构造方法是:输入一串字符;如果直接输入#,则是空树;否则则是AB###;即以前序顺序输入;代码:void Tree<T>::creat_tree(TreeNode<T> * &pointer) { //递归实现对森林的赋值;********************** /*...

灵丘县19645647509： 二叉树,如何设计一个算法,使得交换左右子树.要求非递归算法. - ？
康承冰珍： 递归算法:void exchange(BitTree T){ BitNode p; if(T->lchild==null && T->rchild==null) return; else{ p=T->lchild; T->lchild=T->rchild; t->rchild=P; }if(T->lchild){exchange(T->lchild);}if(T->rchild){exchange(T->rchild);}}非递归算法使...

灵丘县19645647509： c语言:在二叉树中,用非递归算法求节点所在的层次数 - ？
康承冰珍： 先一层一层的遍历二叉树 用一个辅助的数据结构队列 队列! 注意 这个很重要 队首放节点 队尾取出节点 比如:根节点放入队列 (开始只有这个一个节点在队列中) 然后呢 从队尾取出这个根节点 然后打散 把他的左右孩子放入对首(这时候有2...

灵丘县19645647509： 在二叉树T中,编写一个非递归程序输出该树的所有叶子结点. - ？
康承冰珍： 算法思路:需要辅助栈用后序遍历非递归算法,当遍历到该结点时,栈里面从栈顶到栈底的各元素就是该结点从其双亲开始依次往根回溯的所有祖先

灵丘县19645647509： 在二叉树T中,编写一个非递归程序输出该树的所有叶子结点.... - ？
康承冰珍： 在二叉树T中,编写一个非递归程序输出该树的所有叶子结点....汗马绝尘安外振中标青史 锦羊开泰富民清政展新篇 春满人间汗马绝尘安外振中标青史 锦羊开泰富民清政展新篇 春满人间

灵丘县19645647509： 一棵具有n个结点的完全二叉树以数组存储,试写一个非递归算法实现对该树的前序遍历 - ？
康承冰珍： #include ＂stdafx.h＂#include <stack>#include <iostream>using namespace std; int _tmain(int argc, _TCHAR* argv[]){ //构建完全二叉树,层数是三,7个节点 int a[7] = {0,1,2,3,4,5,6}; //前序遍历,先访问左儿子,再访问自己,再访问右儿子 //左...