bintree.cpp

建立二叉树

// Bintree.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream>
#include<queue>
using namespace std;

struct Bintreenode
{int data;
Bintreenode* leftchild;
Bintreenode* rightchild;
Bintreenode() : leftchild(NULL), rightchild(NULL),data(0) {
}
};
Bintreenode *search(Bintreenode *subtree,int x)
{if(subtree==0) return 0;
	if(subtree->data==x)return subtree;
Bintreenode *p;
if((p=search(subtree->leftchild,x))!=0) return p;
else return search(subtree->rightchild,x);
}

Bintreenode* Parent(Bintreenode * subtree,Bintreenode *current)
{if(subtree==0) return 0;
if(subtree->leftchild==current||subtree->rightchild==current) return subtree;
Bintreenode *p;
if((p=Parent(subtree->leftchild,current))!=0) return p;
else return Parent(subtree->rightchild,current);
}

int _tmain(int argc, _TCHAR* argv[])
{cout<<"请输入n"<<endl;
int n;
cin>>n;
cout<<"请输入"<<n<<"个数"<<endl;
int *p=new int[n];
for(int i=0;i<n;i++)
cin>>p[i];

queue<Bintreenode* >Q,R;
Bintreenode* q,*r;
Bintreenode* root=new Bintreenode;
Q.push(root);
for( int i=0;i<n;i++)
 {q=Q.front();Q.pop();q->data=p[i];
 
  q->leftchild=new Bintreenode;Q.push(q->leftchild);
 q->rightchild=new Bintreenode;Q.push(q->rightchild);
 }

R.push(root);
while(!R.empty())
{q=R.front();R.pop();cout<<q->data<<" ";
if(q->leftchild!=0)R.push(q->leftchild);
if(q->rightchild!=0)R.push(q->rightchild);
}
cout<<endl;
cout<<"请输入要查找的节点的值"<<endl;
cin>>n;
q=search(root,n);
if(q==0)cout<<"未找到"<<endl;
else
{r=Parent(root,q);
 while(r!=0)
 {cout<<r->data;
  r=Parent(root,r);
 }
}

	return 0;
}