C++ 实现二叉树的创建、遍历、深度计算和路径查找

#include #include using namespace std; struct node {

 int data;
 node* lch;
 node* rch;

}; class tree { private: void create(node &R,int data[],int i,int n); void release(node R); public: node root; tree(int data[], int n); void preorder(node R); void inorder(node* R); void postorder(node* R); void levelorder(node* R); void depth(int data[],int n); void path(int k); ~tree(); }; void tree::create(node *&R, int data[], int i, int n) {

if (i <= n && data[i - 1] != 0)
{
	R = new node;
R->data = data[i-1];
R->lch = R->rch =NULL;
create(R->lch, data, 2 * i, n);
create(R->rch, data, 2 * i + 1, n);

}

} tree::tree(int data[], int n) { create(root, data, 1, n); } void tree::preorder(node* R)//前序排列 {

if (R != NULL)
{
	cout << R->data;
	preorder(R->lch);
	preorder(R->rch);
}

} void tree::inorder(node* R)//中序排列 { if (R !=NULL) { inorder(R->lch); cout << R->data; inorder(R->rch); } } void tree::postorder(node* R)//后序排列 { if (R != NULL) { postorder(R->lch); postorder(R->rch); cout << R->data; } } void tree::levelorder(node* R)//层序排列 { node* queue[100]; int front=0 ,rear = 0; if (R != NULL)queue[++rear] = R; while(front!=rear) { node *p = new node; p = queue[++front]; cout << p->data; if (p->lch != NULL)queue[++rear] = p->lch; if (p->rch != NULL)queue[++rear] = p->rch; delete p; }

} void tree::release(node* R)//销毁二叉树 {if(R!= NULL) { release(R->lch); release(R->rch); delete R; } } tree::~tree() { release(root); } void tree::depth(int data[],int n)//计算树的深度 { int j = 1,i=0,k=1;

while (j<=n)
{
	if (data[j - 1] != 0)
	{
		i++;
	}
	j++;
}

while (k <= n)
{
	if (pow(2, k) - 1 <= i) {
		k++;

	}
	else break;
}
cout << k;

} void tree::path(int k)//找到根节点与值为k的结点的路径 {

{
	node* p[100];
	int top = -1;
	node* R = root;
	p[++top] = R;
	while (R->data != k)
	{
		if (R != NULL)
			R = R->lch;
		p[++top] = R;
		if (R == NULL) 
		{
			top--;
			continue;
		}
		if (R->data == k) 
			break;
		R = R->rch;
		p[++top] = R;
	}
	for (int i = 0; ; i++)
	{
		if (p[i] != 0 && p[i + 1] != 0)
		{
			cout << p[i]->data << "->";
		}
		if (p[i] != 0 && p[i + 1] == NULL)
		{
			cout << p[i]->data;
		}
		if (p[i] == NULL) 
			break;
	}
}

} int main() { int data[100] = { 1,2,3,4,5,6,7,8,9,10 }; tree a(data, 10); cout << "前序排列："; a.preorder(a.root); cout << endl; cout << "中序排列："; a.inorder(a.root); cout << endl; cout << "后序排列："; a.postorder(a.root); cout << endl; cout << "层序排列："; a.levelorder(a.root); cout << endl; cout << "树的深度："; a.depth(data,10); cout << endl; cout << "路径："; a.path( 5); a.~tree(); return 0; }path函数如何修改，才能找到指定结点到根结点的路径 内容：可以修改path函数，使用一个栈来保存从根节点到当前节点的路径，当找到目标节点后，遍历栈输出路径即可。具体修改如下：

void tree::path(int k)//找到根节点与值为k的结点的路径 { node* p[100]; int top = -1; node* R = root; p[++top] = R; while (R->data != k) { if (R != NULL) R = R->lch; p[++top] = R; if (R == NULL) { top--; continue; } if (R->data == k) break; R = R->rch; p[++top] = R; } cout << "路径："; for (int i = top; i >= 0; i--) { cout << p[i]->data; if (i != 0) cout << "->"; } }