学步园

 1．在一棵一般的二叉树中找到指定的元素，如果有重复出现的元素，要求元素为深度最深的任何一个。指定元素找不到时返回EMPTY_NODE，请用

C语言实现，相关数据结构与函数声明如下：
struct Node
{
         int iValue;　　
         int id;
         Node *pLeft;
    Node *pRight;
};
 
const Node EMPTY_NODE = {0, 0, NULL, NULL};
Node findDeepest(Node *pRoot, int iWanted); //pRoot为根节点，wanted为指定元素的iValue

程序[根据程序遍历即可，二叉树的创建根据满二叉数组提供的数据，利用前序递归进行创建]

/*******************************************************************<br /> *<br /> * DESCRIPTION: Baidu 20091106<br /> *<br /> * AUTHOR: Neesky<br /> *<br /> * DATE:2009-11-6<br /> *<br /> *******************************************************************/<br /> /** include files **/<br /> #include <iostream><br /> using namespace std;<br /> struct Node<br /> {<br /> int iValue;<br /> int iD;<br /> Node *pLeft;<br /> Node *pRight;<br /> };<br /> const Node EMPTY_NODE = {0, 0, NULL, NULL};<br /> /**<br /> * ArrNodes For Full Binary Tree<br /> *<br /> * @author NeeSky (2009-11-6)<br /> */<br /> int ArrNodes[8]={-1,1,2,3,4,3,6,7};<br /> /**<br /> * Create Binary Tree As Arrays,Recursive Method<br /> *<br /> * @author NeeSky (2009-11-6)<br /> *<br /> * @return Node*<br /> */<br /> Node* CreateBinaryTree(int ArrNode[], int N, int i)<br /> {<br /> Node *p=new Node;<br /> p->iValue=ArrNode[i];p->iD=i;<br /> if(2*i<N)p->pLeft=CreateBinaryTree(ArrNode,N,2*i);<br /> if(2*i+1<N)p->pRight=CreateBinaryTree(ArrNode,N,2*i+1);<br /> return p;<br /> }<br /> /**<br /> * Visit The Binary Tree as Level Order for find deepest iWanted<br /> *<br /> * @author NeeSky (2009-11-6)<br /> *<br /> * @param root<br /> */<br /> Node findDeepest(Node *pRoot, int iWanted)<br /> {<br /> if(pRoot==NULL)return EMPTY_NODE;<br /> Node *p=pRoot;queue<Node*> que;<br /> Node *pDeepest=NULL;<br /> que.push(p);<br /> while(!que.empty())<br /> {<br /> p=que.front();que.pop();<br /> if(p->iValue==iWanted)pDeepest=p;/*The Final Deepest Node*/<br /> if(p->pLeft!=NULL)que.push(p->pLeft);<br /> if(p->pRight!=NULL)que.push(p->pRight);<br /> }<br /> return *pDeepest;<br /> }<br /> /**<br /> * The Main Programming<br /> *<br /> * @author NeeSky (2009-11-7)<br /> *<br /> * @param argc<br /> * @param argv<br /> *<br /> * @return int<br /> */<br /> int main (int argc, char *argv[])<br /> {<br /> Node* t=CreateBinaryTree(ArrNodes,8,1); /*Create Binary Node As Full Binary Tree Array*/<br /> Node node=findDeepest(t, 3);<br /> if(node.iD!=0&&node.iValue!=0)<br /> cout<<"/nDeepest Node(id) is: "<<node.iD<<endl;<br /> return(0);<br /> }<br />

输出：

Deepest Node(id) is: 5