为了账号安全,请及时绑定邮箱和手机立即绑定

请问如果建立一棵二叉树,要求先建立一个空树InitTree()和销毁树DestroyTree()函数

请问如果建立一棵二叉树,要求先建立一个空树InitTree()和销毁树DestroyTree()函数

C# C
慕侠2389804 2022-01-21 15:15:16
建立一棵二叉树,要求先建立一个空树InitTree()和销毁树DestroyTree()函数,然后用先序方法构造一棵二叉树,然后按中序遍历的方式输出这棵树。
查看完整描述

2 回答

?
蝴蝶不菲

TA贡献1810条经验 获得超4个赞

#include<iostream>
using namespace std;
typedef char ElemType;
struct BTreeNode
{ ElemType data;
BTreeNode *leftChild;
BTreeNode *rightChild;
};

void InitTree(BTreeNode* T)
{
T=NULL;
}

void DestroyTree(BTreeNode* T)
{
if(T!=NULL) {
DestroyTree(T->leftChild);
DestroyTree(T->rightChild);
delete T;
}

}

void CreateBiTree(BTreeNode* &T)
{ ElemType mark;
cin>>mark;
if(mark=='$') T=NULL;
else {
T=new BTreeNode;
T->data=mark;
CreateBiTree(T->leftChild);
CreateBiTree(T->rightChild);
}
}

void InOrder(BTreeNode* T )
{
if(T!=NULL)
{
InOrder(T->leftChild);
cout<<T->data;
InOrder(T->rightChild);
}
}

void main()
{
BTreeNode *T=new BTreeNode;
InitTree(T);
cout<<"按先序序列输入:"<<endl;
cout<<"例如输入ABC$$DE$G$$F$$$"<<endl;
CreateBiTree(T);
cout<<"按中序序列输出:"<<endl;
InOrder(T );
cout<<endl;
DestroyTree(T);
}



查看完整回答
反对 回复 2022-01-23
?
慕斯王

TA贡献1864条经验 获得超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;
}
在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点;深度为k的二叉树至多有2^k-1个结点;对任何一棵二叉树T,如果其终端结点数为n_0,度为2的结点数为n_2,则n_0=n_2+1。
一棵深度为k,且有2^k-1个节点称之为满二叉树;深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称之为完全二叉树。



查看完整回答
反对 回复 2022-01-23
  • 2 回答
  • 0 关注
  • 223 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信