二叉树的遍历、查找、插入以及删除
二叉树的主要存储方式是链接存储，标准存储结构也称为二叉链表。 二叉链表结点类的定义
struct Node{
Node *left, *right; //左右子树
T data;
};常见的二叉树遍历方式
下面给个实例来表示具体的遍历方式：
前序遍历访问顺序：访问根结点；左子树；右子树。 首先访问根结点A，然后左子树L；因为L也采用前序遍历的方式，则首先访问L的左子树B，B没有孩子结点，接下来访问L的右子树，这样以A的左子树遍历完毕，剩下遍历右子树。 对应前序遍历顺序：A-L-B-E-C-D-W-X
//前序遍历递归实现
void preOrder(Node *t)
{if (t==NULL) return;
cout<<t->data<<'';
preOrder(t->left);
preOrder(t->right);
}中序遍历访问顺序：左子树；访问根结点；右子树。 首先遍历根结点A的左子树，最先访问为B-L-E,左子树遍历结束；接下来就是A的右子树C，因为C没有左子树，根据中序遍历顺序，则访问C，然后访问C对应的右子树D（注意这时并不是D，因为D还有左子树，所以先访问W，W的右子树X，才轮到D）通俗一点讲就相当于排队时候本来轮到你的顺序了，结果你前面那一位代替别人留了几个位置，所以只能等待人家。 对应中序遍历顺序：B-L-E-A-C-W-X-D 后序遍历访问顺序：左子树；右子树；访问根结点。 对应后序遍历顺序：B-E-L-X-W-D-C-A
//后序遍历递归实现
void postOrder(Node *t)
{if (t==NULL) return;
preOrder(t->left);
preOrder(t->right);
cout<<t->data<<'';
}二叉树的一个重要应用就是查找。这里用到了二叉排序树，二叉排序树的三大基本操作： （1）查找 find（tree，x）； 二叉排序树的查找实现:
bool find(Node *t,T x)
{if (t==NULL) return false; //空树
else if(x<t->data) return find(t->left,x);
else if(x>t->data) return find(t->right,x);
else return true;
}（2）插入 insert（tree，x）；
void insert(Node * &t,T x)
{if (t==NULL) return t = new Node(x,NULL,NULL);
else if(x<t->data) insert(t->left,x);
else if(x>t->data) insert(t->right,x);
}（3）删除 remove（tree，x）； 二叉排序树上最复杂的操作就是remove，因为树中结点可以有两个儿子，若删除根结点就会将原来的树分裂成三部分。 删除操作过程： 首先比较被删结点和根结点的值，根据比较结果分三种情况删除。如果小于根结点，在左子树上删除；大于根结点，在右子树上删除；等于根结点，删除根结点。在删除根结点的时候，考虑有两个儿子的时候，把右子树上的最小值作为替身，删除替身。否则，将结点的非空儿子替代被删结点的位置，释放被删结点的空间。
void remove(Node * &t,T x)
{if (t==NULL) return false; //空树
else if(x<t->data) remove(t->left,x); //在t的左子树上删除X
else if(x>t->data) remove(t->right,x); //右子树上删除
else if(t->left!=NULL && t->right!=NULL) //有两个孩子
{Node *tmp = t->right;
while(tmp->left!=NULL) tmp = tmp->left;
t->data = tmp->data;
remove(t->right,t->data);
}
else{ //被删结点是叶结点或只有一个孩子
Node * oldNode = t;
t = (t->left!=NULL)?t->left:t->right;
delete oldNode;
}
}腾讯云开发者
