建立一棵二叉树，输出该二叉树的前序遍历、中序遍历和后序遍历以及层序遍历，并实现对结点全职的查找。

Question

火速求代码，哪位大大会的发我邮箱[email protected]
写错了，是结点权值的查找，要c++语言的。

Answer 1

template <class T>
struct BiNode //二叉树的结点结构
{
T data;
BiNode<T> *lchild, *rchild;
};
template <class T>
struct element
{
BiNode<T> *ptr;
int flag;
};
template <class T>
class BiTree
{
public:
BiTree( ); //构造函数，初始化一棵二叉树，其前序序列由键盘输入
~BiTree(void); //析构函数，释放二叉链表中各结点的存储空间
BiNode<T>* Getroot(); //获得指向根结点的指针
void PreOrder(BiNode<T> *root); //前序遍历二叉树
void InOrder(BiNode<T> *root); //中序遍历二叉树
void PostOrder(BiNode<T> *root); //后序遍历二叉树
void LeverOrder(BiNode<T> *root); //层序遍历二叉树
BiNode<T> * Find(BiNode<T> *&root,T item) ;//查找结点
private:
BiNode<T> *root; //指向根结点的头指针
BiNode<T> *Creat(); //有参构造函数调用
void Release(BiNode<T> *root); //析构函数调用
};

template<class T>
BiTree<T>::BiTree()
{
this->root = Creat();
}
template<class T>
BiNode<T>* BiTree<T>::Getroot( )
{
return root;
}
template <class T>
BiNode<T>* BiTree<T>::Creat( )
{
BiNode<T>* root;
T ch;
cout<<"请输入创建一棵二叉树的结点数据"<<endl;
cin >> ch;
if (ch=="#") root = NULL;
else{
root = new BiNode<T>; //生成一个结点
root->data=ch;
root->lchild = Creat(); //递归建立左子树
root->rchild = Creat(); //递归建立右子树
}
return root;
}

template<class T>
BiTree<T>::~BiTree(void)
{
Release(root);
}
template<class T>
void BiTree<T>::Release(BiNode<T>* root)
{
if (root != NULL){
Release(root->lchild); //释放左子树
Release(root->rchild); //释放右子树
delete root;
}
}

template <class T>
void BiTree<T>::PreOrder(BiNode<T> *root) //前序遍历
{
if (root == NULL) return;
else {
cout << root->data << ' ';
PreOrder(root->lchild);
PreOrder(root->rchild);
}
}

template <class T>
void BiTree<T>::InOrder(BiNode<T> * root) //中序遍历
{
if (root == NULL) return;
else {
InOrder(root->lchild);
cout << root->data << " ";
InOrder(root->rchild);
}
}

template <class T>
void BiTree<T>::PostOrder(BiNode<T> *root) //后续遍历
{
if (root == NULL) return;
else
{
PostOrder(root->lchild);
PostOrder(root->rchild);
cout << root->data << " ";
}
}

template <class T>
void BiTree<T>::LeverOrder(BiNode<T> *root) //层序遍历
{
const int MaxSize = 100;
int front = 0;
int rear = 0;
BiNode<T>* Q[MaxSize];
BiNode<T>* q;
if (root == NULL) return;
else{
Q[rear++] = root;
while (front != rear)
{
q = Q[front++];
cout<< q->data << " ";
if (q->lchild != NULL) Q[rear++] = q->lchild;
if (q->rchild != NULL) Q[rear++] = q->rchild;
}
}
}

template<class T>
BiNode<T> * BiTree::Find(BiNode<T> *&root,T item) //查找data为item的结点
{
if(root==NULL) return NULL;
if(Root->data==item) return root;
BiNode<T> *p;
if((p=Find(root->lchild,item))!=NULL) return p;
if((p=Find(root->rchild,item))!=NULL) return p;
return NULL;
}

Answer 2

111

Answer 3

你搞错了... 2k-1 是 2 的 k-1 次方

二叉树 第 k 层 最多有 2的k-1次方 个节点

深度为 k 的满二叉树 有 2的k次方 -1 个节点