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

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

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 条评论
登录 后参与评论

相关文章

来自专栏nnngu

数据结构02 线性表之顺序表

这篇文章主要总结线性表之顺序表的相关操作,主要分以下几个部分来总结。 1、线性表是什么?  2、线性表的两种存储结构?  3、顺序表的存储结构表示?   4、顺...

3046
来自专栏Python爱好者

Java基础笔记12

1383
来自专栏我和未来有约会

Js中的变量

Js中的变量:  1:如果在var中没有初始化变量的值,则默认为undefined.  2:可以不用var来申明一个变量,但是在过程级中申明一个变量时,就必须用...

1816
来自专栏GopherCoder

Python 强化训练:第三篇

983
来自专栏全沾开发(huā)

学习zepto.js(对象方法)[5]

学习zepto.js(对象方法)[5] clone: 该方法不接收任何参数,会返回对象中的所有元素集合,但不会对象绑定的事件. var...

32211
来自专栏mwangblog

python元组(Turple)

1345
来自专栏java一日一条

浅谈Java中的equals和==

为什么第3行和第4行的输出结果不一样?==和equals方法之间的区别是什么?如果在初学Java的时候这个问题不弄清楚,就会导致自己在以后编写代码时出现一些低级...

442
来自专栏cs

C#3.0面向对象程序设计一

文章首发 http://www.imooc.com/article/22105 我还在简书。。。。。。 面向对象三大特征,继承,封装,多态 1.0 封...

2806
来自专栏诸葛青云的专栏

手把手教你c语言基础语法——结构体

在前面已经介绍了整形(int,long,….),浮点型(flaot,double),字符型(char),还介绍了数组(存储一组具有相同类型的数据),字符串。但是...

460
来自专栏Python爬虫与算法进阶

萌新刷题(十二)二叉树的前序遍历

题目 给出一棵二叉树,返回其节点值的前序遍历。 样例 给出一棵二叉树 {1,#,2,3}, 1 \ 2 / ...

3156

扫码关注云+社区