A. 以二叉連表做存儲結構，試編寫按層次順序遍歷二叉樹的演算法
//二叉樹，按層次訪問
//引用如下地址的思想，設計一個演算法層序遍歷二叉樹（同一層從左到右訪問）。思想：用一個隊列保存被訪問的當前節點的左右孩子以實現層序遍歷。
//http://..com/link?url=a9ltidaf-SQzCIsa
typedef struct tagMyBTree
{
int data;
struct tagMyBTree *left,*right;
}MyBTree;
void visitNode(MyBTree *node)
{
if (node)
{
printf("%d ", node->data);
}
}
void visitBTree(queue<MyBTree*> q);
void createBTree(MyBTree **tree)
{
int data = 0;
static int initdata[15] = {1,2,4,0,0,5,0,0,3,6,0,0,7,0,0};//構造成滿二叉樹，利於查看結果
static int i = 0;
//scanf("%d", &data);
data = initdata[i++];
if (data == 0)
{
*tree = NULL;
}
else
{
*tree = (MyBTree*)malloc(sizeof(MyBTree));
if (*tree == NULL)
{
return;
}
(*tree)->data = data;
createBTree(&(*tree)->left);
createBTree(&(*tree)->right);
}
}
void visitBTreeTest()
{
queue<MyBTree*> q;
MyBTree *tree;
createBTree(&tree);
q.push(tree);
visitBTree(q);
}
void visitBTree(queue<MyBTree*> q)
{
if (!q.empty())
{
MyBTree *t = q.front();
q.pop();
visitNode(t);
if (t->left)
{
q.push(t->left);
}
if (t->right)
{
q.push(t->right);
}
visitBTree(q);
}
}
B. 已知二叉樹採用二叉鏈表存儲，編寫演算法實現層次遍歷二叉樹
這是我以前寫的程序，包含了前序中序後序 層次便利：若只需層序便利 只要把其餘的刪掉就行！
#include"stdafx.h"
#include<stdlib.h>
#include<math.h>
typedef structbitnode{
char data;
struct bitnode *lchild,*rchild;
}bitnode,*bitree;
typedef structqnode{
bitree data;
struct qnode *next;
}qnode;
typedef struct{
qnode * front;
qnode * rear;
}linkqueue;
intinitqueue(linkqueue &q)
{
q.front=q.rear=(qnode*)malloc(sizeof(qnode));
if(!q.front) exit(OVERFLOW);
q.front->next=NULL;
return 1;
}
intenqueue(linkqueue &q,bitree e)
{
qnode *p;
p=(qnode*)malloc(sizeof(qnode));
if(!p) exit(OVERFLOW);
p->data=e;p->next=NULL;
q.rear->next=p;
q.rear=p;
return 1;
}
intoutqueue(linkqueue & q,bitree &e)
{ qnode *p;
if(q.front==q.rear) return 0;
p=q.front->next;
e=p->data;
q.front->next=p->next;
if(q.rear==p)
q.rear=q.front;
return 1;
}
intcreatebitree(bitree &t)
{
char ch;
scanf("%c",&ch);
if(ch=='.')
t=NULL;
else{
if(!(t=(bitnode*)malloc(sizeof(bitnode))))
exit(OVERFLOW);
t->data=ch;
createbitree(t->lchild);
createbitree(t->rchild);
}
return 1;
}
int visit(char e)
{
printf("%c",e);
return 1;
}
intpreordertraverse(bitree t,int (*visit)(char e))
{
if(t){
if(visit(t->data))
if(preordertraverse(t->lchild,visit))
if(preordertraverse(t->rchild,visit))return 1;
return 0;
}else return 1;
}
intinordertraverse(bitree t,int (*visit)(char e))
{
if(t){
if(inordertraverse(t->lchild,visit))
if(visit(t->data))
if(inordertraverse(t->rchild,visit))return 1;
return 0;
}else return 1;
}
intpostordertraverse(bitree t,int (*visit)(char e))
{
if(t){
if(postordertraverse(t->lchild,visit))
if(postordertraverse(t->rchild,visit))
if(visit(t->data))
return 1;
return 0;
}else return 1;
}
voidlevelordertraverse(bitree t)
{
linkqueue q;
bitree e;
initqueue(q);
enqueue(q,t);
while(outqueue(q,e)){
if(e)
{
visit(e->data);
enqueue(q,e->lchild);
enqueue(q,e->rchild);
}
}
}
int main(int argc,char* argv[])
{
bitree t;
printf("輸入字元：");
createbitree(t);
printf("輸出先序遍歷：");
preordertraverse(t, visit);
printf("\n");
printf("輸出中序遍歷：");
inordertraverse(t,visit);
printf("\n");
printf("輸出後序遍歷：");
postordertraverse(t,visit);
printf("\n");
printf("輸出層序遍歷：");
levelordertraverse(t);
printf("\n");
return 0;
}
C. 設二叉樹以二叉鏈表存儲，試設計演算法，實現二叉樹的層序遍歷。
按層次遍歷演算法如下：
#include <iostream>
using namespace std;
typedef struct treenode { //樹結點結構
int data;
struct treenode *left;
struct treenode *right;
}TreeNode;
typedef struct stack{ //棧結點結構
TreeNode *node;
struct stack *next;
}STACK;
void Traversal(TreeNode *root)
{
STACK *head = NULL;
STACK *tail = NULL;
if (root != NULL) //根結點入棧
{
head = new STACK();
head->next = NULL;
head->node = root;
tail = head;
}
while(head != NULL)
{
STACK *temp;
if (head->node->left != NULL) //棧頂結點的左結點入棧
{
temp = new STACK();
temp->next = NULL;
temp->node = head->node->left;
tail->next = temp;
tail = temp;
}
if (head->node->right != NULL) //棧頂結點的右結點入棧
{
temp = new STACK();
temp->next = NULL;
temp->node = head->node->right;
tail->next = temp;
tail = temp;
}
cout<<head->node->data<<endl; //結點出棧
temp = head;
head = head->next;
delete(head);
}
}
D. 建立二叉樹的二叉鏈表表示，實現二叉樹的先序、中序、後序和按層次遍歷，統計並輸出結點個數。
以下是程序代碼，裡面還包括求樹的深度和葉子，已經運行通過了。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define Max 20 //結點的最大個數
typedef struct node{
char data;
struct node *lchild;
struct node *rchild;
}BTNode; //自定義二叉樹的結點類型
typedef BTNode *BTree; //定義二叉樹的指針
int NodeNum,leaf; //NodeNUm為結點數，leaf為葉子數
BTree CreatBTree(void)
{BTree T;
char ch;
if((ch=getchar())=='#')
return(NULL); //讀入#，返回空指針
else{
T=(BTNode *)malloc(sizeof(BTNode));//生成結點
T->data=ch;
T->lchild=CreatBTree();//構造左子樹
T->rchild=CreatBTree();//構造右子樹
return(T);
}
}
void Preorder(BTree T) //先序遍歷
{
if(T){
printf("%c",T->data);//訪問結點
Preorder(T->lchild);//先序遍歷左子樹
Preorder(T->rchild);//先序遍歷右子樹
}
}
void Inorder(BTree T)//中序遍歷
{
if(T)
{
Inorder(T->lchild);//中序遍歷左子樹
printf("%c",T->data);//訪問結點
Inorder(T->rchild);//中序遍歷右字樹
}
}
void Postorder(BTree T)//後序遍歷
{
if(T)
{
Postorder(T->lchild);
Postorder(T->rchild);
printf("%c",T->data);
}
}
int TreeDepth(BTree T)//後序遍歷求二叉樹的深度，結點數和葉子數
{
int hl,hr,max;
if(T)
{
hl=TreeDepth(T->lchild);//求左深度
hr=TreeDepth(T->rchild);//求右深度
max=hl>hr?hl:hr;//取左右深度的最大值
NodeNum=NodeNum+1;//求結點數
if(hl==0&&hr==0)
leaf=leaf+1;
return(max+1);
}
else return(0);
}
void Levelorder(BTree T)//層次遍歷二叉樹
{
int front=0,rear=1;
BTNode *cq[Max],*p;//定義結點的指針數組cq
cq[1]=T;//根入隊
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front];//出隊
printf("%c",p->data);//出隊，輸出結點的值
if(p->lchild!=NULL)
{rear=(rear+1)%NodeNum;
cq[rear]=p->rchild;//右子樹入隊
}
}
}
void main()
{
BTree root;
int i,depth;
printf("\n");
printf("創建二叉樹，請輸入完全二叉樹的先序序列，用#代表虛結點:");
root=CreatBTree();//返回根結點
do{
printf("********************SELECT********************\n");
printf("\t1:先序遍歷\n");
printf("\t2:中序遍歷\n");
printf("\t3:後序遍歷\n");
printf("\t4:深度、結點數、葉子數\n");
printf("\t5:層次遍歷\n");
printf("備註：選擇層次遍歷之前，需要先選擇4，求出該樹的結點數。");
printf("\t0:Exit\n");
printf("\t*********************************************\n");
scanf("%d",&i);//輸入菜單序號
switch(i)
{
case 1:printf("先序遍歷結果為:");
Preorder(root);
break;
case 2:printf("中序遍歷結果為:");
Inorder(root);
break;
case 3:printf("後序遍歷結果為:");
Postorder(root);
break;
case 4:depth=TreeDepth(root);
printf("深度=%d 結點數=%d",depth,NodeNum);
printf("葉子數=%d",leaf);
break;
case 5:printf("層次遍歷為:");
Levelorder(root);
break;
default:exit(1);
}
printf("\n");
}
while(i!=0);
}
E. 二叉樹以二叉鏈表方式存儲,以後序遍歷或層次遍歷的方式求各結點中最大元素的值
以下的函數以後序遍歷的方法求解
void findMax(BtNode *root, int &maxValue)
{
if(root == NULL)
{
return; // 若當前節點指針為空，則直接返回
}
findMax(root->leftChild, maxValue); // 先遍歷左子樹
findMax(root->rightChild, maxValue); // 再遍歷右子樹
if(maxValue < root->data)
{
maxValue = root->data; // 將當前節點的值與maxValue比較，如果大於maxValue，則將maxValue改為當前節點的值
}
}
F. 二叉樹的鏈式存儲結構的數據結構定義、創建、先序和後序遍歷，並將結果序列輸出。
1、建立一個單鏈表，並從屏幕顯示單鏈表元素列表。
2、從鍵盤輸入一個數，查找在以上創建的單鏈表中是否存在該數;如果存在，顯示它的位置;如果不存在，給出相應提示。
3、在上述的單鏈表中的指定位置插入指定的元素
4、刪除上述單鏈表中指定位置的元素。
源程序：頭文件
#include<iostream.h>
#include<malloc.h>
typedef char ElemType;
typedef int Status;
#define OK 1
#define ERROR 0
typedef struct LNode{
ElemType data;
LNode *next;
}LNode,*LinkList;
void about(){ //版本信息
cout<<"單鏈表的操作"
}
void showmenu(){ //功能列表
cout<<endl <<" **********功能**********"<<endl
<<" * 1.輸出單鏈表的全部數據*"<<endl
<<" * 2.查找鏈表元素 *"<<endl
<<" * 3.鏈表插入元素 *"<<endl
<<" * 4.鏈表刪除元素 *"<<endl
<<" * 5.結束 *"<<endl
<<" ************************"<<endl
<<"請輸入所需功能: ";
}
//*******查看輸入的全部數據*********
void PrintList(LinkList L){
LinkList p;
cout<<endl<<"你輸入的數據為: ";
p=L->next; //從頭結點開始掃描
while(p){ //順指針向後掃描，直到p->next為NULL或i=j為止
cout<<p->data;
p=p->next; }
cout<<endl; }
//逆序輸入 n 個數據元素，建立帶頭結點的單鏈表
void CreateList_L(LinkList &L, int n) {
int i;
LinkList p;
L = new LNode;
L->next = NULL; // 先建立一個帶頭結點的單鏈表
cout<<"逆序輸入 n 個數據元素，建立帶頭結點的單鏈表"<<endl;
for (i = n; i > 0; --i) {
p = new LNode;
cin>>p->data; // 輸入元素值
p->next = L->next; L->next = p; // 插入
}
}
// L是帶頭結點的鏈表的頭指針，以 e 返回第 i 個元素
Status GetElem_L(LinkList L, int i, ElemType &e) {
int j;
LinkList p;
p = L->next; j = 1; // p指向第一個結點，j為計數器
while (p && j<i) { p = p->next; ++j; } // 順指針向後查找，直到 p 指向第 i 個元素或 p 為空
if ( !p || j>i )
return ERROR; // 第 i 個元素不存在
e = p->data; // 取得第 i 個元素
return OK;
}
// 本演算法在鏈表中第i 個結點之前插入新的元素 e
Status ListInsert_L(LinkList L, int i, ElemType e) {
int j;
LinkList p,s;
p = L; j = 0;
while (p && j < i-1)
{ p = p->next; ++j; } // 尋找第 i-1 個結點
if (!p || j > i-1)
return ERROR; // i 大於表長或者小於1
s = new LNode; // 生成新結點
if ( s == NULL) return ERROR;
s->data = e;
s->next = p->next; p->next = s; // 插入
return OK;
}
Status ListDelete_L(LinkList L, int i, ElemType &e)
{LinkList p,q;
int j;
p = L; j = 0;
while (p->next && j < i-1) { p = p->next; ++j; }
// 尋找第 i 個結點，並令 p 指向其前趨
if (!(p->next) || j > i-1)
return ERROR; // 刪除位置不合理
q = p->next; p->next = q->next; // 刪除並釋放結點
e = q->data; free(q);
return OK;
}
#include"LinkList.h"
void main()
{LinkList L;
int n,choice,i;
ElemType e;
about();
cout<<"請輸入鏈表中元素的個數";
cin>>n;
CreateList_L(L, n);
showmenu(); //功能列表
cin>>choice;
while(choice!=5)
{ //輸入時候退出程序
switch(choice){
case 1:PrintList(L);break; //1.查看輸入的全部數據
case 2:{
cout<<"輸入你要查找的元素的位置： ";
cin>>i;GetElem_L(L, i, e);
cout<<"第"<<i<<"個元素的值是"<<e<<endl;
break;} //2.查找鏈表元素
case 3:
{cout<<"請輸入你要插入元素的位置i： ";
cin>>i;
cout<<endl<<"請輸入你要插入元素的值： ";
cin>>e;
ListInsert_L(L, i,e);
break;} //3.鏈表插入元素
case 4:
{cout<<"請輸入你要刪除元素的位置";
cin>>i;
ListDelete_L(L, i, e) ;
break;} //4.鏈表刪除元素
default:cout<<"輸入錯誤,請輸入-5,輸入重顯示功能表^_^ "<<endl;
}
cout<<endl<<"輸入功能序號:";
cin>>choice;
}
}
G. 建立一棵二叉樹，輸出該二叉樹的前序遍歷、中序遍歷和後序遍歷以及層序遍歷，並實現對結點全職的查找。
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;
}