首頁猿問需要建立一棵二叉樹，但是要求先建立...

需要建立一棵二叉樹，但是要求先建立一個(gè)空樹InitTree()和銷毀樹DestroyTree()函數(shù)

Java 算法

天涯盡頭無女友 2022-03-18 14:11:50

建立一棵二叉樹，要求先建立一個(gè)空樹InitTree()和銷毀樹DestroyTree()函數(shù)，然后用先序方法構(gòu)造一棵二叉樹，然后按中序遍歷的方式輸出這棵樹。

查看完整描述

2 回答

一只名叫tom的貓

TA貢獻(xiàn)1906條經(jīng)驗(yàn) 獲得超3個(gè)贊

#include<iostream>
using namespace std;
// 二叉樹結(jié)點(diǎn)類
struct BinTreeNode
{
// 數(shù)據(jù)成員:
double data; // 數(shù)據(jù)域
BinTreeNode *leftChild; // 左孩子指針域
BinTreeNode *rightChild; // 右孩子指針域
BinTreeNode(){ leftChild = rightChild = NULL;}; // 無參數(shù)的構(gòu)造函數(shù)
BinTreeNode(double &val,BinTreeNode *lChild = NULL, BinTreeNode *rChild = NULL);
};

BinTreeNode::BinTreeNode(double &val, BinTreeNode *lChild,BinTreeNode *rChild)
{
data = val; // 數(shù)據(jù)元素值
leftChild = lChild; // 左孩子
rightChild = rChild; // 右孩子
}
//節(jié)點(diǎn)類，其數(shù)據(jù)成員為二叉節(jié)點(diǎn)類型的指針
struct Node
{
BinTreeNode *data; // 數(shù)據(jù)域
Node *next; // 指針域
Node(){ next = NULL;};
Node( BinTreeNode *item, Node *link = NULL){ data = item; next = link;};
};
//隊(duì)列類，作為層次遍歷的輔助數(shù)據(jù)結(jié)構(gòu)用
class LinkQueue
{
protected:
Node *front, *rear;
public:
LinkQueue(){rear = front = new Node; };
void OutQueue(BinTreeNode * &e); // 出隊(duì)操作
void InQueue(BinTreeNode * &e); // 入隊(duì)操作
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;
// 輔助函數(shù):
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; // 隊(duì)列
BinTreeNode *t = root; // 從根結(jié)點(diǎn)開始進(jìn)行層次遍歷

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; // 銷毀根結(jié)點(diǎn)
r = NULL;
}
}

int main(void)
{ double e;
BinTreeNode *cur;
cout<<"請輸入根節(jié)點(diǎn)的數(shù)值:";
cin>>e;
cur = new BinTreeNode(e);
BinaryTree bt(e); // 建立二叉樹
cur = bt.GetRoot();
cout<<"請輸入根節(jié)點(diǎn)左孩子的數(shù)值:";
cin>>e;
bt.InsertLeftChild(cur, e);
cout<<"請輸入根節(jié)點(diǎn)右孩子的數(shù)值:";
cin>>e;
bt.InsertRightChild(cur, e);
cout<<"請輸入根節(jié)點(diǎn)左孩子的左孩子的數(shù)值:";
cin>>e;
bt.InsertLeftChild(cur->leftChild, e);
cout<<"請輸入根節(jié)點(diǎn)右孩子的左孩子的數(shù)值:";
cin>>e;
bt.InsertLeftChild(cur->rightChild, e);
cout<<"請輸入根節(jié)點(diǎn)右孩子的右孩子的數(shù)值:";
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<<"樹中節(jié)點(diǎn)數(shù)為"<<bt.NodeCount()<<endl;
cout<<"樹中葉子節(jié)點(diǎn)數(shù)為"<<bt.leafNodeCount()<<endl;
return 0;
}
在計(jì)算機(jī)科學(xué)中，二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實(shí)現(xiàn)二叉查找樹和二叉堆。
二叉樹的每個(gè)結(jié)點(diǎn)至多只有二棵子樹(不存在度大于2的結(jié)點(diǎn))，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2^{i-1}個(gè)結(jié)點(diǎn)；深度為k的二叉樹至多有2^k-1個(gè)結(jié)點(diǎn)；對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n_0，度為2的結(jié)點(diǎn)數(shù)為n_2，則n_0=n_2+1。
一棵深度為k，且有2^k-1個(gè)節(jié)點(diǎn)稱之為滿二叉樹；深度為k，有n個(gè)節(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)節(jié)點(diǎn)都與深度為k的滿二叉樹中，序號為1至n的節(jié)點(diǎn)對應(yīng)時(shí)，稱之為完全二叉樹。

反對回復(fù) 2022-03-23

慕沐林林

TA貢獻(xiàn)2016條經(jīng)驗(yàn) 獲得超9個(gè)贊

#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);
}