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嗎？