A. 二叉树用C++如何实现
二叉树是程序应用得比较多的一种结构。它可以反映物体之间的层次结构，还能通过孩子和双亲反映两物体之间某些特殊关系；排序二叉树还能帮助我们进行排序，并因此而提供快速的查找；二叉树基础上的伸展树能不断地优化我们系统的结构。并查集能很好地让进行分类；小根堆能帮助快速找到值最小的结点，它是优先队列的雏形。所有的这些都是以二叉树为基础的。
实现的二叉树的基本功能包括前中后序的递归和非递归访问，求结点个数和叶子结点个数，还有求树高。这些是用C++类实现的。
BTree.h文件(类声明文件)
[cpp]viewplain
#ifndefBTREE_H
#defineBTREE_H
structBTreeNode
{
intdata;
BTreeNode*lChild,*rChild;
};
classBTree
{public:
voidsetRoot(BTreeNode*r){root=r;}
BTreeNode*getRoot(){returnroot;}
//中序遍历(递归)
voidinOrder();
//中序遍历(非递归)
voidNotReInOrder();
BTreeNode*createBTree();
//前序遍历(递归)
voidpreOrder();
//前序遍历(非递归)
voidNotRePreOrder();
//后序遍历(递归)
voidpostOrder();
//后序遍历(非递归)
voidNotRePostOrder();
//求结点个数
intBTreeSize();
//求叶子结点个数
intBTreeLeaves();
//求树高
intBTreeHeight();
//层次法求树高
intlayerHeight();
protected:
//中序遍历
voidinOrder(BTreeNode*);
//前序遍历
voidpreOrder(BTreeNode*);
//后序遍历
voidpostOrder(BTreeNode*);
//结点个数
intBTreeSize(BTreeNode*);
//叶子结点
intBTreeLeaves(BTreeNode*);
//树高
intBTreeHeight(BTreeNode*);
private:
BTreeNode*root;
};
#endif
BTree.cpp(类的实现文件)
[cpp]viewplain
#include<iostream>
#include<stack>
#include<queue>
#include"BTree.h"
usingnamespacestd;
//建立二叉树的算法
BTreeNode*BTree::createBTree()
{
BTreeNode*current=0;
intval=0;
cin>>val;
//-1的个数比数值的个数多1
if(val==-1)
returnNULL;
else
{
current=newBTreeNode;
current->data=val;
current->lChild=createBTree();
current->rChild=createBTree();
returncurrent;
}
}
//利用重载的方法
voidBTree::inOrder()
{
inOrder(root);
cout<<endl;
}
//中序访问二叉树(递归)
voidBTree::inOrder(BTreeNode*r)
{
if(r!=0)//是if，而不是while
{
inOrder(r->lChild);//递归访问
cout<<r->data<<"";
inOrder(r->rChild);//递归访问
}
}
//中序遍历(非递归)
voidBTree::NotReInOrder()
{
stack<BTreeNode*>s;
BTreeNode*r=getRoot();
while(!s.empty()||r!=0)
{
while(r!=0)
{
s.push(r);
r=r->lChild;
}
if(!s.empty())
{
r=s.top();
s.pop();
cout<<r->data<<"";
r=r->rChild;
}
}
}
//重载形式
voidBTree::preOrder()
{
preOrder(root);
cout<<endl;
}
//前序递归访问二叉树(递归)
voidBTree::preOrder(BTreeNode*r)
{
if(r!=0)//是if，而不是while
{
cout<<r->data<<"";
preOrder(r->lChild);//递归访问
preOrder(r->rChild);//递归访问
}
}
//前序遍历(非递归)
voidBTree::NotRePreOrder()
{
stack<BTreeNode*>s;
BTreeNode*r=getRoot();
s.push(r);
while(!s.empty())
{
r=s.top();
s.pop();
cout<<r->data<<"";
if(r->rChild!=0)
s.push(r->rChild);
if(r->lChild!=0)
s.push(r->lChild);
}
}
//重载形式
voidBTree::postOrder()
{
postOrder(root);
cout<<endl;
}
//后序遍历(递归)
voidBTree::postOrder(BTreeNode*r)
{
if(r!=0)//是if，而不是while
{
postOrder(r->lChild);//递归访问
postOrder(r->rChild);//递归访问
cout<<r->data<<"";
}
}
//后序非递归访问要定义新的结构体类型
structNode
{
BTreeNode*tp;
boolflag;
};
//后序遍历(非递归)
voidBTree::NotRePostOrder()
{
Nodenode;//定义Node结构体的一个结点
stack<Node>s;
BTreeNode*r=getRoot();
while(!s.empty()||r!=0)
{
while(r!=0)
{
node.tp=r;
node.flag=0;
s.push(node);
r=r->lChild;
}
if(!s.empty())
{
node=s.top();
s.pop();
r=node.tp;//将栈顶的BTreeNode*部分赋给r
if(node.flag==1)
{
cout<<r->data<<"";
r=0;//表示已经访问了该结点
}
else
{
node.flag=1;
s.push(node);
r=r->rChild;
}
}
}
}
//重载形式
intBTree::BTreeSize()
{
returnBTreeSize(root);
}
//求二叉树结点个数的函数
intBTree::BTreeSize(BTreeNode*r)
{
//二叉树的结点个数为左右子树的高度之和再+1
if(r==0)return0;
else
return1+BTreeSize(r->lChild)+BTreeSize(r->rChild);
}
//重载形式
intBTree::BTreeLeaves()
{
returnBTreeLeaves(root);
}
//求二叉树叶子结点个数的函数
intBTree::BTreeLeaves(BTreeNode*r)
{
//当为空时，返回0；当找到叶子时返回1
if(r==0)return0;
else
if(r->lChild==0&&r->rChild==0)
return1;
else
returnBTreeLeaves(r->lChild)+BTreeLeaves(r->rChild);
}
//重载形式
intBTree::BTreeHeight()
{
returnBTreeHeight(root);
}
//求二叉树高度的函数
intBTree::BTreeHeight(BTreeNode*r)
{
if(r==0)return0;
else
{
//二叉树的高度为左右子树的最大者+1
intlHei=BTreeHeight(r->lChild);
intrHei=BTreeHeight(r->rChild);
return(lHei>rHei)?lHei+1:rHei+1;
}
}//层次遍历求树高需要利用的新结构
structLayerBTreeNode
{
BTreeNode*ptr;
intheight;
};
//层次遍历求高度
intBTree::layerHeight()
{
queue<LayerBTreeNode>que;
LayerBTreeNodetemp,lTemp,rTemp;//牺牲空间来获得算法的清晰度
BTreeNode*r=getRoot();
inthei=1;
temp.ptr=r;
temp.height=1;
que.push(temp);//先将根对应的LayerBTreeNode对象进队
//不为空时
while(!que.empty())
{
//BTreeNode*btreePtr=0;
temp=que.front();//取出队首元素
que.pop();
r=temp.ptr;
//用当前的高度跟取出的队首进行比较
if(hei<temp.height)
hei=temp.height;
if(r->lChild!=0||r->rChild!=0)
{
//如果它的左右子树不为空，则进队列
if(r->lChild!=0)
{
lTemp.ptr=r->lChild;
lTemp.height=temp.height+1;//在原来高度基础上加1,再入队列
que.push(lTemp);
}
if(r->rChild!=0)
{
rTemp.ptr=r->rChild;
rTemp.height=temp.height+1;
que.push(rTemp);
}
}
}
returnhei;
}
B. 实现二叉树的创建，插入，删除，以及遍历访问二叉树
这个书上的实验操作都有啊 ！ 应该是很简单的代码····
C. 二叉树的后序遍历是怎样访问的还有哪几类分类啊高手指教~~~
左子树->右子树->根（如果子树不是叶子节点就递归这个过程）
其他的还有：
先序遍历：根->左->右
中序遍历：左->根->右
D. 访问二叉树的类（C++）
老楼……
E. 二叉树的访问
这个问题我以前回答过了
凑合着看吧
很显然你还不懂的遍历一棵二叉树的原理
当你拿到一棵二叉树，无论它的形状如何的千奇百怪
我们都可以将它按照如下的方式划分
根
/ \
左子树 右子树
一棵有很多个节点的二叉树可以划分为以上的形式
也可以这么理解，只要是按以上形式组合的都可以称为是二叉树
一个仅仅只有根节点的二叉树也可以划分成以上的形式，只不过他的左右子树都为空罢了
所以，我们发现，二叉树的定义其实是一个递归定义的过程
大的二叉树是由小的二叉树构建而成的
所以，当我们考虑要遍历一棵二叉树时
也是首选递归的遍历
遍历二叉树
它的基本思想是先按照上面的形式把整棵二叉树划分为3部分
哪么接下来的工作就很简单了
我们只需要将这3部分都遍历一遍就可以了（这里用到了分而治之的思想）
而对于这3部分来说
根节点的遍历无疑是最方便的，直接访问就ok了
而对于左右子树呢？
我们不难发现，左右子树其实分别成为了两棵完整的树
他们拥有各自独立的根节点，左子树和右子树
对他们的遍历，很显然应该与刚才的遍历方法一致便可
（如果上面的都理解了，那么这个题就是小菜一碟了，如果觉得无法理解，可以按照下面的方法自己多分解几棵树）
对于这个题目，中序遍历这可二叉树
先看根节点
1
/ \
左子树 右子树
我们应该先遍历左子树
也就是下面这棵树
2
/ \
4 5
对于这棵树在进行中序遍历
我们应先遍历她的左子树
他只有一个根节点4，左右子树都为空
哪么遍历这个只有一个根节点的二叉树
先访问她的左子树，为空
返回
访问该树的根节点4
在访问右子树也为空
此时，这棵树已经被完全的遍历了
我们需要返回上一层也就是
2
/ \
4 5
这棵树
此时，她的左子树已经被访问完毕
根据中序遍历的规则
需要访问此树的根节点2
此时的访问顺序是4-2
访问了根节点
在访问右子树只有一个根节点的5（具体过程看4的访问）
5访问完毕
也就意味着
2
/ \
4 5
这棵树已经访问完了
需要返回上一层
也就是1为根的树
此时这棵树的左子树已经访问完毕
此时访问的顺序是4-2-5应该没有问题
接下来访问根节点1
在访问右子树
3
/ \
4 7
是不是觉得似曾相识？？？
她的访问应该跟
2
/ \
4 5
一致
哪么最终遍历的顺序也出来了
4-2-5-1-6-3-7
-----------------------------
花了10多分钟
希望对你有所帮助
顺便自己也复习下
呵呵
匿名 �0�2<span class="tm">6-02 15:05</span>
</p>
<div>
<div class="ra ft"><div class="bt bg1"><img alt="相关内容" class="m" height="16" src="/static/img/ico3.gif" width="16"/>相关内容</div></div>
<p class="ft">
F. 关于二叉树的中序遍历和后序遍历的访问，是如何进行的
关于二叉树递归遍历问题，很早以前就说过原理了
请参考传送门：
http://..com/question/89674628.html
G. 二叉树怎么看
树与二叉树
树是一种简单的非线性结构，所有元素之间具有明显的层次特性。
在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。
在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。
二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
二叉树的基本性质：
（1）在二叉树的第k层上，最多有2k-1(k≥1)个结点；
（2）深度为m的二叉树最多有2m-1个结点；
（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；
（4）具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分；
（5）具有n个结点的完全二叉树的深度为[log2n]+1；
（6）设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，….n给结点进行编号（k=1,2….n），有以下结论：
①若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为int(k/2)；
②若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）；
③若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。
满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。
完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。
二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。
二叉树的遍历：
（1）前序遍历（dlr），首先访问根结点，然后遍历左子树，最后遍历右子树；
（2）中序遍历（ldr），首先遍历左子树，然后访问根结点，最后遍历右子树；
（3）后序遍历（lrd）首先遍历左子树，然后访问遍历右子树，最后访问根结点。
H. 二叉树的创建与访问算法的设计
Node{
Node* left;
Node* right;
int value;
};
void traverse(Node* tree)
{
if( !tree) return;
traverse(tree->left);
traverse(tree->right);
// do something here on tree->value -> e.g.
printf("%d\n", tree->value);
}
Finish entering tree elements by yourself.
I. 系统按照什么顺序访问二叉树的各个节点
依据前序遍历的顺序，得出a为根节点
通过中序遍历的顺序确定a的左右子树分别为bdg和cefh
再依次通过前序遍历的顺序和中序遍历的顺序确定各子树的分支，得原二叉树为
a
／
＼
b
c
／
／
＼
d
e
f
＼
／
g
h
则其后序遍历为gdbehfca
选a
J. 二叉树相关知识
二叉树 (binary tree) 是另一种树型结构，它的特点是每个结点至多只有二棵子 树 (即二叉树中不存在度大于 2的结点 )，并且，二叉树的子树有左右之分，其次序不能任意颠倒 . 二叉树是一种数据结构 :
Binary_tree=(D,R)
其中： D是具有相同特性的数据元素的集合 ;若 D等于空 ,则 R等于空称为空的二叉树 ;若 D等于空则 R是 D上某个二元关系 H的集合，即 R={H}，且
(1) D 中存在唯一的称为根的元素 r，它的关系 H下无前驱 ;
(2) 若 D-{r}不等于空，则 D-{r}={Dl,Dr}，且 Dl交 Dr等于空 ;
(3) 若 Dl不等于空 ,则在 Dl中存在唯一的元素 xl,〈 r,xl〉属于 H，且存在 Dl上的关系 Hl属于 H； 若 Dr不等于空 ,则在 Dr中存在唯一的元素 xr,〈 r,xr〉 >属于 H, 且存 Dr上的关 系 Hr属于 H； H={r,xl,＜ r,xr＞ ,Hl, Hr};
(4) (Dl, Hl) 是一棵合本定义的二叉树，称为根 r的左子树 ,(Dr,Hr)是一棵符合定义的二叉树，称为根的右子树。
其中，图 6.2 是各种形态的二叉树 .
(1) 为空二叉树 (2)只有一个根结点的二叉树 (3)右子树为空的二叉树 (4)左子树为空的二叉树 (5)完全二叉树
二叉树的基本操作：
(1)INITIATE(BT ） 初始化操作。置 BT为空树。
(2)ROOT(BT)\ROOT(x) 求根函数。求二叉树 BT的根结点或求结点 x所在二叉树的根结点。
若 BT是空树或 x不在任何二叉树上，则函数值为 “空 ”。
(3)PARENT(BT,x) 求双亲函数。求二叉树 BT中结点 x的双亲结点。若结点 x是二叉树 BT 的根结点
或二叉树 BT中无 x结点，则函数值为 “空 ”。
(4)LCHILD(BT,x) 和 RCHILD(BT,x) 求孩子结点函数。分别求二叉树 BT中结点 x的左孩 子和右孩子结点。
若结点 x为叶子结点或不在二叉树 BT中，则函数值为 “空 ”。
(5)LSIBLING(BT,x) 和 RSIBING(BT,x) 求兄弟函数。分别求二叉树 BT中结点 x的左兄弟和右兄弟结点。
若结点 x是根结点或不在 BT中或是其双亲的左 /右子树根 ,则函树值 为 “空 ”。
(6)CRT_BT(x,LBT,RBT) 建树操作。生成一棵以结点 x为根，二叉树 LBT和 RBT分别为左， 右子树的二叉树。
(7)INS_LCHILD(BT,y,x) 和 INS_RCHILD(BT,x) 插入子树操作。将以结点 x为根且右子树为空的二叉树
分别置为二叉树 BT中结点 y的左子树和右子树。若结点 y有左子树 /右子树，则插入后是结点 x的右子树。
(8)DEL_LCHILD(BT,x) 和 DEL-RCHILD(BT,x) 删除子树操作。分别删除二叉树 BT中以结点 x为根的左子树或右子树。
若 x无左子树或右子树，则空操作。
(9)TRAVERSE(BT) 遍历操作。按某个次序依此访问二叉树中各个结点，并使每个结点只被访问一次。
(10)CLEAR(BT) 清除结构操作。将二叉树 BT置为空树。
5.2.2 二叉树的存储结构
一 、顺序存储结构
连续的存储单元存储二叉树的数据元素。例如图 6.4(b)的完全二叉树 , 可以向量 (一维数组 ) bt(1:6)作它的存储结构，将二叉树中编号为 i的结点的数据元素存放在分量 bt[i]中 ,如图 6.6(a) 所示。但这种顺序存储结构仅适合于完全二叉树 ,而一般二叉树也按这种形式来存储 ,这将造成存 贮浪费。如和图 6.4(c)的二叉树相应的存储结构图 6.6(b)所示，图中以 “0”表示不存在此结点 .
二、 链式存储结构
由二叉树的定义得知二叉树的结点由一个数据元素和分别指向左右子树的两个分支构成 ,则表 示二叉树的链表中的结点至少包含三个域 :数据域和左右指针域 ,如图 (b)所示。有时 ,为了便于找 到结点的双亲 ,则还可在结点结构中增加一个指向其双亲受的指针域，如图 6.7(c)所示。
5.3 遍历二叉树
遍历二叉树 (traversing binary tree)的问题， 即如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。 其中常见的有三种情况：分别称之为先 (根 )序遍历，中 (根 )序遍历和后 (根 )序遍历。
5.3.1 前序遍历
前序遍历运算：即先访问根结点，再前序遍历左子树，最后再前序遍历右子树。前序遍历运算访问二叉树各结点是以根、左、右的顺序进行访问的。例如：
按前序遍历此二叉树的结果为： Hello!How are you?
proc preorder(bt:bitreprtr)
if (bt<>null)[
print(bt^);
preorder(bt^.lchild);
preorder(bt^.rchild);]
end;
5.3.2 中序遍历
中序遍历运算：即先中前序遍历左子树，然后再访问根结点，最后再中序遍历右子树。中序遍历运算访问二叉树各结点是以左、根、右的顺序进行访问的。例如：
按中序遍历此二叉树的结果为： a*b-c
proc inorder(bt:bitreprtr)
if (bt<>null)[
inorder(bt^.lchild);
print(bt^);
niorder(bt^.rchild);]
end;
5.3.3 后序遍历
后序遍历运算：即先后序遍历左子树，然后再后序遍历右子树，最后访问根结点。后序遍历运算访问二叉树各结点是以左、右、根的顺序进行访问的。例如：
按后序遍历此二叉树的结果为： Welecome to use it!
proc postorder(bt:bitreprtr)
if (bt<>null)[
postorder(bt^.lchild);
postorder(bt^.rchild);]
print(bt^);
end;
五、例：
1.用顺序存储方式建立一棵有31个结点的满二叉树，并对其进行先序遍历。
2.用链表存储方式建立一棵如图三、4所示的二叉树，并对其进行先序遍历。
3.给出一组数据：R={10.18,3,8,12,2,7,3}，试编程序，先构造一棵二叉树，然后以中序遍历访问所得到的二叉树，并输出遍历结果。
4.给出八枚金币a,b,c,d,e,f,g,h，编程以称最少的次数，判定它们蹭是否有假币，如果有，请找出这枚假币，并判定这枚假币是重了还是轻了。