1. 利用C++,设计程序,定义二叉链表,存储二叉排序树,声明并定义相应的函数,实现链式二叉排序树的下列操作
2 代码： 1 ）二叉排序树： #include"BSTreeNode.h" #include"seqstack.h" #define Max(x1,x2) (x1>x2?x1:x2) //返回两个数中的最大者 #include using namespace std; template class BSTree { private: //void destory(BSTreeNode *p);//删除以p为根的二叉树 void InOrder(BSTreeNode *r);//私有函数：此算法按照中序次序遍历二叉树 void PostOrder(BSTreeNode *r);//私有函数：此算法按照后序次序遍历二叉树 int Depth(const BSTreeNode *r); //私有函数：此算法计算二叉树的深度 int LeafSize(const BSTreeNode *r); //私有函数：此算法计算二叉树的叶子结点个数 //void CreatPreThreed(BSTreeNode *&r); BSTreeNode*Find(const Type &k,BSTreeNode*p)const; void Insert(const Type &x,BSTreeNode*&p); void Delete(const Type &k,BSTreeNode*&p); BSTreeNode*& Min(BSTreeNode*&p); BSTreeNode *root; public: BSTree():root(NULL){} BSTreeNode *Root(){return root;} int Depth(); //计算二叉树的深度 int LeafSize(); //计算二叉树的叶子结点个数 void PreOrder();//用栈先序遍历二叉树 void CreatPreThreed(){CreatPreThreed(root);} void InOrder(); void PostOrder(); BSTreeNode *Find(const Type &k)const{return Find(k,root);} //BSTreeNode*& Min(){Min(BSTreeNode*&p);}; //Type Max(); void Insret(const Type &x){Insert(x,root);} void Delete(const Type &k){Delete(k,root);} void CreatBSTree(); }; template void BSTree::InOrder(BSTreeNode *r) { if(r!=NULL) { InOrder(r->GetLeftChild()); cout<GetData()<GetRightChild()); } } template void BSTree::PostOrder(BSTreeNode*r) { if(r!=NULL) { PostOrder(r->GetLeftChild()); PostOrder(r->GetRightChild()); cout<GetData()</递归结束条件：空树叶子结点个数为 else if(t->leftChild == NULL && t->rightChild == NULL) return 1; else return LeafSize(t->leftChild)+LeafSize(t->rightChild); } template int BSTree::Depth() { return Depth(root); } template int BSTree::Depth(const BSTreeNode* t) { if(t==NULL) return 0; //递归结束条件：空树深度为 return 1+Max(Depth(t->leftChild),Depth(t->rightChild)); } template void BSTree::PreOrder() { seqstack *> s(50); if(root==NULL) cout<<"二叉树为空！"<data<GetLeftChild(); do { if(p!=NULL) { cout<GetData()<GetLeftChild(); } else if(s.empty()!=1) { p=s.pop(); p=p->GetRightChild(); } }while(s.empty()!=1||p!=NULL); } /*template void BSTree::CreatPreThreed(BSTreeNode *&r) { Type ch; cin>>ch; if(ch=='#')return; r=new BinTreeNode(ch,NULL,NULL); CreatPreThreed(r->leftChild); CreatPreThreed(r->rightChild); }*/ template void BSTree::InOrder() { InOrder(root); } template void BSTree::PostOrder() { PostOrder(root); }/* template BSTreeNode* BSTree::Find(const Type &k,BSTree*p)const { if(p==NULL) return NULL; else if（kdata） return Find(k,p->leftChild); else if(k>p->data) return Find(k,p->rightChild); else return p; }*/ template BSTreeNode *BSTree::Find(const Type &k,BSTreeNode*p)const//在p为根的二叉排序树上进行查找的迭代算法 { BSTreeNode*temp=p; if(p!=NULL) { while(temp!=NULL) { if(temp->data==k) return temp;//查找成功 if(temp->datarightChild;//查找右子树 else temp=temp->leftChild;//查找左子树 } } return temp;//查找失败 } template void BSTree::Insert(const Type &x,BSTreeNode*&p)//在p为根的二叉排序树上插入结点的递归算法 { if(p==NULL)//空二叉树 p=new BSTreeNode(x);//创建数据元素x的结点 else if(xdata) Insert(x,p->leftChild);//在左子树插入 else if(x>p->data) Insert(x,p->rightChild);//在右子树插入 else //结点x存在 { cout<<"已经存在该节点插入失败"leftChild);//若p的关键字大于k，则在p的左子树删除 else if(k>p->data) //delete(k,p->rightChild); Delete(k,p->rightChild);//若p的关键字小于k，则在p的右子树删除 else if(p->leftChild!=NULL&&p->rightChild!=NULL) { /* temp=Min(p->rightChild); p->data=temp->data; delete(p->data,temp); */ BSTreeNode *&temp1=Min(p->rightChild); p->data=temp1->data; Delete(p->data,temp1); //注意这里和你原来的比较是Delete而非delete } else { temp=p; if(p->leftChild==NULL) p=p->rightChild; else if(p->rightChild==NULL) p=p->leftChild; delete temp; } } templatevoid BSTree::CreatBSTree() { int i(0); cout<<'\n'; Type ch; while(ch!=-1) { cout<<"第">ch; if(ch!=-1) { Insert(ch,root); i++; } else break; } } //template templateBSTreeNode*& BSTree::Min(BSTreeNode *&p) { /* BSTreeNode*&q; while(p!=NULL) { q=p; p=p->GetLeftChild(); } */ while (p->leftChild!=NULL) p=p->leftChild; return p; }
2. 利用二叉链表存储树，则根结点的右指针是 为什么答案不是右孩子是空
因为存的是一般树，二叉链表储存要先化成二叉树，根节点没有兄弟，右指针为空
3. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。
答案：C。用二叉链表存储结构也就是左孩子右兄弟的存储结构。
后序遍历比较合理。正常的逻辑应该就是：做好当前结点子树内部的交换，然后交换当前结点的左右子树。刚好符合后序遍历的算法逻辑。
1、交换好左子树
2、交换好右子树
3、交换左子树与右子树
其他算法如先序和按层次其逻辑都差不多，即访问当前结点时交换其左右子树。从逻辑上来看稍显别扭一点点。因此说最合适应该是后序遍历，但是从实现上来说先序和按层次都是可以的。
1、交换左子树与右子树
2、遍历左子树
3、遍历右子树
按层次遍历
1、根结点入队列
2、出队列，交换其左右子树，将子树的根入队列
3、重复2直到队列为空
中序遍历相对较难实现一些。
(3)利用2叉链表存储树扩展阅读：
树的遍历是树的一种重要的运算。树的3种最重要的遍历方式分别称为前序遍历、中序遍历和后序遍历。
以这3种方式遍历一棵树时，若按访问结点的先后次序将结点排列起来，就可分别得到树中所有结点的前序列表、中序列表和后序列表。相应的结点次序分别称为结点的前序、中序和后序。
4. 为什么用二叉链表存储树，则根节点的右指针是空 为什么不是指向右孩子
将一棵树转化为二叉树，此时二叉树的根节点的右指针为空，
因为这个指针是用来指向另一棵树的根节点的。具体情况你
也可以参看森林转化为二叉树的方法。
5. 利用二叉链表存储二叉树，则根节点的右指针为空。 为什么不是指向右孩子
题目写错了吧，应该是用二叉链表存储树（转换的二叉树），则根结点的右指针为空
6. 二叉排序树。用二叉链表作存储结构。（8
这是我前几天写的，看了下应该可以满足要求，由于测试还不够，不知道有没有bug。
第一点你自己改改，2、3都达到了，至于第四，不用说肯定是平衡了的二叉树相对查找效率要高一些，平衡，随机插入，打乱插入等操作都是为了防止最差情况的线性树的出现。测试的话用rand()生成随机数外加time.h里的几个函数，配合使用下就出来了。
#include<stdio.h>
#include<stdlib.h>
//binarysearchtree
typedefstructBST
{
intdata;
structBST*lhs;
structBST*rhs;
}BST;
//插入一个节点
BST*BSTInsertNode(BST*root,intelem)
{
BST*node;
node=(BST*)malloc(sizeof(BST));
node->data=elem;
node->lhs=node->rhs=0;
if(!root)
returnnode;
while(1)
{
if(node->data<root->data)
{
if(root->lhs)
root=root->lhs;
else
{
root->lhs=node;
returnroot->lhs;
}
}
else
{
if(root->rhs)
root=root->rhs;
else
{
root->rhs=node;
returnroot->rhs;
}
}
}
}
//获得父节点
BST*BSTGetParentNode(BST*root,BST*node)
{
if(root==node)
return0;
if(root->lhs&&node->data<root->lhs->data)
returnBSTGetParentNode(root->lhs,node);
elseif(root->rhs&&node->data>root->rhs->data)
returnBSTGetParentNode(root->rhs,node);
else
returnroot;
}
//删除一个节点
BST*BSTDeleteNode(BST*root,BST*node)
{
BST*parent;
BST**whichNode;
BST*temp;
if(root!=node)
{
parent=BSTGetParentNode(root,node);
whichNode=parent->lhs==node?&parent->lhs:&parent->rhs;
}
else
whichNode=&root;
if(!node->lhs&&!node->rhs)
*whichNode=0;
elseif(!((node->lhs?1:0)^(node->rhs?1:0)))
*whichNode=node->lhs?node->lhs:node->rhs;
else
{
temp=node->rhs;
while(temp->lhs)
temp=temp->lhs;
temp->lhs=node->lhs;
*whichNode=node->rhs;
}
free(node);
return*whichNode;
}
//删除树
voidBSTDeleteTree(BST*node)
{
if(node)
{
BSTDeleteTree(node->lhs);
BSTDeleteTree(node->rhs);
free(node);
}
}
//建造树，从数组构造
BST*BSTBuildTree(int*beg,int*end)
{
BST*root;
if(beg>=end)
return0;
root=(BST*)malloc(sizeof(BST));
root->data=*beg++;
root->lhs=root->rhs=0;
while(beg!=end)
BSTInsertNode(root,*beg++);
returnroot;
}
//查找节点
BST*BSTSearchNode(BST*root,intelem)
{
if(root)
{
if(elem<root->data)
returnBSTSearchNode(root->lhs,elem);
elseif(elem>root->data)
returnBSTSearchNode(root->rhs,elem);
else
returnroot;
}
else
return0;
}
//获得最小值
BST*BSTGetMinimumNode(BST*root)
{
while(root->lhs)
root=root->lhs;
returnroot;
}
//获得最大值
BST*BSTGetMaximumNode(BST*root)
{
while(root->rhs)
root=root->rhs;
returnroot;
}
//前序遍历
voidBSTPreorderTraverse(BST*node)
{
if(node)
{
printf("%d",node->data);
BSTPreorderTraverse(node->lhs);
BSTPreorderTraverse(node->rhs);
}
}
//中序遍历
voidBSTInorderTraverse(BST*node)
{
if(node)
{
BSTInorderTraverse(node->lhs);
printf("%d",node->data);
BSTInorderTraverse(node->rhs);
}
}
//后序遍历
voidBSTPostorderTraverse(BST*node)
{
if(node)
{
BSTPostorderTraverse(node->lhs);
BSTPostorderTraverse(node->rhs);
printf("%d",node->data);
}
}
//获得前继值
BST*BSTGetPredecessor(BST*root,BST*node)
{
BST*predecessor;
BST*rightCld;
if(node->lhs)
returnBSTGetMaximumNode(node->lhs);
predecessor=rightCld=node;
while((predecessor=BSTGetParentNode(root,predecessor)))
if(predecessor->rhs==rightCld)
returnpredecessor;
else
rightCld=predecessor;
return0;
}
//获得后继值
BST*BSTGetSuccessor(BST*root,BST*node)
{
BST*successor;
BST*leftCld;
if(node->rhs)
returnBSTGetMinimumNode(node->rhs);
successor=leftCld=node;
while((successor=BSTGetParentNode(root,successor)))
if(successor->lhs==leftCld)
returnsuccessor;
else
leftCld=successor;
return0;
}
//获得树高
intBSTGetTreeHeight(BST*root)
{
intl;
intr;
if(root)
{
l=BSTGetTreeHeight(root->lhs);
r=BSTGetTreeHeight(root->rhs);
return1+(l>r?l:r);
}
else
return-1;
}
//计算子节点数
intBSTGetSubtreeNodeNum(BST*node)
{
if(node)
returnBSTGetSubtreeNodeNum(node->lhs)
+BSTGetSubtreeNodeNum(node->rhs)
+1;
else
return0;
}
//用于打乱数组，交换
inlinevoidSwap(int*a,int*b)
{
inttemp;
temp=*a;
*a=*b;
*b=temp;
}
//用于打乱数组，qsort的比较用过程
inlineintCMP(constvoid*lhs,constvoid*rhs)
{
return*(constint*)lhs-*(constint*)rhs;
}
//数组有序?
intIsOrdered(int*beg,int*end)
{
intattri;
intcmpVal;
if(beg>=end)
return0;
if(end-beg<=2)
return1;
if(*beg<*(beg+1))
attri=1;
else
attri=0;
cmpVal=*beg++;
while(++beg!=end)
{
if(attri)
{
if(cmpVal>*beg)
return0;
}else
{
if(cmpVal<*beg)
return0;
}
}
return1;
}
//高层次打乱数组
voidHighlyUnorderArray(int*beg,int*end)
{
int*mid=beg+(end-beg)/2;
int*folk;
if(!IsOrdered(beg,end))
qsort(beg,end-beg,sizeof(int),CMP);
if((mid-beg)&1)
Swap(beg++,mid);
folk=beg+2;
while(folk<mid)
{
Swap(beg++,folk++);
Swap(beg++,folk++);
}
folk=mid+2;
while(folk<end)
{
Swap(folk,folk-1);
folk+=2;
}
}
//中序遍历结果输出到数组
voidBSTInorderWalkToArray(BST*root,int**p)
{
if(root)
{
BSTInorderWalkToArray(root->lhs,p);
**p=root->data;
(*p)++;
BSTInorderWalkToArray(root->rhs,p);
}
}
//平衡树，返回平衡好的新树
BST*BSTBalanceTree(BST*root)
{
intsize=BSTGetSubtreeNodeNum(root);
int*a=(int*)malloc(sizeof(int)*size);
int*end=a;
BST*balancedTree;
BSTInorderWalkToArray(root,&end);
HighlyUnorderArray(a,end);
balancedTree=BSTBuildTree(a,end);
free(a);
returnbalancedTree;
}
intmain()
{
inta[]=;
intc[]=;
BST*bstTree=BSTBuildTree(a,a+sizeof(a)/sizeof(a[0]));
BSTPreorderTraverse(bstTree);
putchar('\n');
BSTInorderTraverse(bstTree);
putchar('\n');
BSTPostorderTraverse(bstTree);
printf("\n\n");
BST*balancedTree=BSTBalanceTree(bstTree);
printf("%d%d\n",BSTGetTreeHeight(bstTree),BSTGetTreeHeight(balancedTree));
BSTDeleteTree(bstTree);
BSTDeleteTree(balancedTree);
}
7. 用二叉链表存储树，为什么根结点的右指针是空，数据结构
采用二叉树结构存储树或森林，即树/森林的左子右兄表示法。
二叉树中节点的左“孩子”是原树/森林对应节点的“长子节点”，右“孩子”是原树/森林对应节点的“兄弟节点”。
而树的根节点是没有兄弟的，故在二叉链表中它的右指针为空（）
8. 利用二叉链表存储树，则根节点的右指针是空的，这是为什么呢，谢谢
二叉链表存储树结构，那么任意节点的左孩子指向该结点的孩子结点，右孩子指针指向该节点的兄弟节点，因为这里是树，不是森林，所以树的根节点没有兄弟结点，则右指针是空。
9. 二叉链表存储方式实现二叉树
用C吗？