建立二叉链表存储下图所示的二叉树，并用递归算法对其进行前序、中序、后序遍历。要求

Question

建立二叉链表存储下图所示的二叉树，并用递归算法对其进行前序、中序、后序遍历。要求二叉树的数据从键盘输入，并将遍历序列输出。
图

Answer 1

#include<stdio.h>
#include<stdlib.h>
typedef struct bitnode
{
char data;
struct bitnode *lchild,*rchild;
}bitnode,*bitree;//二叉树节点类型和节点指针类型

bitree create()//先序创建
{
bitree root=NULL;
char c;
scanf("%c",&c);
fflush(stdin);
if(c=='#')return NULL;
else
{
root=(bitnode*)malloc(sizeof(bitnode));
root->data=c;
root->lchild=create();
root->rchild=create();
}
return root;
}

void preorder(bitree root)//先根遍历
{
if(!root)return;
else
{
putchar(root->data);
preorder(root->lchild);
preorder(root->rchild);
}
}

void inorder(bitree root)//中根遍历
{
if(!root)return;
else
{
inorder(root->lchild);
putchar(root->data);
inorder(root->rchild);
}
}

void postorder(bitree root)//后根遍历
{
if(!root)return;
else
{
postorder(root->lchild);
postorder(root->rchild);
putchar(root->data);
}
}

int leafcount(bitree root)//计算叶子节点
{
if(!root)return 0;
else
{
if(!root->lchild&&!root->rchild)return 1;
else return leafcount(root->lchild)+leafcount(root->rchild);
}
}

int depth(bitree root)//树的高度
{
if(!root)return 0;
else
{
int m=depth(root->lchild);
int n=depth(root->rchild);
return (m>n?m:n)+1;
}
}

void Revolute(bitree root)// 交换左右子树
{
bitree t;
t=root->lchild;
root->lchild=root->rchild;
root->rchild=t;
if(root->lchild)Revolute(root->lchild);
if(root->rchild)Revolute(root->rchild);
}

void main()
{

bitree root=NULL;
printf("输入先序序列：\n");
root=create();

printf("前序遍历：\n");
preorder(root);
printf("\n");

printf("中序遍历：\n");
inorder(root);
printf("\n");

printf("后序遍历：\n");
postorder(root);
printf("\n");

printf("二叉树的叶子结点个数为:%d\n",leafcount(root));
printf("二叉树的高度为:%d\n",depth(root));

printf("交换左右子树后\n");
Revolute(root);

printf("前序遍历：\n");
preorder(root);
printf("\n");

printf("中序遍历：\n");
inorder(root);
printf("\n");

printf("后序遍历：\n");
postorder(root);
printf("\n");
system("pause");
}

Answer 2

#include<iostream>
using namespace std;
// 二叉树结点类
struct BinTreeNode
{
// 数据成员:
double data; // 数据域
BinTreeNode *leftChild; // 左孩子指针域
BinTreeNode *rightChild; // 右孩子指针域
BinTreeNode(){ leftChild = rightChild = NULL;}; // 无参数的构造函数
BinTreeNode(double &val,BinTreeNode *lChild = NULL, BinTreeNode *rChild = NULL);
};

BinTreeNode::BinTreeNode(double &val, BinTreeNode *lChild,BinTreeNode *rChild)
{
data = val; // 数据元素值
leftChild = lChild; // 左孩子
rightChild = rChild; // 右孩子
}
//节点类，其数据成员为二叉节点类型的指针
struct Node
{
BinTreeNode *data; // 数据域
Node *next; // 指针域
Node(){ next = NULL;};
Node( BinTreeNode *item, Node *link = NULL){ data = item; next = link;};
};
//队列类，作为层次遍历的辅助数据结构用
class LinkQueue
{
protected:
Node *front, *rear;
public:
LinkQueue(){rear = front = new Node; };
void OutQueue(BinTreeNode * &e); // 出队操作
void InQueue(BinTreeNode * &e); // 入队操作
bool Empty(){return front==rear;};
};

void LinkQueue::OutQueue(BinTreeNode * &e)
{ Node *tmpPtr = front->next;
e = tmpPtr->data;
front->next = tmpPtr->next;
if (rear == tmpPtr)
{
rear = front;
}
delete tmpPtr;
}

void LinkQueue::InQueue(BinTreeNode * &e)
{
Node *tmpPtr = new Node(e);
rear->next = tmpPtr;
rear = tmpPtr;
}
// 二叉树类
class BinaryTree
{
protected:
BinTreeNode *root;
// 辅助函数:
void DestroyHelp(BinTreeNode * &r);
void PreOrderHelp(BinTreeNode *r) const ;
void InOrderHelp(BinTreeNode *r) const ;
void PostOrderHelp(BinTreeNode *r) const ;
int HeightHelp(const BinTreeNode *r) const;
int NodeCountHelp(const BinTreeNode *r) const;
int leafNodeCountHelp(const BinTreeNode *r) const;

public:
BinaryTree();
virtual ~BinaryTree();
BinTreeNode *GetRoot() const;
void InOrder() const;
void PreOrder() const;
void PostOrder() const;
void LevelOrder() const;
int NodeCount() const;
int leafNodeCount() const;
void InsertLeftChild(BinTreeNode *cur, double &e);
void InsertRightChild(BinTreeNode *cur, double &e);
int Height() const;
BinaryTree( double &e);
};

BinaryTree ::BinaryTree()
{
root = NULL;
}

BinaryTree ::~BinaryTree()
{
DestroyHelp(root);
}

BinTreeNode *BinaryTree ::GetRoot() const
{
return root;
}

void BinaryTree ::PreOrderHelp(BinTreeNode *r) const

{
if (r != NULL)
{
cout<<(r->data)<<" ";
PreOrderHelp(r->leftChild);
PreOrderHelp(r->rightChild);
}
}

void BinaryTree ::PreOrder() const
{
PreOrderHelp(root);
}

void BinaryTree ::InOrderHelp(BinTreeNode *r) const
{
if (r != NULL)
{
InOrderHelp(r->leftChild);
cout<<(r->data)<<" ";
InOrderHelp(r->rightChild);
}
}

void BinaryTree ::InOrder() const
{
InOrderHelp(root);
}

void BinaryTree ::PostOrderHelp(BinTreeNode *r) const
{
if (r != NULL)
{
PostOrderHelp(r->leftChild);
PostOrderHelp(r->rightChild);
cout<<(r->data)<<" ";
}
}

void BinaryTree ::PostOrder() const
{
PostOrderHelp(root);
}

void BinaryTree ::LevelOrder() const
{
LinkQueue q; // 队列
BinTreeNode *t = root; // 从根结点开始进行层次遍历

if (t != NULL) q.InQueue(t);
while (!q.Empty())
{ q.OutQueue(t);
cout<<(t->data)<<" ";
if (t->leftChild != NULL)
q.InQueue(t->leftChild);
if (t->rightChild != NULL)
q.InQueue(t->rightChild);
}
}

int BinaryTree ::HeightHelp(const BinTreeNode *r) const
{
if(r == NULL)
{ return 0;
}
else
{ int lHeight, rHeight;
lHeight = HeightHelp(r->leftChild); // 左子树的高
rHeight = HeightHelp(r->rightChild); // 右子树的高
return (lHeight > rHeight ? lHeight : rHeight) + 1;
}
}

int BinaryTree ::Height() const
{
return HeightHelp(root);
}

BinaryTree ::BinaryTree( double &e)
{
root = new BinTreeNode (e);
}

int BinaryTree ::NodeCountHelp(const BinTreeNode *r) const
{
if (r ==NULL) return 0;
else return NodeCountHelp(r->leftChild) + NodeCountHelp(r->rightChild) + 1;
}

int BinaryTree ::NodeCount() const
{
return NodeCountHelp(root);
}
int BinaryTree ::leafNodeCountHelp(const BinTreeNode *r) const
{ int lt,rt;
if (r==NULL) return 0;
else if(r->leftChild==NULL &&r->rightChild==NULL)
return 1;
else
{lt=leafNodeCountHelp(r->leftChild);
rt=leafNodeCountHelp(r->leftChild);
return lt+rt;}
}

int BinaryTree ::leafNodeCount() const
{
return leafNodeCountHelp(root);
}

void BinaryTree ::InsertLeftChild(BinTreeNode *cur, double &e)
{
if (cur == NULL)
{
return;
}
else
{ // 插入左孩子
BinTreeNode *child = new BinTreeNode (e);
if (cur->leftChild != NULL)
{child->leftChild = cur->leftChild;
}
cur->leftChild = child;
return;
}
}

void BinaryTree ::InsertRightChild(BinTreeNode *cur, double &e)
{
if (cur == NULL)
{ return;
}
else
{ // 插入右孩子
BinTreeNode *child = new BinTreeNode (e);
if (cur->rightChild != NULL)
{ child->rightChild = cur->rightChild;
}
cur->rightChild = child;
return;
}
}

void BinaryTree ::DestroyHelp(BinTreeNode *&r)
{
if(r != NULL)
{ DestroyHelp(r->leftChild); // 销毁左子树
DestroyHelp(r->rightChild); // 销毁右子树
delete r; // 销毁根结点
r = NULL;
}
}

int main(void)
{ double e;
BinTreeNode *cur;
cout<<"请输入根节点的数值:";
cin>>e;
cur = new BinTreeNode(e);
BinaryTree bt(e); // 建立二叉树
cur = bt.GetRoot();
cout<<"请输入根节点左孩子的数值:";
cin>>e;
bt.InsertLeftChild(cur, e);
cout<<"请输入根节点右孩子的数值:";
cin>>e;
bt.InsertRightChild(cur, e);
cout<<"请输入根节点左孩子的左孩子的数值:";
cin>>e;
bt.InsertLeftChild(cur->leftChild, e);
cout<<"请输入根节点右孩子的左孩子的数值:";
cin>>e;
bt.InsertLeftChild(cur->rightChild, e);
cout<<"请输入根节点右孩子的右孩子的数值:";
cin>>e;
bt.InsertRightChild(cur->rightChild,e);
cout << "先序遍历:" << endl;
bt.PreOrder();
cout<<endl;
system("PAUSE");

cout << "中序遍历:" << endl;
bt.InOrder();
cout<<endl;
system("PAUSE");

cout << "后序遍历:" << endl;
bt.PostOrder();
cout<<endl;
system("PAUSE");

cout << "层次遍历:" << endl;
bt.LevelOrder();
cout<<endl;
system("PAUSE");
cout<<"树的高度为"<<bt.Height()<<endl;
cout<<"树中节点数为"<<bt.NodeCount()<<endl;
cout<<"树中叶子节点数为"<<bt.leafNodeCount()<<endl;
return 0;
}本回答被提问者和网友采纳

Answer 3

创大业千秋昌盛 展宏图再就辉煌 横批：大展宏图