小蜜蜂

小蜜蜂

关注
发信
关注(|-)粉丝(-|)

c++二叉树的递归和非递归的前序中序和后序遍历以及层序遍历

二叉树的递归版的前序，中序和后序遍历很简单也很容易理解，这里就放一个前序遍历的例子

//前序遍历递归算法，递归算法都大同小异，这里就不一一列举了
void binaryTree::pro_order(NodeStack::Node *t) {
	NodeStack::Node *h = t;
	if (h != NULL) {
		cout << h->data<<"  ";
		pro_order(h->lchild);
		pro_order(h->rchild);
	}
	else
		return;
}

中序遍历和后序遍历只要稍微换一下递归调用的位置就行了

非递归的二叉树的遍历需要用到栈，先放出栈的代码

#ifndef  _NodeStack_H_
#define _NodeStack_H_
#include <iostream>
#define MAXSIZE 100
typedef int type;

namespace st {
	class NodeStack {
	public:
		struct Node {
			struct Node *lchild, *rchild;  //左右孩子
			type data;              //存放数据
		};
	private:
		Node NodeData[MAXSIZE];
		int top;        //指向当前有数据的最大的空间
		int size;       //记录栈的大小
	public:
		NodeStack();
		~NodeStack();
		int push(Node*);    //入栈操作
		Node pop();    //出栈操作
		int empty();   //探空操作
		int full();    //判断是不是满的
		void traverse(); //遍历栈
		int get_top();   //获取栈顶元素值
	};
	NodeStack::NodeStack() {
		top = -1;
		size = 100;
		for (int i = 0; i < 100; i++) {
			NodeData[i].lchild = NodeData[i].rchild = NULL;
			NodeData[i].data = NULL;
		}

	}
	NodeStack::~NodeStack() {
	}
	//入栈操作，成功返回1，失败返回0
	int NodeStack::push(Node* n) {
		top++;
		NodeData[top] = *n;
		return 1;
	}
	NodeStack::Node NodeStack::pop() {
		return NodeData[top--];
	}
	int NodeStack::empty() {
		if (top == -1)
			return 1;  //栈是空的
		else
			return 0;  //栈非空
	}
	int NodeStack::full() {
		if (top == size - 1)
			return 1;     //栈是满的
		else
			return 0;     //栈不是满的
	}
	void NodeStack::traverse() {
		int t = top;
		std::cout << "栈空间：";
		while (t != -1)
			std::cout << NodeData[t--].data << " ";
		std::cout << std::endl;
	}
	int NodeStack::get_top() {
		return top;
	}
}
#endif // ! _NodeStack_H_

二叉树的结点结构体是写在栈的类里面的

先是前序遍历

//前序遍历的非递归算法
void binaryTree::pro_traverse() {
	NodeStack::Node h = *head;
	NodeStack::Node *t = &h;
	cout << "前序遍历结果如下（非递归算法）：" << endl;
	stack.push(t);
	while (!stack.empty()) {
		//只要栈不空
		//stack.traverse();
		 h = stack.pop();
		 cout << h.data << "  ";
		if (h.rchild != NULL) {
			//如果右子树不空则入栈
			t = h.rchild;
			stack.push(t);
		}
		if (h.lchild != NULL) {
			//如果左子树不空则入栈
			t = h.lchild;
			stack.push(t);
		}
	}
	cout << endl;
}

然后是中序遍历

//中序遍历的非递归算法
/*每个结点在入栈后都先找所有的左孩子，直到没有左孩子了为止
 *出栈之后找右子树，如果存在右子树那么右子树也遵循上面的步骤
 */
void binaryTree::mid_traverse() {
	NodeStack::Node h = *head;
	NodeStack::Node *t = &h;
	//先让头结点入栈
	cout << "中序遍历的结果如下（非递归算法）：" << endl;
	stack.push(t);
	while (!stack.empty()) {
		while (t->lchild != NULL) {
			t = t->lchild;
			stack.push(t);
		}
		//接下来出栈
		h = stack.pop();
		cout << h.data <<"  ";
		//如果出栈的结点有右子树那么入栈
		if (h.rchild != NULL) {
			t = h.rchild;
			stack.push(t);
			//之后再对右子树做同样操作
			while (t->lchild != NULL) {
				t = t->lchild;
				stack.push(t);
			}
		}
	}
	cout << endl;
}

接下来是后序遍历

//后序遍历的非递归算法
/*一个结点入栈后它的左右左结点都要入栈，直到没有左结点了为止
* 到了没有左结点的时候那么看看它有没有右结点，如果有就先把自己入栈，然后右结点按照上一步检查左结点
* 如果没有就输出，然后继续出栈，重复上面的步骤，这里需要维持一个记录入栈次数的数组，当一个数第三次入栈的时候
* 就不能再入栈了
*/
void binaryTree::pos_traverse() {
	NodeStack::Node h = *head;
	NodeStack::Node *t = &h;
	int num = 0;   //记录入栈的次数
	cout << "后序遍历的结果如下（非递归算法）：" << endl;
	//先入栈
	stack.push(t);
	//将所有左子树入栈
	while (t->lchild != NULL) {
		t = t->lchild;
		stack.push(t);
	}
	while (!stack.empty()) {
		h = stack.pop();    //出栈
		if (h.rchild != NULL && isfirst[stack.get_top()+1] == 0) {
			//如果右子树存在
			t = &h;
			stack.push(t);
			isfirst[stack.get_top()]++;  //第二次入栈次数加一
			t = h.rchild;
			stack.push(t);
			while (t->lchild != NULL) {
				t = t->lchild;
				stack.push(t);
			}
		}
		else {
			//否则直接输出就好了
			cout << h.data << "  ";
			//彻底出栈了之后就可以记录入栈次数为0了
			isfirst[stack.get_top() + 1] = 0;
		}
	}
	cout << endl;
}

最后是层序遍历

//层序遍历
/*层序遍历需要用到队列，我们这里用数组模拟，
*先把头结点入队，然后逐个出队，在出队的同时将左右孩子入队，我们给队分配的空间是100，也就是最多支持6层的树
*2^6=64,2^7=128，对于满二叉树的情况就会溢出，所以最多支持6层（头结点算第0层）
*/
void binaryTree::level_traverse() {
    NodeStack::Node h = *head;
    int head = 0,tail = 0;       //队列的头和尾指针，队空的标志是head == tail
    quene[head++] = h;           //head指向下一个将要填充的空间
    cout << "层序遍历的结果是：" << endl;
    //接下来开始出队
    while (head != tail) {
        h = quene[tail++];
        if (h.lchild != NULL) {
            //左子树入队
            quene[head++] = *h.lchild;
        }
        if (h.rchild != NULL) {
            quene[head++] = *h.rchild;
        }
        cout << h.data << "  ";
    }
    cout << endl;
}


下面贴完整的代码

#include <iostream>
#include "NodeStack.h"      //结点栈，树结点的定义也在这个头文件里
using namespace std;
using namespace st;        //这个命名空间就是指定NodeStack.h的，如果在那个头文件没有使用这个命名空间那么就不需要这一句
typedef int type;
//先写一个普通的二叉查找树
class binaryTree {
private:
	//树的结点的结构体

	NodeStack::Node *head;                 //头指针
	NodeStack stack;            //结点栈
	int isfirst[100];                //用于记录是否是第一次入栈（用于后序遍历的非递归算法）
	NodeStack::Node quene[100];            //模拟队列的数组，用于层序遍历
	//数的结点的栈，用于非递归遍历树
public:
	binaryTree();
	~binaryTree();
	NodeStack::Node* get_head();                //获取头指针
	void destroy(NodeStack::Node* );  //删除结点
	int insert();                    //插入操作
	void pro_traverse();             //前序遍历这棵二叉树
	void mid_traverse();             //中序遍历这棵二叉树
	void pos_traverse();             //后序遍历这棵二叉树
	void level_traverse();           //层序遍历
	//下面是遍历的递归算法
	void pro_order(NodeStack::Node*);
};
//构造函数，分配一个头结点的空间和栈的空间
binaryTree::binaryTree() {
	//初始化头指针
	head = new NodeStack::Node();
	head->lchild = head->rchild = NULL;
	head->data = NULL;
	for (int i = 0; i < 100; i++) {
		isfirst[i] = 0;  //全部初始化为0
		quene[i].lchild = quene[i].rchild = NULL;
		quene[i].data = NULL;
	}

}
//析构函数，收回所有分配的空间
binaryTree::~binaryTree() {
	NodeStack::Node *t = head;
	destroy(t);
	head = new NodeStack::Node();
	head->lchild = head->rchild = NULL;
	head->data = NULL;
}
void binaryTree::destroy(NodeStack::Node *t) {
	if (t->rchild != NULL)
		destroy(t->rchild);
	if (t->lchild != NULL)
		destroy(t->lchild);
	delete t;
}
NodeStack::Node* binaryTree::get_head() {
	return this->head;
}
//插入操作，规定左子树的数比根节点小，右子树的数比根节点大
int binaryTree::insert() {
	cout << "请输入要插入的结点的数据：";
	int num;
	cin >> num;
	if (head->data == NULL) {
		head->data = num;
		return 1;
	}
	else {
		NodeStack::Node *t = new NodeStack::Node();
		NodeStack::Node *pre = NULL;
		NodeStack::Node *h = head;
		t->lchild = t->rchild = NULL;
		t->data = num;
		while (h != NULL) {
			if (h->data > t->data) {
				pre = h;
				h = h->lchild;
			}
			else {
				pre = h;
				h = h->rchild;
			}
		}
		if (pre->data > t->data)
			pre->lchild = t;
		else
			pre->rchild = t;
		return 1;
	}
}
//前序遍历的非递归算法
void binaryTree::pro_traverse() {
	NodeStack::Node h = *head;
	NodeStack::Node *t = &h;
	cout << "前序遍历结果如下（非递归算法）：" << endl;
	stack.push(t);
	while (!stack.empty()) {
		//只要栈不空
		//stack.traverse();
		 h = stack.pop();
		 cout << h.data << "  ";
		if (h.rchild != NULL) {
			//如果右子树不空则入栈
			t = h.rchild;
			stack.push(t);
		}
		if (h.lchild != NULL) {
			//如果左子树不空则入栈
			t = h.lchild;
			stack.push(t);
		}
	}
	cout << endl;
}
//中序遍历的非递归算法
/*每个结点在入栈后都先找所有的左孩子，直到没有左孩子了为止
 *出栈之后找右子树，如果存在右子树那么右子树也遵循上面的步骤
 */
void binaryTree::mid_traverse() {
	NodeStack::Node h = *head;
	NodeStack::Node *t = &h;
	//先让头结点入栈
	cout << "中序遍历的结果如下（非递归算法）：" << endl;
	stack.push(t);
	while (!stack.empty()) {
		while (t->lchild != NULL) {
			t = t->lchild;
			stack.push(t);
		}
		//接下来出栈
		h = stack.pop();
		cout << h.data <<"  ";
		//如果出栈的结点有右子树那么入栈
		if (h.rchild != NULL) {
			t = h.rchild;
			stack.push(t);
			//之后再对右子树做同样操作
			while (t->lchild != NULL) {
				t = t->lchild;
				stack.push(t);
			}
		}
	}
	cout << endl;
}
//后序遍历的非递归算法
/*一个结点入栈后它的左右左结点都要入栈，直到没有左结点了为止
* 到了没有左结点的时候那么看看它有没有右结点，如果有就先把自己入栈，然后右结点按照上一步检查左结点
* 如果没有就输出，然后继续出栈，重复上面的步骤，这里需要维持一个记录入栈次数的数组，当一个数第三次入栈的时候
* 就不能再入栈了
*/
void binaryTree::pos_traverse() {
	NodeStack::Node h = *head;
	NodeStack::Node *t = &h;
	int num = 0;   //记录入栈的次数
	cout << "后序遍历的结果如下（非递归算法）：" << endl;
	//先入栈
	stack.push(t);
	//将所有左子树入栈
	while (t->lchild != NULL) {
		t = t->lchild;
		stack.push(t);
	}
	while (!stack.empty()) {
		h = stack.pop();    //出栈
		if (h.rchild != NULL && isfirst[stack.get_top()+1] == 0) {
			//如果右子树存在
			t = &h;
			stack.push(t);
			isfirst[stack.get_top()]++;  //第二次入栈次数加一
			t = h.rchild;
			stack.push(t);
			while (t->lchild != NULL) {
				t = t->lchild;
				stack.push(t);
			}
		}
		else {
			//否则直接输出就好了
			cout << h.data << "  ";
			//彻底出栈了之后就可以记录入栈次数为0了
			isfirst[stack.get_top() + 1] = 0;
		}
	}
	cout << endl;
}
//前序遍历递归算法，递归算法都大同小异，这里就不一一列举了
void binaryTree::pro_order(NodeStack::Node *t) {
	NodeStack::Node *h = t;
	if (h != NULL) {
		cout << h->data<<"  ";
		pro_order(h->lchild);
		pro_order(h->rchild);
	}
	else
		return;
}
//层序遍历
/*层序遍历需要用到队列，我们这里用数组模拟，
*先把头结点入队，然后逐个出队，在出队的同时将左右孩子入队，我们给队分配的空间是100，也就是最多支持6层的树
*2^6=64,2^7=128，对于满二叉树的情况就会溢出，所以最多支持6层（头结点算第0层）
*/
void binaryTree::level_traverse() {
	NodeStack::Node h = *head;
	int head = 0,tail = 0;       //队列的头和尾指针，队空的标志是head == tail
	quene[head++] = h;           //head指向下一个将要填充的空间
	cout << "层序遍历的结果是：" << endl;
	//接下来开始出队
	while (head != tail) {
		h = quene[tail++];
		if (h.lchild != NULL) {
			//左子树入队
			quene[head++] = *h.lchild;
		}
		if (h.rchild != NULL) {
			quene[head++] = *h.rchild;
		}
		cout << h.data << "  ";
	}
	cout << endl;
}

/*
	测试数据：
				5
			  /	  \
			2	    10
          /  \     /  \
        1      3  7
		         / \
                6   8
*/

int main()
{
	binaryTree bt;
	for(int i=0;i<8;i++)
		bt.insert();
	bt.pro_traverse();
	bt.mid_traverse();
	bt.pos_traverse();
	bt.level_traverse();
	return 0;
}

测试结果：

c++二叉树的递归和非递归的前序中序和后序遍历以及层序遍历-LMLPHP

10-04 17:16
Powered by LMLPHP ©2024 小蜜蜂 0.050423