資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝研究
法律研究C++中的連續樹
連續樹定義為：從根節點到葉節點的任何路徑上的節點值或權重，使得父節點與其所有直接子節點之間的絕對差值始終為1。
如果我們在根到葉的路徑上選擇任何節點，則
|節點權重 - 左子節點權重| = |左子節點權重 - 節點權重| = 1，對右子節點也成立
|節點權重 - 右子節點權重| = |右子節點權重 - 節點權重| = 1
圖表
讓我們透過示例來理解。
下面的樹是連續的，因為父節點與其子節點之間的絕對差值始終為1。
下面的樹不符合連續樹的條件。
查詢樹是否連續的演算法
如果根節點為空，則返回1
如果是葉節點，則返回1，因為樹是連續的，這就是葉節點被訪問的原因。
如果左子樹為空，則檢查當前節點與右子節點的連續性（計算權重的絕對差值），並遞迴地繼續處理右子樹。
如果右子樹為空，則檢查當前節點與左子節點的連續性（計算權重的絕對差值），並遞迴地繼續處理左子樹。
否則，計算左子節點和右子節點權重的絕對差值，並遞迴地繼續處理左子樹和右子樹。
虛擬碼
// Function to check tree is continuous or not
struct btreeNode{
int data;
btreeNode* left, * right;
};
int isContinuous(btreeNode *root){
// if node is NULL return 1, exit condition
if (root == NULL)
return 1;
//if leaf node is reached then tree must be continous during this path
if (root->left == NULL && root->right == NULL)
return 1;
// if no left child
if (root->left == NULL)
return (abs(root->data - root->right->data) == 1) && isContinuous(root->right);
// if no right child
if (root->right == NULL)
return (abs(root->data - root->left->data) == 1) && isContinuous(root->left);
// calculate absoute difference
return abs(root->data - root->left->data)==1 && abs(root->data - root->right->data)==1 &&
isContinuous(root->left) && isContinuous(root->right);
}
更新於：2020年8月3日
瀏覽量：156
廣告