二叉树Notes

相比数组与链表

1.数组存储方式： 优：可以直接通过下标访问数组元素，效率高。对于有序数组，直接采用二分搜索就OK 缺：增删效率太低，因为移动了差不多整个数组 2.链表存储方式： 优：增删效率高 缺：检索效率低，每次要从head结点开始搜索 3.树存储方式： 能够提高存储，读取数据的效率

二叉树

粗略定义： 每个结点最多只能有两个子结点的一种形式 这颗二叉树共有三层，且是一颗满二叉树 路径：从root结点到当前结点的路线 树的高度：最大层数 子结点：eg ④和⑤均为②的子结点 满二叉树：所有叶子结点均在最后一层，结点总数为2^n-1; 完全二叉树：所有的叶子结点均在最后一层或倒数第二层，且最后一层的叶子结点在左边连续，倒数第二层的叶子结点在右边连续

几种遍历(递归)

1.前序遍历 即先输出父结点，再依次遍历左子树和右子树 代码：

void preOrder(Node* node) { if (node == NULL)return; cout << node->data << " "; preOrder(node->left); preOrder(node->right); }

2.中序遍历 即先遍历左子树，再输出父结点，最后遍历右子树 代码：

void infixOrder(Node* node) { if (node == NULL)return; infixOrder(node->left); cout << node->data << " "; infixOrder(node->right); }

3.后序遍历 即先依次遍历左右子树，最后再输出父结点 代码：

void postOrder(Node* node) { if (node == NULL)return; postOrder(node->left); postOrder(node->right); cout << node->data << " "; }

用递归代码是真的简洁又清晰

4.层序遍历 最接近人的思维的一种遍历… 用队列实现，先进先出

void levelOrder(Node* node){ if(node == NULL)return; queue<Node*>que; que.push(node); while(!que.empty()){ Node* tmp = que.front(); que.pop(); cout << tmp->data << " "; if(tmp->left)que.push(tmp->left); if(tmp->right)que.push(tmp->right); } }

用C语言描述

void levelOrder(Node* node){ Node* tree[100]; Node* tmp; int front = 0, rear = 0; tree[rear++] = node; while(front != rear){ tmp = tree[front++]; printf("%c ",tmp->data); if(tmp->left)tree[rear++]=tmp->left; if(tmp->right)tree[rear++]=tmp->right; } }

5.垂直输出

struct Location { int x, y; }; void gotoxy(int x, int y) { static int level = 0; int w = 0; if (y == 0) { level = 0; w = 0; } if (y != level) { cout << endl; w = 0; level++; } cout.width(x - w); w = x; } template<class T> void printBtree(BTNode<T>* root, int width) { if (root == NULL)return; int level = 0, offset = width / 2; queue<BTNode<T>*>q; queue<Location>lq; q.push(root); Location floc, cloc; floc.x = offset; floc.y = level; lq.push(floc); while (!q.empty()) { BTNode<T>* cur = q.front(); q.pop(); floc = lq.front(); lq.pop(); gotoxy(floc.x, floc.y); cout << cur->data; if (floc.y != level) { level++; offset /= 2; } if (cur->left) { q.push(cur->left); cloc.x = floc.x - offset; cloc.y = floc.y + 1; lq.push(cloc); } if (cur->right) { q.push(cur->right); cloc.x = floc.x + offset; cloc.y = floc.y + 1; lq.push(cloc); } } cout << endl; }

二叉树查找

对应着几种遍历，查找也有三种 1.先序查找

Node* preSearch(Node* node, int key) { if (node == NULL)return; if (node->data == key)return node; Node* res = NULL; if (node->left) { res = preSearch(node->left, key); } if (res)return res; if (node->right) { res = preSearch(node->right,key); } return res; }

其他两种大同小异，就不展示了

删除结点

一般来说，若删除的是叶子结点，则直接删除该结点即可 若删除的是非叶子结点，则要删除该子树 代码：

void deleNode(Node* node, int key) { if (!node)return; if (node->left && node->left->data == key) { node->left = NULL; return; } if (node->right && node->right->data == key) { node->right = NULL; return; } if (node->left) { deleNode(node->left, key); } if (node->right) { deleNode(node->right, key); } }

至于说这里为什么不考虑当前结点，因为后面我们传进去的参数会是root,在那里进行判断即可 当然，也可以在此处进行判断

顺序存储二叉树

特点 使用二叉完全树 第n个元素的左结点索引是2n+1 第n个元素的右结点索引是2n+2 第n个元素的父结点索引为(n-1)/2 那么 此时的先序遍历等价于

void PreO(int index) { if(arr.length==0||arr==null) { printf("Empty ArrBT"); return; } printf(arr[index]); if((index*2+1)<arr.length) { PreO(index*2+1); } if(index*2+2<arr.length) { PreO(index*2+2); } }

核心思想完全一样，所以说可以用数组来简单模拟二叉树