每一個格子都有一個數(shù)和一個指針

缺點(diǎn)：

要一個一個找數(shù)，比如上圖，最多要找5次才能找到數(shù)

復(fù)雜度是O(n)

這一個二叉樹最多只用找三次就能找到數(shù)

復(fù)雜度是O(log n)

左子結(jié)點(diǎn)和右子結(jié)點(diǎn)：一個結(jié)點(diǎn)的左右兩個字結(jié)點(diǎn)

父結(jié)點(diǎn)：一個結(jié)點(diǎn)把它的子結(jié)點(diǎn)稱為父結(jié)點(diǎn)

兄弟結(jié)點(diǎn)：一個結(jié)點(diǎn)的兩個子結(jié)點(diǎn)互稱為兄弟結(jié)點(diǎn)

葉結(jié)點(diǎn)就是沒有延伸的結(jié)點(diǎn)，因?yàn)槿~子不能再分叉，所以叫葉結(jié)點(diǎn)

這里的4,6,7三個結(jié)點(diǎn)就是葉子結(jié)點(diǎn)

其余的非葉子結(jié)點(diǎn)被叫做分支結(jié)點(diǎn)

樹的深度是所有節(jié)點(diǎn)中最大層數(shù)被稱為樹的深度

如圖，從一個結(jié)點(diǎn)到根結(jié)點(diǎn)的所有數(shù)都是這個數(shù)的祖先結(jié)點(diǎn)；反過來，一個節(jié)點(diǎn)到子樹中所有節(jié)點(diǎn)都叫后代節(jié)點(diǎn)

1.前序遍歷

void Preorder(node *p){

if(!p) return;

visit(p);

Preorder(p->left_son);

Preorder(p->right_son);

}

2.中序遍歷

void Inorder(node *p){

if(!p) return;

Inorder(p->left_son);

visit(p);

norder(p->right_son);

}

3.后序遍歷

void Postorder(node *p){

if(!p) return;

Postorder(p->left_son);

Postorder(p->right_son);

visit(p);

}

最后點(diǎn)個贊吧，謝謝