首先确定点到点的向量范围

然后做枝叶的随机，将最终节点设置为LEAF

我只给出结构，剩下的LZ自己来吧

function Node(){

thisnodeCount=0;子节点数量

thisisLeaf=false;

thisLChild=[];左枝叶

thisRChild=[];右枝叶

}

结构请按照二叉树的生成来

以下程序已在win-tc和tc20下运行通过，已加详细注释(本人所写)。

/ 数据安全实用程序，加密解密简单程序 /

#include<stdioh>

#include<stdlibh>

#include<conioh>

int flag;

char encrypt(char ch,int key)/加密函数，把字符循环移位/

{

if(ch>='a' && ch<='z') / 如果是小写字母 /

{

ch=(ch-'a'+key%26)%26+'a'; / 字母向后移key%26个位置，超过字母z则再从a开始向后移动 /

}

else if(ch>='A' && ch<='Z') / 如果是大写字母 /

{

ch=(ch-'A'+key%26)%26+'A'; / 字母向后移key%26个位置，超过字母Z则再从A开始向后移动 /

}

return ch;

}

char decrypt(char ch,int key)/解密函数，把字符循环移位/

{

if(ch>='a' && ch<='z') / 如果是小写字母 /

{

ch=(ch-'a'+26-key%26)%26+'a'; / 字母向后移26-key%26个位置，超过字母z则再从a开始向后移动 /

}

else if(ch>='A' && ch<='Z') / 如果是大写字母 /

{

ch=(ch-'A'+26-key%26)%26+'A'; / 字母向后移26-key%26个位置，超过字母Z则再从A开始向后移动 /

}

return ch;

}

void menu()/菜单，1加密，2解密，3显示文本文件内容/

{

clrscr();

printf("\n=======================================================");

printf("\n1Encrypt the text file"); / 加密文件 /

printf("\n2Decrypt the text file"); / 解密文件 /

printf("\n3Display text file contents");/ 显示加密或解密或未加密或解密的文件 /

printf("\n4Quit\n");

printf("=========================================================\n");

printf("Please select a item:"); / 选择一个菜单 /

}

void logo()/显示程序信息/

{

printf("\nwelcome to encrypt program \n ");

return;

}

void encrypt_decrypt_File(char infile,int key, char outfile) / 加密或解密函数 /

{

FILE in,out;

char ch;

clrscr(); / 清屏 /

if((in=fopen(infile,"r"))==NULL) / 打开欲加密或解密的文件/

{

printf("Can not open the infile!\n"); / 如果打开文件失败或文件不存在打印打开失败信息 /

printf("Press any key to exit!\n");

getch(); / 并等待任一按键然后退出程序 /

exit(0);

}

if((out=fopen(outfile,"w"))==NULL) / 打开文件保存加密或解密后的内容/

{

printf("Can not open the outfile!\n"); / 如果打开文件失败或文件不存在打印打开失败信息 /

printf("Press any key to exit!\n"); / 并等待任一按键然后退出程序 /

fclose(in); / 关闭输入文件 /

getch(); / 等待按键，按任一键退出程序 /

exit(0);

}

ch=fgetc(in); /从文本文件中读入字符/

while(ch!=EOF)/加密或解密/

{

/如果是英文字符，则进行加密或解密，否则，不进行加密或解密处理/

if((ch>='a' && ch<='z' ) || (ch>='A' && ch<='Z'))

{ if(flag==1)

fputc(encrypt(ch,key),out);

if(flag==2)

fputc(decrypt(ch,key),out);

}

else

fputc(ch,out);

ch=fgetc(in);

}

/关闭输入及输出文件/

fclose(in);

fclose(out);

}

void displayFile(char infile) /将文本文件的内容显示在屏幕上/

{

FILE fp;

char string[81];

if((fp=fopen(infile,"r"))==NULL) / 以只读方式打开文本文件 /

{

printf("cann't open file");exit(0); / 如果文件不存在或打开失败打印无法打开信息并退出程序 /

}

while(fgets(string,81,fp)!=NULL)

fputs(string,stdout); /把所取字符串送到屏幕显示/

fclose(fp); / 关闭文件 /

}

int main()

{

int i,n;

char ch0,ch1;

char infile[40],outfile[40];

textbackground(LIGHTGRAY); /设置背景颜色为浅灰色/

textcolor(BLACK); /设置文字颜色为黑色/

clrscr();/清除屏幕显示/

logo(); /显示程序信息/

sleep(2); / 延时2秒 /

menu(); /显示屏幕菜单/

ch0=getche();/等待用户从键盘输入，并把输入显示在屏幕上/

while(ch0!='4')

{

clrscr();

if(ch0=='1') /选择加密功能/

{

flag=1;

printf("\nPlease input the infile to be encrypted:"); / 输入要加密的文件名 /

scanf("%s",infile); / 该文件要和本程序放在同一个目录下 /

printf("Please input the encrypt key:");

scanf("%d",&n);/输入加密密码/

printf("Please input the outfile:"); /输入存放加密内容的文件名/

scanf("%s",outfile); / 该文件可以自动创建 /

encrypt_decrypt_File(infile,n,outfile);

printf("\nEncrypt is over!\n");/ 加密成功 /

sleep(1); / 延时1秒 /

}

else if(ch0=='2') /选择解密功能/

{

flag=2;

printf("\nPlease input the infile to be decrypted:"); / 输入要解密的文件名 /

scanf("%s",infile); / 该文件要和本程序放在同一个目录下 /

printf("Please input the decrypt key:");

scanf("%d",&n);/输入解密密码，加密和解密密码应相同/

printf("Please input the outfile:"); /输入存放解密内容的文件名/

scanf("%s",outfile); / 该文件可以自动创建 /

encrypt_decrypt_File(infile,n,outfile);

printf("\nDecrypt is over!\n");

sleep(1); / 延时1秒 /

}

else if(ch0=='3') /选择显示文本文件功能/

{

printf("\nPlease input the infile to be displayed:"); / 输入要显示的文件名 /

scanf("%s",infile);

displayFile(infile);/ 显示文件 /

getch();

}

else

{ /不合法输入/

printf("\nplease input a valid number(1-4)\n");

sleep(1); / 延时1秒 /

}

menu();/显示程序菜单/

ch0=getche(); /等待用户下一次的功能选择/

}

system("cls");/清除屏幕/

logo(); /显示程序信息/

printf("\nGood Bye!\n");

sleep(2);/ 延时2秒 /

system("pause"); / 暂停，按任一键退出程序 /

return 0;

}

实验一 二叉排序树与平衡二叉树的实现

一：题目内容

1问题描述

分别采用二叉链表和顺序表作存储结构，实现对二叉排序树或平衡

二叉树的操作。

2基本要求

(1)用二叉链表作存储结构实现二叉排序树。

1)构建二叉排序树：以回车符(„\n‟)为输入结束标志，输入数列L，生成一棵二叉排序树T；

2)对二叉排序树T作中序遍历，输出结果；

3)计算二叉排序树T查找成功的平均查找长度，输出结果；

4)删除元素：输入元素x，查找二叉排序树T，若存在含x的结点，则删除该结点，并作中序遍历(执行操作2)；否则，输出信息“无x”；

5）插入元素：输入元素x，查找二叉排序树T，若存在含x的结点，则输出信息“x已存在”，否则插入该元素，并作中序遍历(执行操作2)；

2)用顺序表(一维数组)作存储结构----静态链表

1)构建二叉排序树：以回车符(„\n‟)为输入结束标志，输入数列L，生成一棵二叉排序树T；

2)对二叉排序树T作中序遍历，输出结果；

3)计算二叉排序树T查找成功的平均查找长度，输出结果；

4)删除元素：输入元素x，查找二叉排序树T，若存在含x的结点，则删除该结点，并作中序遍历(执行操作2)；否则，输出信息“无x”；

5）插入元素：输入元素x，查找二叉排序树T，若存在含x的结点，则输出信息“x已存在”，否则插入该元素，并作中序遍历(执行操作2)；

(3)用二叉链表作存储结构实平衡的二叉排序树。

1)用数列L，生成平衡的二叉排序树BT：当插入新元素之后，发现

当前的二叉排序树BT不是平衡的二叉排序树，则立即将它转换成新的平

衡的二叉排序树BT；

2)计算平衡的二叉排序树BT的平均查找长度，输出结果。

该功能可选做。

二：问题分析：

这是一个有关二叉树的基本操作的问题。涉及到二叉树的生成，遍历，查找，以及节点的插入和删除操作。

三：程序设计

#include "stdioh"

#include "iostream"

using namespace std;

int i=0;

int n=0;

typedef struct TreeNode

{

int key; struct TreeNode left; struct TreeNode right;

}treeNode;

class BiSortTree

{

public:

BiSortTree(void);

~BiSortTree();

void desplayTree(void);

void insertTree(int key);

void deleteTree(int key);

treeNode searchTree(int key);

private:

treeNode buildTree(treeNode head,int number); treeNode search(treeNode head ,int key); treeNode

head,treeNode p); BiSortTree::searchParent(treeNode

treeNode BiSortTree::searchMinRight(treeNode head); void showTree(treeNode head); void destroyTree(treeNode head); treeNode Head;

};

BiSortTree::BiSortTree()

{

cout

有数(以/n作为结束标志!): "

Head=NULL; int number; cin>>number; while(number!=-1) { Head=buildTree(Head,number);

n++;

cin>>number;

}

}

treeNode BiSortTree::buildTree(treeNode

//head 为父结点

{

treeNode p;

p=new treeNode;

p->key=number;

p->left=p->right=NULL;

if(head==NULL)

{

i++;

return p;

}

else

{

if(p->keykey)

{ number) head,int

}

} i++; else{ } return head; head->right=buildTree(head->right,number); i++; }

void BiSortTree::insertTree(int key)

{

}

treeNode BiSortTree::searchTree(int key)

{

return search(Head,key); Head=buildTree(Head,key);

treeNode BiSortTree::search(treeNode head ,int key) {

}

void BiSortTree::deleteTree(int key)

{

treeNode p; if(head==NULL) return NULL; if(head->key==key) return head; else { } if(keykey ) return search(head->left,key); else return search(head->right,key);

p=NULL;

p=search(Head,key);

if(p==NULL)

{ } cout

else

{ treeNode parent;

parent=searchParent(Head,p);

if(p->left==NULL&&p->right==NULL) { } else { if(p->right==NULL) if(parent->left==p) { } else { } parent->right=NULL; parent->left=NULL;

} else { treeNode rightMinSon, secondParent; if(parent->left==p) { } else { } parent->right=p->left; parent->left=p->left ;

rightMinSon=searchMinRight(p->right);

secondParent=searchParent(p->right ,rightMinSon);

secondParent->left=rightMinSon->right;

if(p->right==rightMinSon)

{ } p->right=rightMinSon->right ;

}

} } }

treeNode BiSortTree::searchParent(treeNode head,treeNode p)

{

if(head->left==p||head->right==p||head==p||head==NULL) return head;

else

}

treeNode BiSortTree::searchMinRight(treeNode head) { { } if(p->keykey) return searchParent(head->left,p); else return searchParent(head->right,p);

}

{ } else { } return searchMinRight(head->left); return head;

void BiSortTree::desplayTree(void) {

cout

cout

}

void BiSortTree::showTree(treeNode Head) {

if(Head!=NULL) { showTree(Head->left );

}

} coutkeyright) ;

BiSortTree::~BiSortTree()

{

}

void BiSortTree::destroyTree(treeNode head) {

}

if(head!=NULL) { } destroyTree(head->left ); destroyTree(head->right ); delete head; cout

int main()

{

BiSortTree tree;

int number,set;

treedesplayTree();

cout

cout

if(set==2) { cout>set) { cin>>number;

treedeleteTree(number);

cout

cin>>number; treeinsertTree(number); cout

四：结果

源文件：

#include <iostreamh>

#include <stdlibh>

#include "BinaryTreeh"

template <class T>

BinTreeNode<T> BinaryTree<T>::Parent (BinTreeNode <T> subTree, BinTreeNode <T> t) {

//私有函数: 从结点 subTree 开始, 搜索结点 t 的双

//亲, 若找到则返回双亲结点地址, 否则返回NULL

if (subTree == NULL) return NULL;

if (subTree->leftChild == t || subTree->rightChild == t )

return subTree; //找到, 返回父结点地址

BinTreeNode <T> p;

if ((p = Parent (subTree->leftChild, t)) != NULL)

return p; //递归在左子树中搜索

else return Parent (subTree->rightChild, t);

//递归在左子树中搜索

};

template<class T>

void BinaryTree<T>::Destroy (BinTreeNode<T> subTree) {

//私有函数: 删除根为subTree的子树

if (subTree != NULL) {

Destroy (subTree->leftChild); //删除左子树

Destroy (subTree->rightChild); //删除右子树

delete subTree; //删除根结点

}

};

template <class T>

void BinaryTree<T>::InOrder (BinTreeNode<T> subTree) {

if (subTree != NULL) {

InOrder (subTree->leftChild); //遍历左子树

cout<<subTree->data<<"|"; //访问根结点

InOrder (subTree->rightChild); //遍历右子树

}

};

template <class T>

void BinaryTree<T>::PreOrder (BinTreeNode<T> subTree) {

if (subTree != NULL) {

cout<<subTree->data<<"|"; //访问根结点

PreOrder (subTree->leftChild); //遍历左子树

PreOrder (subTree->rightChild); //遍历右子树

}

};

template <class T>

void BinaryTree<T>::PostOrder (BinTreeNode<T> subTree) {

if (subTree != NULL ) {

PostOrder (subTree->leftChild); //遍历左子树

PostOrder (subTree->rightChild); //遍历右子树

cout<<subTree->data<<"|"; //访问根结点

}

};

template <class T>

int BinaryTree<T>::Size (BinTreeNode<T> subTree){

//私有函数：利用二叉树后序遍历算法计算二叉

//树的结点个数

if (subTree == NULL) return 0; //空树

else return 1+Size (subTree->leftChild) + Size (subTree->rightChild);

};

template <class T>

int BinaryTree<T>::Height ( BinTreeNode<T> subTree){

//私有函数：利用二叉树后序遍历算法计算二叉

//树的高度或深度

if (subTree == NULL) return 0; //空树高度为0

else {

int i = Height (subTree->leftChild);

int j = Height (subTree->rightChild);

return (i < j) j+1 : i+1;

}

};

template<class T>

void BinaryTree<T>::CreateBinTree (T RefValue, BinTreeNode<T> & subTree) {

//前序序列从键盘输入建立二叉树。

T item;

cin >> item; //读入根结点的值

if (item != RefValue) {

subTree = new BinTreeNode<T>(item); //建立根结点

if (subTree == NULL)

{cerr << "存储分配错!" << endl; exit (1);}

CreateBinTree (RefValue, subTree->leftChild); //递归建立左子树

CreateBinTree (RefValue, subTree->rightChild); //递归建立右子树

}

else subTree = NULL; //封闭指向空子树的指针

};

头文件：

#pragma once

template <class T>

struct BinTreeNode { //二叉树结点类定义

T data; //数据域

BinTreeNode<T> leftChild, rightChild; //左子女、右子女链域

BinTreeNode () //构造函数

{ leftChild = NULL; rightChild = NULL; }

BinTreeNode (T x, BinTreeNode<T> l = NULL, BinTreeNode<T> r = NULL)

{ data = x; leftChild = l; rightChild = r; }

};

template <class T>

class BinaryTree { //二叉树类定义

protected:

BinTreeNode<T> root; //二叉树的根指针

T RefValue; //数据输入停止标志

void Destroy (BinTreeNode<T> subTree); //删除

int Height (BinTreeNode<T> subTree); //返回树高度

int Size (BinTreeNode<T> subTree); //返回结点数

BinTreeNode<T> Parent (BinTreeNode<T> subTree, BinTreeNode<T> t); //返回父结点

void PreOrder (BinTreeNode<T> subTree); //前序遍历

void InOrder (BinTreeNode<T> subTree); //中序遍历

void PostOrder (BinTreeNode<T> subTree); //后序遍历

void CreateBinTree (T RefValue, BinTreeNode<T> & subTree); //从键盘读入建树

public:

BinaryTree () : root (NULL) { } //构造函数

BinaryTree (T value) : RefValue(value), root(NULL) { } //构造函数

~BinaryTree () { Destroy(root); } //析构函数

bool IsEmpty () { return root == NULL;} //判二叉树空否

int Height () { return Height(root); } //求树高度

int Size () { return Size(root); } //求结点数

BinTreeNode<T> Parent (BinTreeNode <T> t)

{ return (root == NULL || root == t) NULL : Parent (root, t); } //返回双亲结点

BinTreeNode<T> LeftChild (BinTreeNode<T> t)

{ return (t != NULL)t->leftChild : NULL; } //返回左子女

BinTreeNode<T> RightChild (BinTreeNode<T> t)

{ return (t != NULL)t->rightChild : NULL; } //返回右子女

BinTreeNode<T> GetRoot () const { return root; } //取根

void PreOrder ()

{ PreOrder (root); } //前序遍历

void InOrder ()

{ InOrder (root); } //中序遍历

void PostOrder ()

{ PostOrder (root); } //后序遍历

void CreateBinTree ()

{ CreateBinTree (RefValue, root);} //从键盘读入建树

};

#include<iostreamh>

#include <stdioh>

#include <stdlibh>

typedef struct node {

char data;

struct node lchild,rchild;//

}BiTNode,BiTree;

void CreatBiTree(BiTree &T)

{

char ch;

ch=getchar();

if (ch == ' ')

T = 0;

else {

T=(BiTNode)malloc(sizeof(BiTNode));

T->data=ch;//生成根节点

CreatBiTree(T->lchild);//构造左子树

CreatBiTree(T->rchild);//构造右子树

}

}

void preorder(BiTree T)//前序遍历

{

if (T!=NULL){

printf ("%c",T->data);

preorder(T->lchild);

preorder(T->rchild);

}

}

void inorder(BiTree T)//中序遍历

{

if (T!=NULL){

inorder(T->lchild);

printf ("%c",T->data);

inorder(T->rchild);

}

}

void postorder(BiTree T)//后序遍历

{

if (T!=NULL){

postorder(T->lchild);

postorder(T->rchild);

printf ("%c",T->data);

}

}

void main ()

{

cout<<"请输入要创建的二叉树包括空格:"<<endl ;

BiTree T;

CreatBiTree(T);//创建二叉树

cout<<"前序遍历的结果为:"<<endl;

preorder(T);

cout<<endl;

cout<<"中序遍历的结果为:"<<endl;

inorder(T);

cout<<endl;

cout<<"后序遍历的结果为:"<<endl;

postorder(T);

}

对于一般的家谱树(一般的多叉树)来说，我们可以很清楚的看出层次关系，树的层数表示代数（一共多少代人），树的最后一层表示最后一代人，由于多叉链表法表示的不方便，因此被迫无奈采用孩子兄弟表示法(二叉链表法)

假设我的家谱是这样的：

转换成孩子兄弟表示法后是这样的：

我们要做的是：这时我们要找有多少代人，以及最后以一代人出来。

 如果根据第一个图来说找代数就是树的高度，最后一代人就是树的最后一层，二叉链表法中却不如第一个图来的直观，但是只要把握二叉链表法的本质还是很清晰的，根据孩子兄弟表示法的特性，（看二叉链表法的图）结点3的左子树保存的是其孩子，结点3的右子树保存的是其堂兄弟(对照第一个图来看)。假设我们每一个节点都有一个变量用来存储它是第几代的，那么从结点1开始，我们要找结点10是第几代的话，应该这么做：结点1是第一代，然后经过结点5是第二袋，然后看到结点10是第三代。因为第i个结点的左子树是他的孩子，既然是孩子，代数必须+1，而右子树是和第i结点同辈份的（堂兄弟），因此不能加1。本质来说就是往左走代数+1，向右走代数不变。这就是这题目的思路，通过这个方法你就可以知道有多少代人了，且每个节点都有保存了代数信息（用变量存起来了），再次遍历树把最后一代的结点输出即可。清晰了吗？清晰了我就开始写程序。