-
子樹
鎖定
設T是有根樹，a是T中的一個頂點，由a以及a的所有後裔（後代）導出的子圖稱為有向樹T的子樹。
- 中文名
- 子樹
- 外文名
- Subtree
- 類 型
- 計算機科學
- 學 科
- 跨學科
- 性 質
- 樹
- 概 念
- T1中存在從節點n的子樹與T2相同
子樹介紹
設T是有根樹，a是T中的一個頂點，由a以及a的所有後裔（後代）導出的子圖稱為有向樹T的子樹，a是子樹的根。
[1]
具體來説，子樹就是樹的其中一個節點以及其下面的所有的節點所構成的樹。比如在下圖1中把A和E中間的那根線刪除，節點E 、I、 J、 P、 Q就構成了一顆以E為根節點的子樹。
圖1
具有代表性的是中的二叉樹左子樹、右子樹，左子樹就是以當前節點看，它的左子節點那一分支的子樹，該子樹以當前節點左子節點為根。右子樹就是以當前節點看，它的右子節點那一分支的子樹，該子樹以當前節點右子節點為根。左右子樹只在二叉樹中有意義，因為二叉樹非左即右。
子樹代碼
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為待刪除節點數 */
}
}
- 詞條統計
-
- 瀏覽次數：次
- 編輯次數：5次歷史版本
- 最近更新： 麦芽的阳光