关于数据结构二叉树的简答题 数据结构二叉树题目
\u6570\u636e\u7ed3\u6784\u7b80\u7b54\u9898\u4e8c\u53c9\u6811\u5c31\u662f\u5ea6\u4e3a2\u7684\u6811,\u8fd9\u4e2a\u7ed3\u8bba\u6b63\u786e\u5417\uff1f\u4e3a\u4ec0\u4e48\uff1f\u80af\u5b9a\u662f\u9519\u7684
\u4e8c\u53c9\u6811\u7684\u5ea6\u4ee3\u8868\u67d0\u4e2a\u7ed3\u70b9\u7684\u5b69\u5b50\u6216\u8005\u8bf4\u76f4\u63a5\u540e\u7ee7\u7684\u4e2a\u6570\uff0c1\u5ea6\u662f\u53ea\u6709\u4e00\u4e2a\u5b69\u5b50\u6216\u8005\u8bf4\u5355\u5b50\u6811\uff0c2\u5ea6\u662f\u6709\u4e24\u4e2a\u5b69\u5b50\u6216\u8005\u8bf4\u5de6\u53f3\u5b50\u6811\u90fd\u6709
\u4e8c\u53c9\u6811\u5ea6\u6570\u6700\u5927\u4e3a2\uff0c\u4e8c\u53c9\u6811\u4e94\u79cd\u57fa\u672c\u5f62\u6001\uff1a\u7a7a\u4e8c\u53c9\u6811\uff0c\u4ec5\u6709\u6839\u8282\u70b9\u7684\u4e8c\u53c9\u6811\uff0c\u5de6\u5b50\u6811\u4e3a\u7a7a\u7684\u4e8c\u53c9\u6811\uff0c\u53f3\u5b50\u6811\u4e3a\u7a7a\u7684\u4e8c\u53c9\u6811\uff0c\u5de6\u53f3\u5b50\u6811\u5747\u4e0d\u4e3a\u7a7a\u7684\u4e8c\u53c9\u6570
\u4e0b\u9762\u662fc++\u7684\u4ee3\u7801\u3002 \u4e3b\u8981\u662f\u4e00\u4e2a\u9012\u5f52\u7684\u601d\u7ef4\u3002\u6536\u597d\u90fd\u662f\u6211\u81ea\u5df1\u5199\u7684\uff0c\u80fd\u7528
//BinTree.h \u5b9a\u4e49
struct Node {int data;Node *lchild,*rchild;};class BinTree { Node *Root;public:BinTree();BinTree(char pre[]);BinTree(char pre[],char mid[],int n);virtual ~BinTree();void PreOrder();void MidOrder();void PostOrder();Node * Search(int x);int Count();int LeafCount();int Depth();private:void PreOrder(Node *p);void MidOrder(Node *p);void PostOrder(Node *p);Node * Search(Node *p, int x);int Count(Node *p);int LeafCount(Node *p);int Depth(Node *p);Node *CreateByPre(char pre[],int &i);Node *CreateByPreMid(char pre[],int ipre, char mid[], int imid,int n);};//BinTree.cpp
// BinTree.cpp: implementation of the BinTree class.#include "BinTree.h"BinTree::BinTree() //\u65e0\u53c2\u6784\u9020\u51fd\u6570{Root = NULL;}BinTree::BinTree(char pre[]) {int i = 0;Root = CreateByPre(pre, i);}Node *BinTree::CreateByPre(char pre[], int &i){char c = pre[i]; i++;if(c == '*') return NULL;Node *p = new Node;p->data = c-'0';p->lchild = CreateByPre(pre, i);p->rchild = CreateByPre(pre, i);return p;}//\u6839\u636e\u5148\u5e8f\u5e8f\u5217\u4e2d\u5e8f\u5e8f\u5217 \u521b\u5efa\u4e8c\u53c9\u6811BinTree::BinTree(char pre[], char mid[], int n){Root = CreateByPreMid(pre, 0, mid, 0, n);}//\u5148\u5e8f\u5e8f\u5217: pre[ipre]...pre[ipre+n-1]//\u4e2d\u5e8f\u5e8f\u5217: mid[imid]...mid[imid+n-1]Node *BinTree::CreateByPreMid(char pre[], int ipre, char mid[], int imid, int n){if(n data = pre[ipre] - '0';for(int i = 0; i lchild = CreateByPreMid(pre,ipre+1, mid, imid, i );p->rchild = CreateByPreMid(pre,ipre+i+1, mid, imid+i+1, n-i-1);return p;}BinTree::~BinTree(){}void BinTree::PreOrder(){PreOrder(Root); //\u5148\u5e8f\u904d\u5386cout data lchild); //\u5148\u5e8f\u904d\u5386\u5de6\u5b50\u6811PreOrder(p->rchild); //\u5148\u5e8f\u904d\u5386\u53f3\u5b50\u6811}void BinTree::MidOrder(){MidOrder(Root); //\u4e2d\u5e8f\u904d\u5386cout lchild); //\u4e2d\u5e8f\u904d\u5386\u5de6\u5b50\u6811cout data rchild); //\u4e2d\u5e8f\u904d\u5386\u53f3\u5b50\u6811}void BinTree::PostOrder(){PostOrder(Root); //\u4e2d\u5e8f\u904d\u5386cout lchild); //\u540e\u5e8f\u904d\u5386\u5de6\u5b50\u6811PostOrder(p->rchild); //\u540e\u5e8f\u904d\u5386\u53f3\u5b50\u6811cout data lchild); int right = Depth(p->rchild); if(left > right) return left + 1; else return right + 1;}//\u67e5\u8be2\u503cx\u7684\u8282\u70b9Node * BinTree::Search(int x){ return Search(Root,x);}Node * BinTree::Search(Node *p, int x){ if(p == NULL) return NULL; if(p->data == x) return p; Node *q = Search(p->lchild,x); //\u6309\u7167\u5148\u5e8f \u67e5\u627e\u5de6\u5b50\u6811 if(q != NULL) return q; return Search(p->rchild,x); //\u6309\u7167\u5148\u5e8f \u67e5\u627e\u53f3\u5b50\u6811}//\u6240\u6709\u8282\u70b9\u4e2a\u6570int BinTree::Count(){ return Count(Root);}int BinTree::Count(Node *p){ if(p==NULL) return 0; int left = Count(p->lchild); int right= Count(p->rchild); return left+right+1;}//\u6240\u6709\u53f6\u5b50\u8282\u70b9\u7684\u4e2a\u6570int BinTree::LeafCount(){return LeafCount(Root);}int BinTree::LeafCount(Node *p){if(p==NULL) return 0;if(p->lchild==NULL && p->rchild==NULL) return 1;int left =LeafCount(p->lchild); int right=LeafCount(p->rchild); return left+right;}
绛旓細棰樼洰32瑕佹眰鏍规嵁鍓嶅簭閬嶅巻鍜屼腑搴忛亶鍘嗗簭鍒楃‘瀹浜屽弶鏍戠殑缁撴瀯銆傚墠搴忛亶鍘嗗簭鍒椾负ABCDEFG锛屾剰鍛崇潃鏍硅妭鐐规槸A銆傞氳繃瑙傚療閫夐」锛屾垜浠彲浠ュ彂鐜板彧鏈夐夐」C涓殑鏍硅妭鐐规槸A銆傜劧鍚庯紝鎴戜滑闇瑕佹鏌ユ瘡涓夐」鏄惁婊¤冻鍓嶅簭閬嶅巻鐨勬潯浠讹紝鍗虫牴鑺傜偣鍦ㄦ渶鍓嶉潰銆傞夐」C涓紝鏍硅妭鐐笰鍚庨潰璺熺潃鐨勬槸D锛岀劧鍚庢槸B锛岀鍚堝墠搴忛亶鍘嗙殑鐗圭偣銆傚洜姝わ紝閫夐」...
绛旓細涓妫靛畬鍏ㄤ簩鍙夋爲涓婃湁1001涓粨鐐癸紝鍏朵腑鍙跺瓙缁撶偣鐨勪釜鏁版槸501銆備竴涓叿鏈1025涓粨鐐圭殑浜屽弶鏍戠殑楂榟涓11鑷1025涔嬮棿銆傚浜庢湁n涓粨鐐圭殑浜屽弶鏍戯紝鍏堕珮搴︿负ëlog2nû+1銆傞珮搴︿负k鐨勪簩鍙夋爲鏈澶х殑缁撶偣鏁颁负2鐨刱-1娆℃柟銆傛繁搴︿负k鐨勫畬鍏ㄤ簩鍙夋爲鑷冲皯鏈2鐨刱-1娆℃柟涓粨鐐癸紝鑷冲鏈2鐨刱娆℃柟鍑1涓粨鐐广備竴妫...
绛旓細1.鍏锋湁10涓粨鐐圭殑浜屽弶鏍戜腑鏈夛紙B锛変釜搴︿负2鐨勭粨鐐 A.8 B.9 C.10 D.11 濡傛灉鏄5000涓粨鐐瑰張鎬庝箞瑙ｏ紵2.璁剧粰瀹氭潈鍊兼绘暟鍙坣涓紝鍏跺搱澶浖鏍戠殑缁撶偣鎬绘暟涓猴細锛堬級蹇樹簡绛旀浜嗙湅浜嗗悗琛ヤ笂鏉 A.涓嶇‘瀹 B.2n C.2n+1 D.2n-1 3.鑻ヤ簩鍙夋爲閲囩敤浜屽弶閾捐〃瀛樺偍缁撴瀯锛岃浜ゆ崲鍏跺簻鍝︽湁鍒嗘敮缁撶偣宸︺佸彸鐨勪綅缃...
绛旓細浜屽弶鏍鐨勫害浠ｈ〃鏌愪釜缁撶偣鐨勫瀛愭垨鑰呰鐩存帴鍚庣户鐨勪釜鏁帮紝1搴︽槸鍙湁涓涓瀛愭垨鑰呰鍗曞瓙鏍戯紝2搴︽槸鏈変袱涓瀛愭垨鑰呰宸﹀彸瀛愭爲閮芥湁 浜屽弶鏍戝害鏁版渶澶т负2锛屼簩鍙夋爲浜旂鍩烘湰褰㈡侊細绌轰簩鍙夋爲锛屼粎鏈夋牴鑺傜偣鐨勪簩鍙夋爲锛屽乏瀛愭爲涓虹┖鐨勪簩鍙夋爲锛屽彸瀛愭爲涓虹┖鐨勪簩鍙夋爲锛屽乏鍙冲瓙鏍戝潎涓嶄负绌虹殑浜屽弶鏁 ...
绛旓細B銆傚浜庝换浣曚竴棰椾簩鍙夋爲T锛屽鏋滃叾缁堢缁撶偣鏁颁负n0锛屽害涓2鐨勭粨鐐规暟涓簄2锛屽垯锛宯0=n2+1锛屽彾瀛愮粨鐐(缁堢缁撶偣)no=15+1=16銆傛垨锛氭瘡涓垎鏋濅笅闈㈤兘鏈変竴涓粨鐐癸紝鎵浠ユ荤粨鐐规暟N=2*15+1*32+0*鍙跺瓙鏁+1(鏍硅妭鐐癸級=63 浜屽弶鏍戜腑闄や簡鍙屽垎鏀粨鐐癸紝鍗曞垎鏀粨鐐瑰氨鏄彾瀛愮粨鐐 鎵浠ュ彾瀛愭暟=63-15-32=16 ...
绛旓細浜屽弶鏍戠殑鍒嗘敮璇寸洿鐧戒簡灏辨槸绾挎銆傛瘮濡備笅鍥句腑鐨勪簩鍙夋爲灏辨湁5涓垎鏀傚畾鐞1銆佷簩鍙夋爲鐨勫垎鏀暟绛変簬浜屽弶鏍戜腑鎵鏈夎妭鐐圭殑搴︾殑鎬诲拰銆傛瘮濡備笂鍥句腑鍚勪釜鑺傜偣鐨勫害鍒嗗埆涓猴細A=2锛孊=2锛孋=1锛孌=0锛孍=0锛孎=0 2+2+1+0+0+0=5 瀹氱悊2銆佸湪浠绘剰涓妫典簩鍙夋爲涓紝搴︽暟涓0鐨勭粨鐐癸紙鍗冲彾瀛愮粨鐐癸級鎬绘瘮搴︿负2鐨勭粨鐐瑰涓...
绛旓細32锛庝竴妫浜屽弶鏍戠殑鍓嶅簭閬嶅巻搴忓垪涓篈BCDEFG锛屽畠鐨勪腑搴忛亶鍘嗗簭鍒楀彲鑳芥槸锛堬級A锛嶤ABDEFG B锛嶢BCDEFG C锛嶥ACEFBG D锛嶢DCFEG 33锛庡凡鐭ヤ竴妫典簩鍙夋爲鐨勫墠搴忛亶鍘嗙粨鏋滀负ABCDEF,涓簭閬嶅巻缁撴灉涓篊BAEDF,鍒欏悗搴忛亶鍘嗙殑缁撴灉涓猴紙A 锛夈侫锛嶤BEFDA B锛嶧EDCBA C锛嶤BEDFA D锛庝笉瀹 34锛庡凡鐭ユ煇浜屽弶鏍戠殑鍚庡簭閬嶅巻搴忓垪鏄...
绛旓細璁炬牴鑺傜偣鐨勬繁搴︿负1銆備粠涓婂埌涓嬬殑涓暟渚濇涓1/2/4/8鈥︹︼紝姣忓眰鏈澶氭湁鍙跺瓙鑺傜偣鐨勪釜鏁颁负2鐨勶紙i-1锛夋鏂癸紝i 涓烘繁搴︺傝繖閲岀殑n=64锛屽洜姝わ紝64=2鐨勶紙i-1锛夋柟锛屾墍浠=7銆 浣嗘槸锛岀敱浜庢槸瀹屽叏浜屽弶鏍锛屽洜姝ゅ彲浠ュ湪绗叓灞傞噷鏈1涓彾瀛愯妭鐐癸紙鏈澶氬彧鑳芥湁涓涓級锛岀鍏眰鐨勯偅涓彾瀛愯妭鐐瑰皢绗竷灞傜殑瑕嗙洊銆...
绛旓細鍙湁涓绉嶆儏鍐碉紝灞傛暟鎵嶅彲鑳芥槸8鍗筹細绗竷灞傚叏閮ㄦ帓婊★紙64涓妭鐐癸級绗叓灞傚彧鏈変竴涓妭鐐 鎬诲叡鐨勫彾瀛愯妭鐐瑰氨涓7灞傜殑63涓+鍏眰鐨1涓紱娌℃湁鍏紡锛屾寜瀹屽叏浜屽弶鏍戠殑鎬ц川鎺ㄨ涓嬪氨鐭ラ亾銆傚師鏉ヤ綘瀵瑰畾涔変笉鐔熸倝锛(1)瀹屽叏浜屽弶鏍戔斺鑻ヨ浜屽弶鏍戠殑楂樺害涓篽锛岄櫎绗 h 灞傚锛屽叾瀹冨悇灞 (1锝瀐-1)鐨勭粨鐐规暟閮借揪鍒版渶澶т釜...
绛旓細鍏堝簭閬嶅巻锛1.2.5.6.3.4.7.9.8.10.11.13.12.14
