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函数中引发了未经处理的异常:读取访问权限冲突。 R 是 0xFFFFFFFFFFFFFFFF，为什么内容：R的值为0xFFFFFFFFFFFFFFFF说明该指针已经被释放或者未初始化，无法进行访问操作，导致了访问权限冲突的异常。可能是在访问到叶子节点时，继续向下遍历导致了该指针被释放，或者在创建节点时未正确初始化指针。需要检查代码中是否存在这样的问题，修正后再运行程序。