• 基本操作
• • 給某結點插入一個左孩子
  • 刪除二叉樹中某結點的左子樹
  • 根據先序與中序遍歷建立二叉樹
• 應用舉例
• • 查找數據元素
  • 二叉鏈表存儲結構 統計葉結點的數目

---

基本操作

通常有：建立空二叉樹、生成以X為根節點的數據域信息、將數據域信息為x的結點插入到二叉樹bt中、刪除某一個結點的左子樹/右子樹、查找某元素、遍歷

給某結點插入一個左孩子

btnode<DataType>*btTree::Insert(btTree bt,DataType x,BtTree parent){ //在二叉樹bt中的parent所指結點和其左子樹中 插入數據元素為x的結點 btTree p; if(parent==NULL){ return NULL;//如果不存在parent結點，不能進行插入，返回空指針 } p=new btnode;//申請結點空間 if(p==NULL) return NULL;//如果沒有存儲空間，返回空指針 p->data=x; p->lchild=NULL; P->rchild=NULL;//建立待插入結點 if(parent->lchild==NULL)parent->lchild=p;//如果parent沒有左孩子，直接插入 else { p->lchild=parent->lchild; parent->lchild=p;//parent的左孩子作為p的左孩子插入 } return bt;//返回根節點地址}

幾個注意點：
1.要先判錯，且多種情況都要考慮，parent為空的情況、p沒有申請到空間的情況
2.對于parent有無子樹也要分開寫
3.建立待插入結點時p->data=x;
p->lchild=NULL;
P->rchild=NULL;注意左右指針域也要初始化

刪除二叉樹中某結點的左子樹

btnode<DataType>*btTree::DeleteL(btTree L,btTree parent) { btTree p; if(parent==NULL||parent->lchild==NULL){ return NULL;//如果不存在parent結點，不能進行插入，返回空指針 } p=parent->lchild; parent->lchild=NULL; delete(p);//當p非葉子節點時，這樣只釋放了樹根結點的空間，若要刪除子樹分支中的結點，還需要用到遍歷 return bt; }

注意：這里當parent為空或者沒有左孩子都要返回空指針，不進行刪除操作

根據先序與中序遍歷建立二叉樹

下面給出該算法描述。假設二叉樹的先序序列和中序序列分別存放在一維數組preod[]與inod[]中，并假設二叉樹各結點的數據值均不相同。
寫法一：

void preInorder(char preod[],char inod[],int i,int j,int k,int h,btTree*t) { int m; (*t)=new btNode; (*t)->data=preod[i];//根結點 m=k;//中序遍歷中的第一個索引 while(inod[m]!=preod[i])m++; if(m==k)t->lchild=NULL;//此時左子樹序列為空 else preInorder(preod,inod,i+1,i+m-k,k,m-1,&((*t)->lchild))); if(m==h)//右子樹序列為空 preInorder(preod,inod,i+m-k+1,j,m+1,h,&((*t)->rchild));}

寫法二：

//把in_order[L1..R1]和post_order[L2..R2]建成一棵二叉樹，返回樹根 int build(int L1, int R1, int L2, int R2) {if (L1 > R1) return 0; //先判斷特殊情況：是否為空樹int root = post_order[R2];int p = L1;while (in_order[p] != root) p++;int cnt = p - L1; //左子樹的結點個數lch[root] = build(L1, p - 1, L2, L2 + cnt - 1);rch[root] = build(p + 1, R1, L2 + cnt, R2 - 1);return root; }

寫法三：

void rebuild(char * preOrder,char* inOrder,int nTreeLen,Node** root) { if(preOrder == NULL || inOrder == NULL) { return;//先檢查邊界條件 } Node*temp = new Node;//先獲得前序遍歷的第一個結點 temp->data = *preOrder; temp->left = NULL; temp->right = NULL; if(*root == NULL) *root = temp;//如果此結點為空，則把當前結點復制到根節點 if(nTreeLen == 1) return;//如果當前樹長度為1，則已經是最后一個結點 char *pOrgInorder = inOrder; char* pLeftEnd =inOrder;//尋找子樹長度 int templen = 0;//用于記錄臨時長度，避免溢出 while( *preOrder != * pLeftEnd ){ if(preOrder ==NULL||pLeftEnd ==NULL)return; templen ++; if(templen > nTreeLen)break; pLeftEnd++; } int LeftLen = (int)(pLeftEnd - pOrgInorder); int RightLen = nTreeLen - LeftLen-1;//右子樹長度 if(LeftLen>0) rebuild(preOrder+1,inOrder,LeftLen;&((*root)->left));//遞歸重建左子樹 if(RightLen>0)rebuild(preOrder+1+LeftLen,Inorder+LeftLen+1,RightLen,&((*root)->right)); }

應用舉例

查找數據元素

Search(bt,x) 在bt為根結點指針的二叉樹中查找數據元素x,查找成功時返回該結點的指針，失敗時返回空指針

biTree Search(btNode*bt,DataType x) {btNode*p;if(bt){if(bt->dara==x) return bt;if(bt->lchild){p=Search(bt->lchild,x);if(p) return p;}if(bt->rchild){p=Search(bt->rchild,x);if(p) return p;}}return NULL; }

注意要驗是否空指針：if(bt), if§return p;

二叉鏈表存儲結構 統計葉結點的數目

int CountLeaf(btNode*bt) { if(!bt) return 0;if(bt->lchild==NULL&&bt->rchild==NULL){ return 1;}return CountLeaf(bt->lchild)+CountLeaf(bt->rchild);}

總結

以上是生活随笔為你收集整理的【算法学习笔记】二叉树的基本操作实现和应用举例，根据先序与中序遍历建立二叉树的实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。