数据结构-练习 5 二叉树的建立 遍历 (一)

二叉树是数据结构的最重要的内容之一，之所以引入二叉树，是因为良好的数据结构非常有助于数据的排序，查询等操作，也是在空间和效率上做个平衡！！

二叉树的定义：每个节点至多有俩颗子树（即二叉树中不存在度大于2的节点），并且，二叉树的子树有左右之分，其次序不能任意颠倒 形如：

节选自：《数据结构》 严蔚敏 图6.4

二叉树的分类：满二叉树，完全二叉树，一般二叉树（暂且列举简单的）。

（a）满二叉树，，根节点的度为1，叶节点的度为0，其余节点的度为2.

（b）完全二叉树：理解上很简单，在满二叉树的基础上，去掉序号靠后的节点，注意必须从倒数第一个点算起。b 就是，而c,d 都不是。因此c，d只是一般的二叉树。

二叉树的几个重要术语： 度，深度，根节点，双亲，叶节点，子树。

度：每个节点可以有的子节点的个数。深度：层数；根节点：最顶层的那个点；双亲：其实是一个节点，如(a)中4和5的双亲是2；叶节点：度为0的节点；子树：如(a),做标记的部分是1的子树。

树的相关性质：1，第i层上至多有2的（i-1）次方个节点；

2，深度为k的二叉树至多有2^k-1个节点；

3，度为0 的节点数n0,度为2的节点数n2，则n0=n2+1;

4，主要是关于节点之间的位置关系， 嗦一堆，其实很简单，就不再贴出来了。

树的建立和遍历：

包括前序 中序 和后序 ，其实就是元素访问的顺序，比如如上图 (d):前序 124536 , 中序：425136 ， 后序： 452631。简单画画就可以了。

代码如下：

[cpp] /*
email:shengbaiyang@163.com
qq:501968942
*/

#include
using namespace std;
struct Tnode
{
char value;
struct Tnode* lChild;
struct Tnode* rChild;

};
typedef Tnode* BiTree;

void InitBiTree(BiTree& T)
{


char inChar=getchar();
//# 表示空节点，但是也要输入，为了保证树的完整性
if(inChar=='#')
T=0;
else
{
T=(BiTree)malloc(sizeof(Tnode));
if(!T) throw "Invalid Address";
else
{
T->value=inChar;
InitBiTree(T->lChild);
InitBiTree(T->rChild);
}

}


}
//前序访问
void PreOrder(BiTree & T)
{

if(T)
{
cout<<"node is: "<value< PreOrder(T->lChild);
PreOrder(T->rChild);

}


}
//中虚访问
void InOrder(BiTree &T)
{

if(T)
{ InOrder(T->lChild);
cout<<"node is : "<value< InOrder(T->rChild);

}


}
//后续访问
void PostOrder(BiTree &T)
{

if(T)
{
PostOrder(T->lChild);
PostOrder(T->rChild);
cout<<"node is : "<value<


}


}


int main()
{



BiTree t;
cout<<"请输入节点值：";
InitBiTree(t);
cout<<"前序访问："< PreOrder(t);
cout<<"中序访问："< InOrder(t);
cout<<"后序访问："< PostOrder(t);




}

/*
email:shengbaiyang@163.com
qq:501968942
*/

#include
using namespace std;
struct Tnode
{
char value;
struct Tnode* lChild;
struct Tnode* rChild;

};
typedef Tnode* BiTree;

void InitBiTree(BiTree& T)
{

char inChar=getchar();
//# 表示空节点，但是也要输入，为了保证树的完整性
if(inChar=='#')
T=0;
else
{
T=(BiTree)malloc(sizeof(Tnode));
if(!T) throw "Invalid Address";
else
{
T->value=inChar;
InitBiTree(T->lChild);
InitBiTree(T->rChild);
}

}


}
//前序访问
void PreOrder(BiTree & T)
{

if(T)
{
cout<<"node is: "<value< PreOrder(T->lChild);
PreOrder(T->rChild);

}

}
//中虚访问
void InOrder(BiTree &T)
{

if(T)
{ InOrder(T->lChild);
cout<<"node is : "<value< InOrder(T->rChild);

}

}
//后续访问
void PostOrder(BiTree &T)
{

if(T)
{
PostOrder(T->lChild);
PostOrder(T->rChild);
cout<<"node is : "<value<


}

}

int main()
{

BiTree t;
cout<<"请输入节点值：";
InitBiTree(t);
cout<<"前序访问："< P