遍历的结果是：ABDCEF
中序遍历先从左子树开始，然后到根，再到右子树。
遍历的结果是：DBAECF
后序遍历先从左子树开始，然后到右子树，再到根。
遍历的结果是：DBEFCA
打印自己，然后先遍历左节点再遍历右节点
这里的栈用处是为了保存二叉树的结构，以弥补二叉树无法获取父节点的结构特性。
不过需要注意的是后入栈的为左孩子，以保证优先遍历左侧。
第一个栈的处理顺序为，自上而下，自右而左。经过第二个栈的逆序，就变成了自下而上，自左而右。
每次将新节点加入队列时，将nlast更新成新节点。
当当前打印的节点等于last，执行换行并将last更新到下一行nlast。
举个例子(用 ! 分割，用 # 表空):
将序列化字符串转化成数组(比如这里通过 ! 分割)
所以我们需要引入一个变量 setleft 来确定下一次需要构建的节点方向。
每次构建新节点之后，下一次都会尝试构建其左侧节点。
而每次遇到空节点后，都会将顶元素推出，并尝试构建其的右侧节点。
因为他的队列，只负责记录下一次想要处理的节点。
并不需要在意左右与层级倒退，只需要处理节点为空的情况即可。
如下图中第三棵二叉树。
2节点的子树下方，左侧高度为2，右侧高度为0。所以不是一个平衡二叉树。
一旦一侧子节点为空，另一侧若高度大于2，则判定为否
目的都是提高搜索二叉树的效率，调整代价降低。
第一个错误的节点为第一次降序较大的节点
第二个错误的节点为第二次降序较小的节点
第一个错误的节点为此次降序较大的节点
第二个错误的节点为此次降序较小的节点
除最后一层无任何子 节点 外，每一层上的所有结点都有两个子结点二叉树。
从图形形态上看，满二叉树外观上是一个三角形
这种满二叉树的层数为L，节点数为N。
则N = 2^L-1 ,L = log(N+1)
满二叉树的结点要么是叶子结点，度为0，要么是度为2的结点，不存在度为1的结点。
在满二叉树的基础上，最后一层所有的结点都连续集中在最左边，这就是完全二叉树。
先遍历左子树左边界，再遍历右子树左边界。从而判断哪边为满二叉树。
满二叉树侧，N=2^H。非满二叉树侧，递归。
每层只遍历一个节点的子树，总计LogN。
每个子树获取右子树左边界遍，需要经历LogN次计算。
总复杂度O((LogN^2))
如果从下标从1开始存储，则编号为i的结点的主要关系为：
双亲：下取整 （i/2）
左孩子：2i
右孩子：2i+1
如果从下标从0开始存储，则编号为i的结点的主要关系为：
双亲：下取整 （(i-1)/2）
左孩子：2i+1
右孩子：2i+2
2的后序节点为3，2的前驱节点为1
下图中2，1两节点距离为2。3，5节点距离为5
三个情况下最大的结果，就是以head为头节点的整棵树上最远的距离。
Swift 算法实战之路：二叉树
左神牛课网算法课
#include<stdioh>
#include<stdlibh>
typedef struct node tree_pointer;
struct node{
char ch;
tree_pointer left_child,right_child;
};
tree_pointer root=NULL;
tree_pointer create(tree_pointer ptr)
{
char ch;
scanf("%c",&ch);
if(ch==' ')
ptr=NULL;
else{
ptr=(tree_pointer)malloc(sizeof(node));
ptr->ch=ch;
ptr->left_child=create(ptr->left_child);
ptr->right_child=create(ptr->right_child);
}
return ptr;
}
void preorder(tree_pointer ptr)
{
if(ptr){
printf("%c",ptr->ch);
preorder(ptr->left_child);
preorder(ptr->right_child);
}
}
void inorder(tree_pointer ptr)
{
if(ptr){
inorder(ptr->left_child);
printf("%c",ptr->ch);
inorder(ptr->right_child);
}
}
void postorder(tree_pointer ptr)
{
if(ptr){
postorder(ptr->left_child);
postorder(ptr->right_child);
printf("%c",ptr->ch);
}
}
void main()
{
printf("构建一个二叉树（结点数为n)：\n");
root=create(root);
printf("前序遍历二叉树：\n");
preorder(root);
printf("\n");
printf("中序遍历二叉树：\n");
inorder(root);
printf("\n");
printf("后序遍历二叉树：\n");
postorder(root);
printf("\n");
}
#include<iostreamh>
#include<malloch>
#define FALSE 0
#define TRUE 1
#define OK 1
#define maxsize 100
typedef int status;
typedef int elemtype;
typedef struct binode
{
elemtype data;
struct binode lchild,rchild;
}binode,bitree;
status treecreated=FALSE;
int leafcount=0;
status createbitree(bitree t);
status preordertraverse(bitree t);
int height(bitree t);
void swap(bitree t);
void leafcounts(bitree t);
void main()
{
int choice=0;
status leave=FALSE,flag;
binode bt;
cout<<"===========二叉树演示程序==============="<<endl;
do
{
cout<<"1：创建一个二叉树，按先序遍历结果输入，空用0表示 "<<endl;
cout<<"2：先序遍历二叉树，递归方式遍历二叉树 "<<endl;
cout<<"3：求叶子数"<<endl;
cout<<"4：计算二叉树的高度"<<endl;
cout<<"5: 树进行左右翻转"<<endl;
cout<<"0：退出"<<endl;
cout<<"-------请输入你的选择:"<<endl;
cin>>choice;
switch(choice)
{
case 1:
if(treecreated)
{
cout<<"sorry,the tree has been already created!"<<endl;
break;
};
cout<<"请输入代表树的数字："<<endl;
flag=createbitree(&bt);
if(flag==OK)
{
cout<<"你已经建立了一棵树了！"<<endl;
treecreated=TRUE;
}
break;
case 2:
if(!treecreated)
{
cout<<"sorry,you must create a tree for further steps!"<<endl;
break;
}
cout<<"先序遍历顺序:"<<endl;
preordertraverse(bt);
cout<<endl;
break;
case 3:
if(!treecreated)
{
cout<<"sorry,you must create a tree for further steps!"<<endl;
break;
}
leafcounts(bt);
cout<<"树的叶子数:"<<leafcount<<endl;
cout<<endl;
break;
case 4:
int h;
h=height(bt);
cout<<"树的高度:"<<h<<endl;
break;
case 5:
swap(&bt);
cout<<"树已经翻转！！！"<<endl;
break;
case 0:
leave=TRUE;
break;
}
}while(!leave);
cout<<" 谢谢 再见了！！！"<<endl;
}
//递归方法实现创建
status createbitree(bitree t)
{
int ch=0;
cin>>ch;
if(ch==0) //输入如果是0表示是空
(t)=NULL;
else
{
(t)=(bitree)malloc(sizeof(binode)); //申请空间
(t)->data=ch; //把数据传给他
createbitree(&(t)->lchild); //左孩子重新进入创建函数
createbitree(&(t)->rchild); //右孩子重新进入创建函数
}
return OK;
}
//递归方法实现先序遍历
status preordertraverse(bitree t)
{
if(t)
{
cout<<t->data<<" "; //先把头结点输出
preordertraverse(t->lchild); //然后是左结点
preordertraverse(t->rchild); //然后是右结点
return OK;
}
else
return OK;
}
int height(bitree t)
{
（以下有一段代码，自己先看看学学吧）
数据结构C语言版 二叉树的顺序存储表示和实现
P126
编译环境：Dev-C++ 4992
日期：2011年2月13日
/
#include <stdioh>
typedef char TElemType;
// 二叉树的顺序存储表示
#define MAX_TREE_SIZE 100 // 二叉树的最大结点数
typedef TElemType SqBiTree[MAX_TREE_SIZE]; // 0号单元存储根结点
typedef struct
{
int level, //结点的层
order; //本层序号(按满二叉树计算)
}position;
typedef int QElemType;
// 队列的顺序存储结构(可用于循环队列和非循环队列)
#define MAXQSIZE 5 // 最大队列长度(对于循环队列，最大队列长度要减1)
typedef struct
{
QElemType base; // 初始化的动态分配存储空间 相当于一个数组
int front; // 头指针,若队列不空,指向队列头元素，相当于一个数组下标
int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置
// 相当于一个数组下标
}SqQueue;
#define ClearBiTree InitBiTree // 在顺序存储结构中，两函数完全一样
TElemType Nil = ' '; // 设空为字符型的空格符
// 构造空二叉树T。因为T是固定数组，不会改变，故不需要&
int InitBiTree(SqBiTree T)
{
int i;
for(i=0;i<MAX_TREE_SIZE;i++)
T[i]=Nil; // 初值为空
return 1;
}
void DestroyBiTree()
{
// 由于SqBiTree是定长类型,无法销毁
}
// 按层序次序输入二叉树中结点的值(字符型或整型), 构造顺序存储的二叉树T
int CreateBiTree(SqBiTree T)
{
int i = 0, l;
char s[MAX_TREE_SIZE];
printf("请按层序输入结点的值(字符)，空格表示空结点，结点数≤%d:\n",
MAX_TREE_SIZE);
printf("例如：abcefgh\n");
gets(s); // 输入字符串
l = strlen(s); // 求字符串的长度
for(;i<l;i++) // 将字符串赋值给T
{
T[i]=s[i];
// 此结点(不空)无双亲且不是根,T[(i+1)/2-1] == Nil表示T[i]无双亲
if(i!=0 && T[(i+1)/2-1] == Nil && T[i] != Nil)
{
printf("出现无双亲的非根结点%c\n",T[i]);
exit(0);
}
}
for(i=l;i<MAX_TREE_SIZE;i++) // 将空赋值给T的后面的结点
T[i]=Nil;
return 1;
}
// 若T为空二叉树,则返回1,否则0
int BiTreeEmpty(SqBiTree T)
{
if(T[0]==Nil) // 根结点为空,则树空
return 1;
else
return 0;
}
// 返回T的深度
int BiTreeDepth(SqBiTree T)
{
int i,j=-1;
for(i=MAX_TREE_SIZE-1;i>=0;i--) // 找到最后一个结点
if(T[i] != Nil)
break;
i++; // 为了便于计算
do
j++;
while(i>=pow(2,j)); //i > pow(2, depth-1) && i <= pow(2, depth)
return j; //j = depth;
}
// 当T不空,用e返回T的根,返回1;否则返回0,e无定义
int Root(SqBiTree T,TElemType e)
{
if(BiTreeEmpty(T)) // T空
return 0;
else
{
e=T[0];
return 1;
}
}
// 返回处于位置e(层,本层序号)的结点的值
TElemType Value(SqBiTree T,position e)
{
// 将层、本层序号转为矩阵的序号
return T[((int)pow(2,elevel-1) - 1) + (eorder - 1)];
// ((int)pow(2,elevel-1) - 1)为该elevel的结点个数，
// (eorder - 1)为本层的位置
}
// 给处于位置e(层,本层序号)的结点赋新值value
int Assign(SqBiTree T,position e,TElemType value)
{
// 将层、本层序号转为矩阵的序号
int i = (int)pow(2,elevel-1) + eorder - 2;
if(value != Nil && T[(i+1)/2-1] == Nil) // 叶子非空值但双亲为空
return 0;
else if(value == Nil && (T[i2+1] != Nil || T[i2+2] != Nil))
// 双亲空值但有叶子（不空）
return 0;
T[i]=value;
return 1;
}
// 若e是T的非根结点,则返回它的双亲,否则返回＂空＂
TElemType Parent(SqBiTree T,TElemType e)
{
int i;
if(T[0]==Nil) // 空树
return Nil;
for(i=1;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e) // 找到e
return T[(i+1)/2-1];
return Nil; // 没找到e
}
// 返回e的左孩子。若e无左孩子,则返回＂空＂
TElemType LeftChild(SqBiTree T,TElemType e)
{
int i;
if(T[0]==Nil) // 空树
return Nil;
for(i=0;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e) // 找到e
return T[i2+1];
return Nil; // 没找到e
}
// 返回e的右孩子。若e无右孩子,则返回＂空＂
TElemType RightChild(SqBiTree T,TElemType e)
{
int i;
if(T[0]==Nil) // 空树
return Nil;
for(i=0;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e) // 找到e
return T[i2+2];
return Nil; // 没找到e
}
// 返回e的左兄弟。若e是T的左孩子或无左兄弟,则返回＂空＂
TElemType LeftSibling(SqBiTree T,TElemType e)
{
int i;
if(T[0]==Nil) // 空树
return Nil;
for(i=1;i<=MAX_TREE_SIZE-1;i++)
if(T[i] == e && i%2 == 0) // 找到e且其序号为偶数(是右孩子)
return T[i-1];
return Nil; // 没找到e
}
// 返回e的右兄弟。若e是T的右孩子或无右兄弟,则返回＂空＂
TElemType RightSibling(SqBiTree T,TElemType e)
{
int i;
if(T[0]==Nil) // 空树
return Nil;
for(i=1;i<=MAX_TREE_SIZE-1;i++)
if(T[i]==e&&i%2) // 找到e且其序号为奇数(是左孩子)
return T[i+1];
return Nil; // 没找到e
}
// 把从q的j结点开始的子树移为从T的i结点开始的子树
// InsertChild()用到
void Move(SqBiTree q,int j,SqBiTree T,int i)
{
if(q[2j+1] != Nil) // q的左子树不空
Move(q,(2j+1),T,(2i+1)); // 把q的j结点的左子树移为T的i结点的左子树
if(q[2j+2] != Nil) // q的右子树不空
Move(q,(2j+2),T,(2i+2)); // 把q的j结点的右子树移为T的i结点的右子树
T[i]=q[j]; // 把q的j结点移为T的i结点
q[j]=Nil; // 把q的j结点置空
}
// 根据LR为0或1,插入c为T中p结点的左或右子树。p结点的原有左或
// 右子树则成为c的右子树
int InsertChild(SqBiTree T,TElemType p,int LR,SqBiTree c)
{
int j,k,i=0;
for(j=0;j<(int)pow(2,BiTreeDepth(T))-1;j++) // 查找p的序号
if(T[j]==p) // j为p的序号
break;
k=2j+1+LR; // k为p的左或右孩子的序号
if(T[k] != Nil) // p原来的左或右孩子不空
Move(T,k,T,2k+2); // 把从T的k结点开始的子树移为从k结点的右子树开始的子树
Move(c,i,T,k); // 把从c的i结点开始的子树移为从T的k结点开始的子树
return 1;
}
// 构造一个空队列Q
int InitQueue(SqQueue Q)
{
(Q)base=(QElemType )malloc(MAXQSIZEsizeof(QElemType)); //分配定长的空间，相当于一个数组
if(!(Q)base) // 存储分配失败
exit(0);
(Q)front=(Q)rear=0; //初始化下标
return 1;
}
// 插入元素e为Q的新的队尾元素
int EnQueue(SqQueue Q,QElemType e)
{
if((Q)rear>=MAXQSIZE)
{ // 队列满，增加1个存储单元
(Q)base=(QElemType )realloc((Q)base,((Q)rear+1)sizeof(QElemType));
if(!(Q)base) // 增加单元失败
return 0;
}
((Q)base+(Q)rear)=e;
(Q)rear++;
return 1;
}
// 若队列不空,则删除Q的队头元素,用e返回其值,并返回1,否则返回0
int DeQueue(SqQueue Q,QElemType e)
{
if((Q)front==(Q)rear) // 队列空
return 0;
e=(Q)base[(Q)front];
(Q)front=(Q)front+1;
return 1;
}
// 根据LR为1或0,删除T中p所指结点的左或右子树
int DeleteChild(SqBiTree T,position p,int LR)
{
int i;
int k=1; // 队列不空的标志
SqQueue q;
InitQueue(&q); // 初始化队列，用于存放待删除的结点
i=(int)pow(2,plevel-1)+porder-2; // 将层、本层序号转为矩阵的序号
if(T[i]==Nil) // 此结点空
return 0;
i=i2+1+LR; // 待删除子树的根结点在矩阵中的序号
while(k)
{
if(T[2i+1]!=Nil) // 左结点不空
EnQueue(&q,2i+1); // 入队左结点的序号
if(T[2i+2]!=Nil) // 右结点不空
EnQueue(&q,2i+2); // 入队右结点的序号
T[i]=Nil; // 删除此结点
k=DeQueue(&q,&i); // 队列不空
}
return 1;
}
int(VisitFunc)(TElemType); // 函数变量
void PreTraverse(SqBiTree T,int e)
{
// PreOrderTraverse()调用
VisitFunc(T[e]); //先调用函数VisitFunc处理根
if(T[2e+1]!=Nil) // 左子树不空
PreTraverse(T,2e+1); //然后处理左子树
if(T[2e+2]!=Nil) // 右子树不空
PreTraverse(T,2e+2);
}
// 先序遍历T,对每个结点调用函数Visit一次且仅一次。
int PreOrderTraverse(SqBiTree T,int(Visit)(TElemType))
{
VisitFunc=Visit;
if(!BiTreeEmpty(T)) // 树不空
PreTraverse(T,0);
printf("\n");
return 1;
}
// InOrderTraverse()调用
void InTraverse(SqBiTree T,int e)
{
if(T[2e+1]!=Nil) // 左子树不空
InTraverse(T,2e+1);
VisitFunc(T[e]);
if(T[2e+2]!=Nil) // 右子树不空
InTraverse(T,2e+2);
}
// 中序遍历T,对每个结点调用函数Visit一次且仅一次。
int InOrderTraverse(SqBiTree T,int(Visit)(TElemType))
{
VisitFunc=Visit;
if(!BiTreeEmpty(T)) // 树不空
InTraverse(T,0);
printf("\n");
return 1;
}
// PostOrderTraverse()调用
void PostTraverse(SqBiTree T,int e)
{
if(T[2e+1]!=Nil) // 左子树不空
PostTraverse(T,2e+1);
if(T[2e+2]!=Nil) // 右子树不空
PostTraverse(T,2e+2);
VisitFunc(T[e]);
}
// 后序遍历T,对每个结点调用函数Visit一次且仅一次。
int PostOrderTraverse(SqBiTree T,int(Visit)(TElemType))
{
VisitFunc = Visit;
if(!BiTreeEmpty(T)) // 树不空
PostTraverse(T,0);
printf("\n");
return 1;
}
// 层序遍历二叉树
void LevelOrderTraverse(SqBiTree T,int(Visit)(TElemType))
{
int i=MAX_TREE_SIZE-1,j;
while(T[i] == Nil)
i--; // 找到最后一个非空结点的序号
for(j=0;j<=i;j++) // 从根结点起,按层序遍历二叉树
if(T[j] != Nil)
Visit(T[j]); // 只遍历非空的结点
printf("\n");
}
// 逐层、按本层序号输出二叉树
void Print(SqBiTree T)
{
int j,k;
position p;
TElemType e;
for(j=1;j<=BiTreeDepth(T);j++)
{
printf("第%d层: ",j);
for(k=1; k <= pow(2,j-1);k++)
{
plevel=j;
porder=k;
e=Value(T,p);
if(e!=Nil)
printf("%d:%c ",k,e);
}
printf("\n");
}
}
int visit(TElemType e)
{
printf("%c ",e);
return 0;
}
int main()
{
int i,j;
position p;
TElemType e;
SqBiTree T,s;
InitBiTree(T);
CreateBiTree(T);
printf("建立二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",
BiTreeEmpty(T),BiTreeDepth(T));
i=Root(T,&e);
if(i)
printf("二叉树的根为：%c\n",e);
else
printf("树空，无根\n");
printf("层序遍历二叉树:\n");
LevelOrderTraverse(T,visit);
printf("中序遍历二叉树:\n");
InOrderTraverse(T,visit);
printf("后序遍历二叉树:\n");
PostOrderTraverse(T,visit);
printf("请输入待修改结点的层号 本层序号: ");
scanf("%d%d%c",&plevel,&porder);
e=Value(T,p);
printf("待修改结点的原值为%c请输入新值: ",e);
scanf("%c%c",&e);
Assign(T,p,e);
printf("先序遍历二叉树:\n");
PreOrderTraverse(T,visit);
printf("结点%c的双亲为%c,左右孩子分别为",e,Parent(T,e));
printf("%c,%c,左右兄弟分别为",LeftChild(T,e),RightChild(T,e));
printf("%c,%c\n",LeftSibling(T,e),RightSibling(T,e));
InitBiTree(s);
printf("建立右子树为空的树s:\n");
CreateBiTree(s);
printf("树s插到树T中,请输入树T中树s的双亲结点 s为左(0)或右(1)子树: ");
scanf("%c%d%c",&e,&j);
InsertChild(T,e,j,s);
Print(T);
printf("删除子树,请输入待删除子树根结点的层号 本层序号 左(0)或右(1)子树: ");
scanf("%d%d%d%c",&plevel,&porder,&j);
DeleteChild(T,p,j);
Print(T);
ClearBiTree(T);
printf("清除二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n",
BiTreeEmpty(T),BiTreeDepth(T));
i=Root(T,&e);
if(i)
printf("二叉树的根为：%c\n",e);
else
printf("树空，无根\n");
system("pause");
return 0;
}
/
输出效果：
请按层序输入结点的值(字符)，空格表示空结点，结点数≤100:
例如：abcefgh
abcdefgh
建立二叉树后,树空否？0(1:是 0:否) 树的深度=4
二叉树的根为：a
层序遍历二叉树:
a b c d e f g h
中序遍历二叉树:
h d b e a f c g
后序遍历二叉树:
h d e b f g c a
请输入待修改结点的层号 本层序号: 3 2
待修改结点的原值为e请输入新值: i
先序遍历二叉树:
a b d h i c f g
结点i的双亲为b,左右孩子分别为 , ,左右兄弟分别为d,
建立右子树为空的树s:
请按层序输入结点的值(字符)，空格表示空结点，结点数≤100:
例如：abcefgh
jk l
树s插到树T中,请输入树T中树s的双亲结点 s为左(0)或右(1)子树: i 0
第1层: 1:a
第2层: 1:b 2:c
第3层: 1:d 2:i 3:f 4:g
第4层: 1:h 3:j
第5层: 5:k
第6层: 9:l
删除子树,请输入待删除子树根结点的层号 本层序号 左(0)或右(1)子树: 2 1 0
第1层: 1:a
第2层: 1:b 2:c
第3层: 2:i 3:f 4:g
第4层: 3:j
第5层: 5:k
第6层: 9:l
清除二叉树后,树空否？1(1:是 0:否) 树的深度=0
树空，无根
请按任意键继续
/
#include<iostream>
#include<map>
using namespace std;
const int N=15e3+100;
struct node{
int v;//结点值
int l,r;//左右孩子的下标
st()
{//初始化
l=r=-1;
}
}tree[4N];//4倍空间,用来储存二叉树
map<int,int>mp;//储存数值在数组a中的下标
int a[N];//基础数组,数组tree在其基础上建树
int n=1;//1 5 8 0 0 0 6 0 0
void build_tree(int rt,int &num)
{//构建二叉树
if(a[num]==0)
{//a[num]==0,表示空结点
tree[rt]v=-1;
}
else
{
if(mpcount(a[num])==0)
mp[a[num]]=rt;//储存a[num]在树中的位置
tree[rt]v=a[num];//结点赋值
num++;
build_tree(2rt,num);//左孩子
num++;
build_tree(2rt+1,num);//右孩子
}
}
/
1 5 8 0 0 0 6 0 0
3
8 1 6
/
int main()
{
int x=1,m=0;
do
{
cin>>a[n++];//储存结点值
}
while(getchar()!='\n');//回车结束输入
build_tree(1,x);//构建二叉树(结构体数组模拟)
cin>>m;//查询次数
for(int i=0;i<m;i++)
{
int num,y;
cin>>num;//查询值
y=mp[num];//mp[num]是num在tree数组中的位置,查询效率O(log2n)
y/=2;//左右孩子的下标除以2，就是父节点的下标
if(y==0)
{//父节点下标为0，既是根节点
cout<<0<<endl;
}
else
{//输出父节点值
cout<<tree[y]v<<endl;
}
}
return 0;
}
自己写的，运行通过，MFC的有点难弄，将就着用吧。
queueh//链式队列用于层序遍历树
// queueh: interface for the queue class
//
//////////////////////////////////////////////////////////////////////
#if !defined(AFX_QUEUE_H__6515EF6D_27AA_4799_95F8_6FE216E99F0F__INCLUDED_)
#define AFX_QUEUE_H__6515EF6D_27AA_4799_95F8_6FE216E99F0F__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include <iostreamh>
#include <asserth>
template<class T>
struct LinkNode
{
T data;
LinkNode<T> link;
LinkNode(LinkNode<T> ptr = NULL){link = ptr;}//仅初始化指针成员的初始函数
LinkNode(const T& item,LinkNode<T> ptr = NULL)
{data = item;link = ptr;} //初始化数据与指针成员的构造函数
};
template <class T>
class queue
{
private:
LinkNode<T> front,rear;//
public:
queue():rear(NULL),front(NULL){};//
~queue(){makeempty();};//
bool EnQueue(T &x);//
bool DeQueue(T &x);//
bool getFront(T &x);//
void makeempty();//
bool Isempty()const{return front==NULL;}//
int getSize()const;//
friend ostream &operator<<(ostream &os,queue<T> &q);//
};
template<class T>
void queue<T>::makeempty()
{
LinkNode<T> p;
while(front!=NULL)
{
p=front;
front=front->link;
delete p;
}
}
template <class T>
bool queue<T>::EnQueue(T &x)
{
if(front==NULL)
{
front=rear=new LinkNode<T>(x);
if(front==NULL)
return false;
}
else
{
rear->link=new LinkNode<T>(x);
if(rear==NULL)
return false;
rear=rear->link;
}
return true;
}
template <class T>
bool queue<T>::DeQueue(T &x)
{
if(Isempty())return false;
LinkNode<T> p=front;
x=front->data;
front=front->link;
delete p;
return true;
}
template<class T>
bool queue<T>::getFront(T &x)
{
if(Isempty())return false;
x=front->data;
return true;
}
template <class T>
int queue<T>::getSize() const
{
LinkNode<T> p=front;
int k=0;
while(p)
{
k++;
p=p->link;
}
return k;
}
#endif // !defined(AFX_QUEUE_H__6515EF6D_27AA_4799_95F8_6FE216E99F0F__INCLUDED_)
BinaryTreeh
// BinaryTreeh: interface for the BinaryTree class
//
//////////////////////////////////////////////////////////////////////
#if !defined(AFX_BINARYTREE_H__61FEB349_65EE_40FB_82DF_25FFBCBDFC6E__INCLUDED_)
#define AFX_BINARYTREE_H__61FEB349_65EE_40FB_82DF_25FFBCBDFC6E__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include <iostreamh>
typedef int T;
struct BinTreeNode
{
T data;
BinTreeNode leftChild,rightChild;
BinTreeNode():leftChild(NULL),rightChild(NULL){}
BinTreeNode(T x,BinTreeNode l=NULL,BinTreeNode r=NULL):data(x),leftChild(l),rightChild(r){}
};
class BinaryTree {
public:
BinaryTree():root(NULL){} //
BinaryTree(T value):RefValue(value) ,root(NULL){} //
~BinaryTree(){destroy(root);}/////////
void CreateBinTree(){CreateBinTree(root);}
bool IsEmpty(){return(root==NULL)true:false;}////////
BinTreeNode Parent(BinTreeNode current)/////////
{return(root==NULL||root==current)NULL:Parent(root,current);}//////
BinTreeNode LeftChild(BinTreeNode current)////
{return(current!=NULL)current->leftChild:NULL;}
BinTreeNode RightChild(BinTreeNode current)///////
{return(current!=NULL)current->rightChild:NULL;}
int Height(){return Height(root);}///////
int Size(){return Size(root);}///////
BinTreeNode getRoot()const{return root;}///////
void preOrder()///////
{preOrder(root);}
void inOrder()///////
{inOrder(root);}
void postOrder()///
{postOrder(root);}
void levelOrder()/////
{levelOrder(root);}
void destroy(){destroy(root);};
int Leaves (){return leaves(root);}
protected:
BinTreeNode root;
T RefValue;
void CreateBinTree(BinTreeNode &subTree);
bool Insert(BinTreeNode &subTree,const T &x);////////
void destroy(BinTreeNode &subTree);/////
bool Find(BinTreeNode &subTree,const T &x);///////
BinTreeNode Copy(BinTreeNode orignode);///////
int Height(BinTreeNode subTree);////////
int Size(BinTreeNode subTree);///////
BinTreeNode Parent(BinTreeNode Parent,BinTreeNode current);//////
BinTreeNode Find(BinTreeNode &subTree,const T &x)const;////////
void Traverse(BinTreeNode &subTree,ostream &out);///////
void preOrder(BinTreeNode &subTree);///////
void inOrder(BinTreeNode &subTree);///////
void postOrder(BinTreeNode &subTree);///////
void levelOrder(BinTreeNode &subtree);
int leaves(BinTreeNode &subTree);
};
#endif // !defined(AFX_BINARYTREE_H__61FEB349_65EE_40FB_82DF_25FFBCBDFC6E__INCLUDED_)
BinaryTreecpp
// BinaryTreecpp: implementation of the BinaryTree class
//
//////////////////////////////////////////////////////////////////////
#include "BinaryTreeh"
#include<stdlibh>
#include "queueh"
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
void BinaryTree::CreateBinTree(BinTreeNode &subTree) /////////建立二叉树
{
T item;
cin>>item;
if(item!=RefValue)
{
subTree=new BinTreeNode(item);
if(subTree==NULL)
{
cerr<<"存储分配错误！"<<endl;
exit(1);
}
CreateBinTree(subTree->leftChild);
CreateBinTree(subTree->rightChild);
}
else subTree=NULL;
}
void BinaryTree::destroy(BinTreeNode & subTree) ////删除二叉树
{
if(subTree!=NULL)
{
destroy(subTree->leftChild);
destroy(subTree->rightChild);
delete subTree;
}
}
BinTreeNode BinaryTree::Parent(BinTreeNode subTree, BinTreeNode current) //找父母结点
{
if(subTree==NULL) return NULL;
if(subTree->leftChild==current||subTree->rightChild==current)
return subTree;
BinTreeNode p;
if((p=Parent(subTree->leftChild,current))!=NULL) return p;
else return Parent(subTree->rightChild,current);
}
void BinaryTree::preOrder( BinTreeNode &subTree) //前序遍历
{
if(subTree!=NULL)
{
cout<<subTree->data<<" ";
preOrder(subTree->leftChild);
preOrder(subTree->rightChild);
}
}
void BinaryTree::inOrder( BinTreeNode &subTree) //中序遍历
{
if(subTree!=NULL)
{
inOrder(subTree->leftChild);
cout<<subTree->data<<" ";
inOrder(subTree->rightChild);
}
}
void BinaryTree::postOrder( BinTreeNode &subTree ) // 后序遍历
{
if(subTree!=NULL)
{
postOrder(subTree->leftChild);
postOrder(subTree->rightChild);
cout<<subTree->data<<" ";
}
}
void BinaryTree::levelOrder(BinTreeNode &subtree) //层序遍历
{
if(root==NULL)return;
queue<BinTreeNode> Q;
BinTreeNode p=root;
QEnQueue(p);
while(!QIsempty())
{
QDeQueue(p);
cout<<p->data<<" ";
if(p->leftChild)
QEnQueue(p->leftChild);
if(p->rightChild)
QEnQueue(p->rightChild);
}
}
int BinaryTree::Size(BinTreeNode subTree) //求结点个数
{
if(subTree==NULL) return 0;
else return 1+Size(subTree->leftChild)+Size(subTree->rightChild);
}
int BinaryTree::Height(BinTreeNode subTree) //求数的深度
{
if(subTree==NULL) return 0;
else
{
int i=Height(subTree->leftChild);
int j=Height(subTree->rightChild);
return (i>j)i+1:j+1;
}
}
int BinaryTree::leaves(BinTreeNode &subTree) //求叶子节点个数
{
if(subTree==NULL) return 0;
else if(subTree->leftChild==NULL&&subTree->rightChild==NULL)return 1;
else
{
int i=leaves(subTree->leftChild);
int j=leaves(subTree->rightChild);
return i+j;
}
}
主函数：
#include "BinaryTreeh"
int main_menu()
{
char option;
while(1)
{
cout<<" 主菜单"<<endl;
cout<<endl;
cout<<" 请选择 *** 作:"<<endl;
cout<<" 1 建立树:"<<endl;
cout<<" 2 清空树"<<endl;
cout<<" 3 退出"<<endl;
cin>>option;
switch(option)
{
case '1':
return 1;
case '2':
return 2;
case '3':
return 3;
default:
cout<<"输入错误，请检查输入!"<<endl;
break;
}
}
}
int tree_menu(BinaryTree &btn)
{
char option;
while(1)
{
cout<<" 树的相关 *** 作:"<<endl;
cout<<" 请选择 *** 作:"<<endl;
//cout<<" 1 输入节点"<<endl;
cout<<" 2 按前序输出"<<endl;
cout<<" 3 按中序输出"<<endl;
cout<<" 4 按后序输出"<<endl;
cout<<" 5 按层序输出"<<endl;
cout<<" 6 求节点个数"<<endl;
cout<<" 7 求树的深度"<<endl;
cout<<" 8 求树的高度"<<endl;
cout<<" 9 返回主菜单"<<endl;
cin>>option;
switch(option)
{
// case '1':
// {
// cout<<"输入节点,-1为结束标志"<<endl;
// btnCreateBinTree();
// break;
// }
case '2':
{
cout<<"按前序输出为:"<<endl;
btnpreOrder();
break;
}
case '3':
{
cout<<"按中序输出为:"<<endl;
btninOrder();
break;
}
case '4':
{
cout<<"按后序输出为:"<<endl;
btnpostOrder();
break;
}
case '5':
{
cout<<"按层序输出为:"<<endl;
btnlevelOrder();
break;
}
case '6':
{
cout<<"节点个数为:"<<btnSize()<<endl;
break;
}
case '7':
{
cout<<"求树的深度为:"<<btnHeight()<<endl;
break;
}
case '8':
{
cout<<"求树的高度为:"<<btnHeight()<<endl;
break;
}
case '9':
return 9;
default:
cout<<"输入有误，请检查输入!"<<endl;
break;
}
}
}
int main()
{
bool bCreated=false;
int op;
BinaryTree btn(-1);
while(1)
{
op=main_menu();
switch(op)
{
case 1:
{
if(!bCreated)
{
cout<<"1 输入节点,-1为结束标志"<<endl;
btnCreateBinTree();
}
bCreated=true;
tree_menu(btn);
break;
}
case 2:
{
btndestroy();
bCreated=false;
break;
}
case 3:
return 0;
}
}
return 0;
}
以上就是关于数据结构基础--二叉树全部的内容，包括:数据结构基础--二叉树、数据结构 c语言版二叉树(1) 建立一棵含有n个结点的二叉树，采用二叉链表存储；、数据结构 二叉树同构等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）