问题1
请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。
二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。
- 二叉树头文件
BinaryTree.h
#ifndef BT
#define BT
#include <iostream>
using namespace std;
//模板节点类
template <class Type>
class BinTreeNode
{
public:
BinTreeNode<Type> *leftChild=NULL, *rightChild=NULL;
Type data;
};
//模板二叉树类
template <class Type>
class BinaryTree
{
public:
BinTreeNode<Type> *root ;
BinaryTree(){ root = NULL;};
BinaryTree(BinTreeNode<Type> *r){root = r;}
BinaryTree(const Type& key){ BinTreeNode<Type> r(key); root = &r;}
void PreOrder(BinTreeNode<Type> *current);
void InOrder(BinTreeNode<Type> *current);
void PostOrder(BinTreeNode<Type> *current);
BinTreeNode<Type>* create();
void destroy(BinTreeNode<Type>* r);
};
//删除包含输入节点及以其为根节点的子树,后序删除
template <typename T>
void BinaryTree<T>::destroy(BinTreeNode<T>* r)
{
if(r != NULL)
{
destroy(r->leftChild);
destroy (r->rightChild);
cout << "删除值为" << r->data << "的节点" << endl;
delete r;
}
}
template <typename T>
BinTreeNode<T>* BinaryTree<T>::create(){
BinTreeNode<T>* current;
T val;
//cout << "按照中序，输入字符串。‘-’表示NULL：" << endl;
cin >> val;//输入键值
cout << "读入" << val << endl;
if(val == '-')//标识当前子树为空，转向下一节点
{
cout << "空节点" << endl;
return NULL;
}
else{
current = new BinTreeNode<T>;
current->data = val;
cout << "创建一个非空节点，值是" << val << endl;
current->leftChild = create();
current->rightChild = create();
}
return current;
}
template <class Type>
void BinaryTree<Type>::PreOrder(BinTreeNode<Type> *current)
{
if(current != NULL)
{
cout << current->data;
PreOrder (current->leftChild);
PreOrder (current->rightChild);
}
}
template <class Type>
void BinaryTree<Type>::InOrder(BinTreeNode<Type> *current)
{
if(current != NULL)
{
InOrder(current->leftChild);
cout << (current->data);
InOrder (current->rightChild);
}
}
template <class Type>
void BinaryTree<Type>::PostOrder(BinTreeNode<Type> *current)
{
if(current != NULL)
{
PostOrder(current->leftChild);
PostOrder (current->rightChild);
cout << (current->data);
}
}
#endif
- main函数文件
#include<iostream>
#include "BinaryTree.h"
using namespace std;
template <typename T>
BinTreeNode<T> * leafLink(BinTreeNode<T> *r);
void hw1_1();
int main()
{
hw1_1();
}
void hw1_1()
{
BinTreeNode<char> *head;
BinTreeNode<char> *temp;
cout << "按照中序，输入字符串。‘-’表示NULL：" << endl;//abd--ef--g--c--
BinaryTree<char> tree;
tree.root = tree.create();
cout << "............." <<endl;
head = leafLink(tree.root);
cout << "单链表：" << endl;
while(head->rightChild != NULL)
{
temp=head;
cout << head->data << "-->";
head = head->rightChild;
temp->rightChild = NULL;
}
cout << head->data <<endl;
tree.destroy(tree.root);
}
template <typename T>
BinTreeNode<T> * leafLink(BinTreeNode<T> *r)
{
static BinTreeNode<T> *s1,*s2;
//static int flag=0;
//BinTreeNode<T>* current;
if(r == NULL)
return NULL;
if(r->leftChild ==NULL && r->rightChild == NULL)
{
if(s2==NULL)
{ s2 = r;s1 = r; cout << "找到一个叶子节点,值是" << s1->data << endl;} //cout << "找到一个叶子节点,值是" << s1->data << endl;}
else
{ s2->rightChild = r;s2 = r;cout << "找到一个叶子节点,值是" << r->data << endl;} //cout << "找到一个叶子节点,值是" << r->data << endl;}
}
else
{
leafLink(r->leftChild);
leafLink(r->rightChild);
}
return s1;
}
- 运行测试
-
构建的二叉树为：
- 控制台输入及输出：
-
按照中序，输入字符串。‘-’表示NULL：
abd--ef--g--c--
读入a
创建一个非空节点，值是a
读入b
创建一个非空节点，值是b
读入d
创建一个非空节点，值是d
读入-
空节点
读入-
空节点
读入e
创建一个非空节点，值是e
读入f
创建一个非空节点，值是f
读入-
空节点
读入-
空节点
读入g
创建一个非空节点，值是g
读入-
空节点
读入-
空节点
读入c
创建一个非空节点，值是c
读入-
空节点
读入-
空节点
.............
找到一个叶子节点,值是d
找到一个叶子节点,值是f
找到一个叶子节点,值是g
找到一个叶子节点,值是c
单链表：
d-->f-->g-->c
删除值为d的节点
删除值为f的节点
删除值为g的节点
删除值为e的节点
删除值为b的节点
删除值为c的节点
删除值为a的节点
问题2
已知二叉树以二叉链表存储，编写算法完成：对于树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
- main函数文件
#include<iostream>
#include "BinaryTree.h"
using namespace std;
template <typename T>
BinTreeNode<T> * leafLink(BinTreeNode<T> *r);
void hw1_1();
void hw1_2();
int main()
{
hw1_2();
}
template <typename T>
void findAndDel(T &key, BinTreeNode<T> *r, BinaryTree<T> &tree);
void hw1_2()
{
cout << "按照中序，输入字符串。‘-’表示NULL：" << endl;
BinaryTree<char> tree;
tree.root = tree.create();
cout << "目前树的前序输出: ";
tree.PreOrder(tree.root);
cout << endl;
char key;
cout << "输入要删除的字符" << endl;
cin >> key;
findAndDel(key, tree.root, tree);
cout << "............."<< endl;
cout << "删除值为"<<key<<"节点后，树的前序输出: ";
tree.PreOrder(tree.root);
cout << endl;
tree.destroy(tree.root);
}
template <typename T>
void findAndDel(T &key, BinTreeNode<T> *r, BinaryTree<T> &tree)
{
if(r != NULL)
{
if(key == r->data)
{
cout << "找值为"<< r->data <<"的节点" << endl;
tree.destroy(r->leftChild);
tree.destroy(r->rightChild);
r->leftChild = NULL;
r->rightChild = NULL;
}
else
{
//cout << "找值为"<< r->data <<"的左子树" << endl;
findAndDel(key, r->leftChild, tree);
//cout << "找值为"<< r->data <<"的右子树" << endl;
findAndDel(key, r->rightChild, tree);
}
}
}
- 运行测试
按照中序，输入字符串。‘-’表示NULL：
abd--ef--g--ceh--k--i--
读入a
创建一个非空节点，值是a
读入b
创建一个非空节点，值是b
读入d
创建一个非空节点，值是d
读入-
空节点
读入-
空节点
读入e
创建一个非空节点，值是e
读入f
创建一个非空节点，值是f
读入-
空节点
读入-
空节点
读入g
创建一个非空节点，值是g
读入-
空节点
读入-
空节点
读入c
创建一个非空节点，值是c
读入e
创建一个非空节点，值是e
读入h
创建一个非空节点，值是h
读入-
空节点
读入-
空节点
读入k
创建一个非空节点，值是k
读入-
空节点
读入-
空节点
读入i
创建一个非空节点，值是i
读入-
空节点
读入-
空节点
目前树的前序输出: abdefgcehki
输入要删除的字符
e
找值为e的节点
删除值为f的节点
删除值为g的节点
找值为e的节点
删除值为h的节点
删除值为k的节点
.............
删除值为e节点后，树的前序输出: abdecei
删除值为d的节点
删除值为e的节点
删除值为b的节点
删除值为e的节点
删除值为i的节点
删除值为c的节点
删除值为a的节点
