(c++)二叉树（一）
(c++)二叉树（一）
我扫了一圈，发现网上讲二叉树的都好古怪，有用的代码大部分都在书上。于是就结合我对二叉树的理解分享下，希望对大家有所帮助
首先，对于一颗二叉树而言，一个结点要有三个要素才能被称为二叉树
一、当前结点的值
二、左结点的地址
三、右结点的地址
故我们创建一个二叉树结点的结构体
typename T
struct BinTreeNode{
T data;
BinTreeNodeT *lChild, *rChild;
BinTreeNode() : lChild(NULL), rChild(NULL) {}
BinTreeNode(T x, BinTreeNodeT *l = NULL, BinTreeNodeT *r = NULL) : data(x),lChild(l), rChild(r) {} //带默认值的有参构造参数
};
二叉树的功能我们将封装成一个类，来供方便调用
关于这个二叉树，其功能要有
1、构造和析构
1.1、构造函数
1.2、析构函数
2、二叉树的创建
2.1、广义表创建二叉树
2.2、前序遍历创建二叉树
2.3、先序遍历和中序遍历创建二叉树
2.4、后序遍历和中序遍历创建二叉树
3、二叉树的遍历
3.1、递归遍历
3.1.1、先序遍历
3.1.2、中序遍历
3.1.3、后序遍历
3.2、非递归遍历
3.2.1、先序遍历
3.2.2、中序遍历
3.2.3、后序遍历
3.2.4、层次遍历
4、结点获取
4.1、根节点
4.2、某节点的父节点
4.3、某节点的左节点
4.4、某节点的右节点
类的定义
template typename T
class BinaryTree
{
public:
//各类函数定义
protected:
//各类函数实现
private:
BinTreeNodeT *root;//根结点
T Ref;//指定数据结束符
};
1、构造和析构
BinaryTree() : root(NULL) {}
BinaryTree(T value) : RefValue(value), root(NULL) {}
~BinaryTree() { Destroy(root); }
2、二叉树的创建
前序遍历：根左右（根结点-左结点-右结点）
中序遍历：左根右
后序遍历：左右根
2.1 广义表创建二叉树
void CreateBinTree(BinTreeNodeT *BT){
stackBinTreeNodeT * s;
BT = NULL;
BinTreeNodeT *p, *t; //p用来记住当前创建的节点，t用来记住栈顶的元素
int k;//k是处理左、右子树的标记
T ch;
cinch;
while (ch != Ref){
switch (ch){
case (: //对(做处理
s.push(p);
k = 1;
break;
case ): //对)做处理
s.pop();
break;
case ,: //对,做处理
k = 2;
break;
default:
p = new BinTreeNodeT(ch); //构造一个结点
if (BT == NULL){
BT = p;
}
else if (k == 1) {//加入左结点
t = s.top();
t-lChild = p;
}
else {//加入右结点
t = s.top();
t-rChild = p;
}
}
cinch;
}
}
2.2 前序遍历创造二叉树
图源百度百科
类内定义：void CreateBinTree_PreOrder() { CreateBinTree_PreOrder(root); }
void CreateBinTree_PreOrder(BinTreeNodeT *subTree)
{
T item;//结点值
if (cinitem){
if (item != Ref){//未遇到结束符，那么创建结点
subTree = new BinTreeNodeT(item); //默认参数构造结点
if (subTree == NULL){
cout空间分配错误！endl;
exit(1);
}
CreateBinTree_PreOrder(subTree-lChild);//递归创建左子树
CreateBinTree_PreOrder(subTree-rChild); //递归创建右子树
}
else{//遇到结束符，当前结点设置为空
subTree == NULL;
}
}
}
2.3 先序遍历与中序遍历创造二叉树
关于两个遍历创建二叉树的我只举一个例子，其他的类比即可
已知一棵二叉树的先序遍历序列和中序遍历序列分别是abdgcefh、dgbaechf，求二叉树及后序遍历序列。
第一次循环：
（因为先序的头为根结点，故可以从中序区分左右子树）
先序：a bdg cefh
中序：dgb a echf
第二次循环：
bdg中：先序：b dg
中序：dg b
cefh中：先序：c e fh
中序：e c hf
第三次循环
dg中：先序：d g
中序：d g
fh中：先序：f h
中序：h f
void CreateBinTreeBy_Pre_In(const char *pre, const char *in){
int n = strlen(pre);
CreateBinTreeBy_Pre_In(root, pre, in, n);
}
void CreateBinTreeBy_Pre_In(BinTreeNodeT *cur, const char *pre, const char *in, int n){
if (n = 0){//创建结束
cur = NULL;
return;
}
int k = 0;
while (pre[0] != in[k]) {//在中序中找到pre[0]的值（也就是前序的根节点）
k++;
}
cur = new BinTreeNodeT(in[k]); //创建结点（为前序的pre[0]）
CreateBinTreeBy_Pre_In(cur-lChild, pre + 1, in, k);
CreateBinTreeBy_Pre_In(cur-rChild, pre + k + 1, in + k + 1, n - k - 1);
}
2.4 中序遍历与后序遍历创建二叉树
思路同上，没什么好讲的
void CreateBinTreeBy_Post_In(const char *post, const char *in){
int n = strlen(post);
CreateBinTreeBy_Post_In(root, post, in, n);
}
void CreateBinTreeBy_Post_In(BinTreeNodeT *cur, const char *post, const char *in, int n){
if (n == 0){
cur = NULL;
return;
}
char r = *(post + n - 1);//根结点值
cur = new BinTreeNodeT(r); //构造当前结点
int k = 0;
const char *p = in;
while (*p != r){
k++;
p++;
}
CreateBinTreeBy_Post_In(cur-lChild, post, in, k);
CreateBinTreeBy_Post_In(cur-rChild, post + k, p + 1, n - k - 1);
}
（(c++)二叉树（一））宝，都看到这里了你确定不收藏一下？？