你这题目不全吧,我以前做的一个课程设计,其中的几个要求和你的一样,不过比你的多一些要求,已经通过了,你看看吧:
要求:
1. 创建二叉树的链表存储结构;
2. 实现二叉链表的初始化算法、二叉树空的判断算法;
3. 实现二叉树的先序遍历算法、中序遍历算法和后序遍历算法;
4. 利用某遍历算法实现计算二叉树中叶子结点、度为2的结点和度为1的结点的个数。
5. 求二叉树中结点个数。
6. 求二叉树的深度。
7. 设计一个算法,求二叉树中指定结点x的层数。
8. 设计一算法,求先序遍历序列中第k个结点的左右孩子。
9. 求结点x的所有祖先。
10.输出所有叶子结点到根结点的路径。
11.如果将二叉树中左分支标为0,右分支标为1,从叶子结点到根结点的路径由所经过的左、右分支组成。取左右分支的上0和1就构成了叶子结点的二进制编码。请输出二叉树中所有叶子结点的编码。
代码实现
#include <iostream>
using namespace std;
#define Elemtype char
struct TreeNode
{
Elemtype data;
struct TreeNode *lchrild,*rchrild,*preNode;
int record;
};
void IsEmptyTree(struct TreeNode *Node)
{
if(Node!=NULL) cout<<"树不为空!"<<endl;
else cout<<"树是空的。"<<endl;
}
struct TreeNode *CreateTree(struct TreeNode *preNode)
{ struct TreeNode *Node;
Elemtype data;
cin>>data;
if(data=='#') return 0;
else
{ Node=new struct TreeNode;
Node->data=data;
Node->preNode=preNode;
Node->lchrild=CreateTree(Node);
Node->rchrild=CreateTree(Node);
}
return Node;
}
void PreOrderTraverse(struct TreeNode *Node)
{
if(Node!=NULL)
{
cout<<Node->data<<" ";
PreOrderTraverse(Node->lchrild);
PreOrderTraverse(Node->rchrild);
}
}
void InOrderTraverse(struct TreeNode *Node)
{
if(Node!=NULL)
{
InOrderTraverse(Node->lchrild);
cout<<Node->data<<" ";
InOrderTraverse(Node->rchrild);
}
}
void LaterOrderTraverse(struct TreeNode *Node)
{
if(Node!=NULL)
{
LaterOrderTraverse(Node->lchrild);
LaterOrderTraverse(Node->rchrild);
cout<<Node->data<<" ";
}
}
void GetData(struct TreeNode *Node,int &i,Elemtype *Data)
{
if(Node!=NULL)
{
GetData(Node->lchrild,i,Data);
Data[i]=Node->data;
i++;
GetData(Node->rchrild,i,Data);
}
}
void CaculateTreeNode(struct TreeNode *Node,int &tNode,int &One,int &Two)
{
if(Node!=NULL)
{
if(Node->lchrild==NULL&&Node->rchrild==NULL) tNode++;
else if(Node->lchrild!=NULL&&Node->rchrild!=NULL) Two++;
else One++;
CaculateTreeNode(Node->lchrild,tNode,One,Two);
CaculateTreeNode(Node->rchrild,tNode,One,Two);
}
}
int TreeHight(struct TreeNode *Node)
{
int i,j;
if(Node==NULL) return 0;
else
{
i=TreeHight(Node->lchrild);
j=TreeHight(Node->rchrild);
}
return ((i>j)?i:j)+1;
}
struct TreeNode *FindNode(struct TreeNode *Node,Elemtype x)
{
struct TreeNode * result = 0;
if(Node==NULL)return 0;
else
{
if(Node->data==x) return Node;
result = FindNode(Node->lchrild,x);
if(result > 0)
return result;
return FindNode(Node->rchrild,x);
}
}
void PreTraverseFind(struct TreeNode *Node,int &i,int k,Elemtype &ch)
{
if(Node!=NULL)
{
i++;
if(i==k) ch=Node->data;
PreTraverseFind(Node->lchrild,i,k,ch);
PreTraverseFind(Node->rchrild,i,k,ch);
}
}
/*void PreTraverseFind(struct TreeNode *Node,int &i,int k,struct TreeNode *p)
{
if(Node!=NULL)
{
i++;
if(i==k) p=Node;
PreTraverseFind(Node->lchrild,i,k,p);
PreTraverseFind(Node->rchrild,i,k,p);
}
}*/
void TreeNodeLocate(struct TreeNode *xNode,struct TreeNode * Root,int &i)
{
if(xNode!=NULL)
{
i++;
if(xNode==Root) return;
TreeNodeLocate(xNode->preNode,Root,i);
}
}
void SearchChildren(struct TreeNode *Node)
{
if(Node->lchrild!=NULL) cout<<"左孩子:"<<Node->lchrild->data<<",";
else cout<<"没有左孩子,";
if(Node->rchrild!=NULL) cout<<"右孩子:"<<Node->rchrild->data<<"."<<endl;
else cout<<"没有右孩子."<<endl;
}
void SearchAllParents(struct TreeNode *xNode,struct TreeNode *Root,Elemtype ch)
{
if(xNode!=NULL)
{
if (xNode->data!=ch) cout<<xNode->data<<" ";
if(xNode==Root) return;
SearchAllParents(xNode->preNode,Root,ch);
}
}
//找所有叶子结点的路径
void FindAllWay(struct TreeNode *xNode,struct TreeNode *Root,Elemtype ch)
{
if(xNode!=NULL)
{
if (xNode!=Root) cout<<xNode->data<<"->";
else{ cout<<xNode->data<<endl; return;}
FindAllWay(xNode->preNode,Root,ch);
}
}
void FindNodeWay(struct TreeNode *Node,struct TreeNode *Root)
{
if(Node!=NULL)
{
if(Node->lchrild==NULL&&Node->rchrild==NULL)
{
FindAllWay(Node,Root,Node->data);//找到一个叶子结点就调用FindAllWay
}
FindNodeWay(Node->lchrild,Root);
FindNodeWay(Node->rchrild,Root);
}
}
void SetNodeRecord(struct TreeNode *Node,struct TreeNode *Root )
{
if(Node!=NULL)
{
if(Node!=Root)
{
if(Node==Node->preNode->lchrild) Node->record=0;
if(Node==Node->preNode->rchrild) Node->record=1;
}
SetNodeRecord(Node->lchrild,Root);
SetNodeRecord(Node->rchrild,Root);
}
}
void FindNodeBinary(struct TreeNode *xNode,struct TreeNode *Root,Elemtype ch)
{
if(xNode!=NULL)
{
if (xNode!=Root) cout<<xNode->record;
else{cout<<endl; return; }
FindNodeBinary(xNode->preNode,Root,ch);
}
}
void FindAllNodeBinary(struct TreeNode *Node,struct TreeNode *Root)
{
if(Node!=NULL)
{
if(Node->lchrild==NULL&&Node->rchrild==NULL) //找到叶子结点
{
FindNodeBinary(Node,Root,Node->data);
}
FindAllNodeBinary(Node->lchrild,Root);
FindAllNodeBinary(Node->rchrild,Root);
}
}
void main()
{
struct TreeNode *Node,*Root,*p;
int tNode=0,One=0,Two=0;
Elemtype ch;
int i=0,k,n;
cout<<"\n提示:以#表示一棵树有左叶子或者有右子,以##表示既无左叶子也没有右叶子,请输入该树的先序遍历方式,";
cout<<"(输入:A B C # # D E # G # # F # # #):"<<endl;
Root=Node=CreateTree(Node);
IsEmptyTree(Node);
cout<<"树的递归先序遍历结果:";
PreOrderTraverse(Node);
cout<<endl;
cout<<"树的递归中序遍历结果:";
InOrderTraverse(Node);
cout<<endl;
cout<<"树的递归后序遍历结果:";
LaterOrderTraverse(Node);
cout<<endl;
CaculateTreeNode(Node,tNode,One,Two);
cout<<"二叉树中叶子结点"<<tNode<<" "<<"度为2的结点"<<One<<" "<<"度为1的结点的个数"<<Two<<endl;
k=tNode+One+Two;
cout<<"总结点数为:"<<k<<endl;
cout<<"树的深度为:"<<TreeHight(Node)<<endl;
cout<<"你要判断哪个字符所在层次:";
Elemtype *Data=new Elemtype[k];
GetData(Node,i,Data);
cin>>ch;
i=0;
p=FindNode(Node,ch);
TreeNodeLocate(p,Root,i);
cout<<"你要查找的字符所在层次为:"<<i<<endl;
cout<<"请输入你要查找(线序遍历中)第几个结点的左右孩子:";
cin>>n;
/* 方法2:PreTraverseFind(Node,i,k,ch);//返回元素
Node=FindNode(Node,ch);//找到元素地址*/
while(1)
{
if(n<=k) break;
cout<<"你输入的结点树大于了该树的总结点树,请重新输入:";
cin>>n;
}
if(n<=k)
{
cout<<"结果:";
i=0;
//PreTraverseFind(Node,i,n,p);
PreTraverseFind(Node,i,n,ch);//返回元素
p=FindNode(Node,ch);//找到元素地址*/
SearchChildren(p);
}
cout<<"输入你要查找哪个结点的所有祖先:";
cin>>ch;
cout<<"你查询的所有祖先如下:";
p=FindNode(Root,ch);//找到ch的结点地址
SearchAllParents(p,Root,ch);
cout<<"\n所有叶子结点到跟结点的路径如下:"<<endl;
FindNodeWay(Root,Root);
cout<<"所有叶子结点的二进制编码如下:"<<endl;
SetNodeRecord(Root,Root );
FindAllNodeBinary(Root,Root);
}
追问我才运行了下,按照先序输入结点的时候,怎么回车显示不出来。?求解、