二叉树

二叉树构建

创建节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Node{
public:
char data;
Node * left;
Node * right;
Node(char data){
this->data = data;
left = right = NULL;
}
};
//创建一个节点
Node* node = new Node('D');
//删除一个节点
delete node;
node = NULL;

二叉树遍历

先序/中序/后序
以后序为例

1
2
3
4
5
6
7
void post_order(Node *root){
if (root){
post_order(root->left);
post_order(root->right);
cout<<root->data;
}
}

有先序和后序构建二叉树

1
2
3
4
5
6
7
8
9
10
11
Node* build_tree(string preOrder,string inOrder){
Node* root = new Node(preOrder[0]);
int position = inOrder.find(preOrder[0]);
if (position>=1){
root->left = build_tree(preOrder.substr(1,position+1),inOrder.substr(0,position));
}
if (inOrder.length()-1>position){
root->right = build_tree(preOrder.substr(position+1,preOrder.length()-1-position),inOrder.substr(position+1,inOrder.length()-1-position));
}
return root;
}

完全二叉树

注意:左右叶子节点=父节点×2,父节点×2+1

完全二叉树,第d层,起始为第2^d个节点,一共有2^d个节点