設T是有根樹，a是T中的一個頂點，由a以及a的所有後裔（後代）導出的子圖稱為有向樹T的子樹。
基本介紹
- 中文名：子樹
- 外文名：Subtree
- 類型：計算機科學
- 學科：跨學科
- 性質：樹
- 概念：T1中存在從節點n的子樹與T2相同
介紹,代碼,
介紹
設T是有根樹，a是T中的一個頂點，由a以及a的所有後裔（後代）導出的子圖稱為有向樹T的子樹，a是子樹的根。具體來說，子樹就是樹的其中一個節點以及其下面的所有的節點所構成的樹。比如在下圖中把A和E中間的那根線刪除，節點E 、I、 J、 P、 Q就構成了一顆以E為根節點的子樹。
具有代表性的是中的二叉樹左子樹、右子樹，左子樹就是以當前節點看，它的左子節點那一分支的子樹，該子樹以當前節點左子節點為根。右子樹就是以當前節點看，它的右子節點那一分支的子樹，該子樹以當前節點右子節點為根。左右子樹只在二叉樹中有意義，因為二叉樹非左即右。
代碼
1、樹節點定義
struct TreeNode{ int val; TreeNode *next; TreeNode(int v) : val(v), next(NULL) {}};2、判斷一棵樹是否是另一棵樹的子樹
bool IsPart(TreeNode *root1, TreeNode *root2){ if (root2 == NULL) return true; if (root1 == NULL) return false; if (root1->val != root2->val) return false; return IsPart(root1->left, root2->left) && IsPart(root1->right, root2->right);}bool IsPartTree(TreeNode *root1, TreeNode *root2){ bool result = false; if (root1 != NULL && root2 != NULL) { if (root1->val == root2->val) result = IsPart(root1, root2); if (!result) result = IsPartTree(root1->left, root2); if (!result) result = IsPartTree(root1->right, root2); } return result;}3、刪除子樹
Status deleted[MAX_TREE_SIZE+1]; /* 刪除標誌數組(全局量) */void DeleteChild(PTree *T,TElemType p,int i){ /* 初始條件：樹T存在，p是T中某個節點，1≤i≤p所指節點的度 */ /* 操作結果：刪除T中節點p的第i棵子樹 */ int j,k,n=0; LinkQueue q; QElemType pq,qq; for(j=0;j<=T->n;j++) deleted[j]=0; /* 置初值為0(不刪除標記) */ pq.name='a'; /* 此成員不用 */ InitQueue(&q); /* 初始化佇列 */ for(j=0;j<T->n;j++) if(T->nodes[j].data==p) break; /* j為節點p的序號 */ for(k=j+1;k<T->n;k++) { if(T->nodes[k].parent==j) n++; if(n==i) break; /* k為p的第i棵子樹節點的序號 */ } if(k<T->n) /* p的第i棵子樹節點存在 */ { n=0; pq.num=k; deleted[k]=1; /* 置刪除標記 */ n++; EnQueue(&q,pq); while(!QueueEmpty(q)) { DeQueue(&q,&qq); for(j=qq.num+1;j<T->n;j++) if(T->nodes[j].parent==qq.num) { pq.num=j; deleted[j]=1; /* 置刪除標記 */ n++; EnQueue(&q,pq); } } for(j=0;j<T->n;j++) if(deleted[j]==1) { for(k=j+1;k<=T->n;k++) { deleted[k-1]=deleted[k]; T->nodes[k-1]=T->nodes[k]; if(T->nodes[k].parent>j) T->nodes[k-1].parent--; } j--; } T->n-=n; /* n為待刪除節點數 */ } }