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

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

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

相关文章

来自专栏Android机动车

数据结构学习笔记——树(上)

之前一直介绍的是一对一的线性结构,可现实中还有多一对多的情况需要处理,这就是今天要介绍的一对多的数据结构——树。

752
来自专栏来自地球男人的部落格

[LeetCode] 113. Path Sum II

【原题】 Given a binary tree and a sum, find all root-to-leaf paths where each pa...

2077
来自专栏肖洒的博客

数据结构笔记(二)

栈是限定仅在表尾进行插入和删除操作的线性表。 队列是只允许在一段进行插入操作、而在另一端进行删除操作的线性表。

823
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题25二叉树中和为某一值的路径

题目:输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。PS:从根结点开始,一直到叶子结点形式一条路径。 分析:要找出路径之和为指定整...

2765
来自专栏WindCoder

二叉树的动态链式存储实现—C语言

2071
来自专栏撸码那些事

【图解数据结构】二叉查找树

1122
来自专栏向治洪

数据结构之二叉树

二叉树的定义: 二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及...

2035
来自专栏用户画像

4.3.2 线索二叉树

二叉树结点的各种遍历序列,其实质是对一个非线性结构进行线性化操作,使在这个访问序列中每一个结点(除第一个和最后一个)都有一个直接前驱和直接后继。

942
来自专栏开发与安全

数据结构:线索二叉树(Threaded Binary Tree)

我们知道满二叉树只是一种特殊的二叉树,大部分二叉树的结点都是不完全存在左右孩子的,即很多指针域没有被充分地利用。另一方面我们在对一棵二叉树做某种次序遍历的时候,...

2716
来自专栏猿人谷

二叉树的遍历——递归和非递归

二 叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是 递归定义...

1988

扫码关注云+社区