二叉树的遍历、查找、插入以及删除

二叉树的主要存储方式是链接存储,标准存储结构也称为二叉链表。 二叉链表结点类的定义

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;
        }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mathor

二叉树的下一个结点&二叉树的上一个结点

 最笨的方法就是一直网上回溯,直到找到了头结点,然后从头结点开始重新中序遍历一次树,然后得到答案  还有一种比较巧妙的方法,先判断当前结点有没有右子树,如果有...

442
来自专栏章鱼的慢慢技术路

笔试常考题型之二叉树的遍历

1345
来自专栏琯琯博客

PHP二叉树(一):平衡二叉树(AVL)

平衡二叉树 <?php /** * description: 平衡二叉树 */ //结点 class Node { public $key; ...

2769
来自专栏nnngu

算法08 五大查找之:二叉排序树(BSTree)

上一篇总结了索引查找,这一篇要总结的是二叉排序树(Binary Sort Tree),又称为二叉查找树(Binary Search Tree) ,即BSTree...

3416
来自专栏ACM算法日常

二叉搜索树(BST)- HDU 3791

二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sor...

591
来自专栏书山有路勤为径

二叉查找树

二叉查找树是一种数据结构,它是具有以下性质的二叉树: 1.若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值; 2.若右子数不空,则右子树上所有...

512
来自专栏章鱼的慢慢技术路

笔试常考题型之二叉树的遍历

1624
来自专栏菩提树下的杨过

数据结构与算法C#版笔记--查找(Search)

做数据库开发的程序员,可能每天都会处理各种各样的查询sql,这个就是查找(Search)。通过查询记录主键字段(即主关键码)或其它非唯一字段(即次关键码)找到所...

2097
来自专栏用户画像

4.3.1 二叉树的遍历

所谓二叉树的遍历,是指按照某条搜索路径访问树中的每个结点,使得每个几点均被访问一次,而且仅被访问一次。

682
来自专栏拭心的安卓进阶之路

重温数据结构:二叉树的常见方法及三种遍历方式 Java 实现

树的分类有很多种,但基本都是 二叉树 的衍生,今天来学习下二叉树。 ? 什么是二叉树 Binary Tree 先来个定义: 二叉树是有限个节点的集合,这个集合...

2056

扫码关注云+社区