二叉树

不在邓公所用的头文件下的二叉数实现。
在学习邓公的二叉树的过程中知道了二叉树要么是一棵空树，要么有两个指针，分别指向左右两个子树。而树的问题，大多采用递归来处理。
在这里我选择采用链式存储结构：
//二叉树头文件
#pragma once
#ifndef BITREE_H_INCLUDED
#define BITREE_H_INCLUDED
#include<iostream>
#include <string>
using namespace std;
struct BiNode {
	char data; 
	BiNode *LChild, *RChild; 
};

class BiTree {
private:
	BiNode * root;
	int height;
	void PreOrder(BiNode * t);
	void InOrder(BiNode * t);
	void PostOrder(BiNode * t);
	BiNode* create(string& s, int& pos);
	void GetHeight(BiNode * t, int h);
public:
	BiTree() { root = NULL; height = 0; }
	//按照前序遍历序列创建二叉树
	void createBiTree(string s);
	//前序遍历二叉树
	void preOrder();
	//中序遍历二叉树
	void inOrder();
	//递归后序遍历二叉树
	void postOrder_1();
	//非递归后序遍历二叉树
	void postOrder_2();
	//层序遍历二叉树
	void levelOrder();
	//求树的高度
	int get_Height();
};

#endif // BITREE_H_INCLUDED


//测试文件
#include "BinTree.h"
#include "queue"
#include "stack"
#include "vector"
#include <iostream>
using namespace std;

//递归创建二叉树
BiNode * BiTree::create(string& s, int& pos) {
	++pos;
	BiNode * t;
	if ((unsigned)pos >= s.size()) return 0;
	else {
		if (s[pos] == '#')
			t = NULL;
		else {
			t = new BiNode;
			t->data = s[pos];
			t->LChild = create(s, pos);
			t->RChild = create(s, pos);
		}
		return t;
	}
}

//按照前序遍历序列创建二叉数
void BiTree::createBiTree(string s) {
	int pos = -1;
	root = create(s, pos);
}

//前序遍历二叉树
void BiTree::preOrder() {
	PreOrder(root);
	cout << endl;
}
void BiTree::PreOrder(BiNode * t) {
	if (t != NULL) {
		cout << t->data << ' ';
		PreOrder(t->LChild);
		PreOrder(t->RChild);
	}
}

//中序遍历二叉树
void BiTree::inOrder() {
	InOrder(root);
	cout << endl;
}
void BiTree::InOrder(BiNode * t) {
	if (t != NULL) {
		InOrder(t->LChild);
		cout << t->data << ' ';
		InOrder(t->RChild);
	}
}

//递归后序遍历二叉树
void BiTree::postOrder_1() {
	PostOrder(root);
	cout << endl;
}
void BiTree::PostOrder(BiNode * t) {
	if (t != NULL) {
		PostOrder(t->LChild);
		PostOrder(t->RChild);
		cout << t->data << ' ';
	}
}

//非递归后序遍历二叉树
void BiTree::postOrder_2() {
	BiNode *p, *r;
	r = NULL;
	p = root;
	stack<BiNode*> my_stack;
	while (p != NULL || !my_stack.empty()) {
		if (p) {
			my_stack.push(p);
			p = p->LChild;
		}
		else {
			p = my_stack.top();
			if (p->RChild != NULL & p->RChild != r) {
				p = p->RChild;
				my_stack.push(p);
				p = p->LChild;
			}
			else {
				p = my_stack.top();
				my_stack.pop();
				cout << p->data << ' ';
				r = p;
				p = NULL;
			}
		}
	}
	cout << endl;
}

//使用队列进行层序遍历二叉树
void BiTree::levelOrder() {
	if (root == NULL)
		return;
	queue<BiNode*> q;
	q.push(root);
	while (!q.empty()) {
		BiNode * t;
		t = q.front();
		q.pop();
		cout << t->data << ' ';
		if (t->LChild != NULL)
			q.push(t->LChild);
		if (t->RChild != NULL)
			q.push(t->RChild);
	}
	cout << endl;
}

//求树的高度
int BiTree::get_Height() {
	GetHeight(root, 0);
	return height;
}
void BiTree::GetHeight(BiNode* t, int h) {
	if (t != NULL) {
		++h;
		if (h > height)
			height = h;
		GetHeight(t->LChild, h);
		GetHeight(t->RChild, h);
	}
}

//测试
int main() {
	BiTree a;
	string s;
	s = "AB##C##";//注意，无论是键盘实现输入，还是整体s输入，都要将其补成满二叉树
	a.createBiTree(s);
	cout << "前序遍历" << endl;
	a.preOrder();
	cout << "中序遍历" << endl;
	a.inOrder();
	cout << "递归后序遍历" << endl;
	a.postOrder_1();
	cout << "非递归后序遍历" << endl;
	a.postOrder_2();
	cout << "层序遍历" << endl;
	a.levelOrder();
	cout << "树高" << endl;
	cout << a.get_Height() << endl;
	system("pause");
	return 0;
}
//在测试的代码中，生成的二叉树是根节点为A，其左右子节点分别为BC，再下面皆为空节点
//可能会有疑惑，为什么不是根节点是A，其左右子节点分别为B和空，这就在于我们的创建函数：它总是沿着一边进行创建，即创建了左子节点后，再继续创建其的左子节点，直至最后一个元素
//所以当输入ABC时，实际上只创建了一条单边，即根节点为A，左子节点为B，左左子节点为C，其高度为3，就不会是2.
二叉数（二）

二叉树

推荐阅读
