介绍下二叉树

发布网友发布时间：2022-04-26 23:59

我来回答

共2个回答

懂视网时间：2022-04-22 16:34

本篇文章给大家带来的内容是关于JavaScript二叉树（二叉搜索树）的详细介绍，有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。

可能有一部分人没有读过我上一篇写的二叉堆，所以这里把二叉树的基本概念复制过来了，如果读过的人可以忽略前面针对二叉树基本概念的介绍，另外如果对链表数据结构不清楚的最好先看一下本人之前写的js数据结构-链表

二叉树

二叉树(Binary Tree)是一种树形结构，它的特点是每个节点最多只有两个分支节点，一棵二叉树通常由根节点，分支节点，叶子节点组成。而每个分支节点也常常被称作为一棵子树。

根节点：二叉树最顶层的节点

分支节点：除了根节点以外且拥有叶子节点

叶子节点：除了自身，没有其他子节点

常用术语
在二叉树中，我们常常还会用父节点和子节点来描述，比如图中2为6和3的父节点，反之6和3是2子节点

二叉树的三个性质

在二叉树的第i层上，至多有2^i-1个节点
i=1时，只有一个根节点，2^(i-1) = 2^0 = 1
深度为k的二叉树至多有2^k-1个节点
i=2时，2^k-1 = 2^2 - 1 = 3个节点
对任何一棵二叉树T，如果总结点数为n0，度为2(子树数目为2)的节点数为n2,则n0=n2+1

树和二叉树的三个主要差别

树的节点个数至少为1，而二叉树的节点个数可以为0

树中节点的最大度数(节点数量)没有,而二叉树的节点的最大度数为2

树的节点没有左右之分，而二叉树的节点有左右之分

二叉树分类

二叉树分为完全二叉树(complete binary tree)和满二叉树(full binary tree)

满二叉树：一棵深度为k且有2^k - 1个节点的二叉树称为满二叉树

完全二叉树：完全二叉树是指最后一层左边是满的，右边可能满也可能不满，然后其余层都是满的二叉树称为完全二叉树(满二叉树也是一种完全二叉树)

二叉搜索树

二叉搜索树满足以下的几个性质：

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；

任意节点的左、右子树也需要满足左边小右边大的性质

我们来举个例子来深入理解以下

一组数据：12,4,18,1,8,16,20
由下图可以看出，左边的图满足了二叉树的性质，它的每个左子节点都小于父节点，右子节点大于其父节点，同时左子树的节点都小于根节点，右子树的节点都大于根节点

二叉搜索树主要的几个操作：

查找（search）

插入（insert）

遍历（transverse）

二叉树搜索树的链式存储结构

通过下图，可以知道二叉搜索树的节点通常包含4个域，数据元素，分别指向其左，右节点的指针和一个指向父节点的指针所构成，一般把这种存储结构称为三叉链表。
图片描述

用代码初始化一个二叉搜索树的结点：

一个指向父亲节点的指针 parent

一个指向左节点的指针 left

一个指向右节点的指针 right

一个数据元素，里面可以是一个key和value

 class BinaryTreeNode {
 constructor(key, value){
  this.parent = null;
  this.left = null;
  this.right = null;
  this.key = key;
  this.value = value;
 }
 }

接着我们再用代码去初始化一个二叉搜索树

在二叉搜索树中我们会维护一个root指针，这个就相当于链表中的head指针，在没有任何节点插入的时候它指向空，在有节点插入以后它指向根节点。

 class BinarySearchTree {
 constructor() {
  this.root = null;
 }
 }

创建节点

 static createNode(key, value) {
 return new BinarySearchTree(key, value);
 }

插入操作

看下面这张图，13是我们要插入的节点，它插入的具体步骤：

跟根节点12做比较，比12大，所以我们确定了，这个节点是往右子树插入的
而根节点的右边已经有节点，那么跟这个节点18做比较，结果小于18所以往18的左节点找位置
而18的左节点也已经有节点了，所以继续跟这个节点做比较，结果小于16
刚好16的左节点是空的(left=null)，所以13这个节点就插入到了16的左节点

通过上面的描述，我们来看看代码是怎么写的

定义两个指针，分别是p和tail，最初都指向root，p是用来指向要插入的位置的父节点的指针，而tail是用来查找插入位置的，所以最后它会指向null，用上图举个例子，p最后指向了6这个节点，而tail最后指向了null（tail为null则说明已经找到了要插入的位置）

循环，tail根据我们上面分析的一步一步往下找位置插入，如果比当前节点小就往左找，大则往右找，一直到tail找到一个空位置也就是null

如果当前的root为null，则说明当前结构中并没有节点，所以插入的第一个节点直接为跟节点，即this.root = node

将插入后的节点的parent指针指向父节点

 insert(node){
 let p = this.root;
 let tail = this.root;
 
 // 循环遍历，去找到对应的位置
 while(tail) {
  p = tail;
  // 要插入的节点key比当前节点小
  if (node.key < tail.key){
  tail.left = tail.left;
  }
  // 要插入的节点key比当前节点大
  else {
  tail.right = tail.right;
  }
 }
 
 // 没有根节点，则直接作为根节点插入
 if(!p) {
  this.root = node;
  return;
 }
 
 // p是最后一个节点，也就是我们要插入的位置的父节点
 // 比父节点大则往右边插入
 if(p.key < node.key){
  p.right = node;
 }
 // 比父节点小则往左边插入
 else {
  p.left = node;
 }
 
 // 指向父节点
 node.parent = p;

 }

查找

查找就很简单了，其实和插入差多，都是去别叫左右节点的大小，然后往下找

如果root = null, 则二叉树中没有任何节点，直接return，或者报个错什么的。

循环查找

 search(key) {
 let p = this.root;
 if(!p) {
  return;
 }
 
 while(p && p.key !== key){
  if(p.key<key){
  p = p.right;
  }else{
  p = p.left;
  }
 }
 
 return p;
 }

遍历

中序遍历(inorder)：先遍历左节点，再遍历自己，最后遍历右节点，输出的刚好是有序的列表

前序遍历(preorder)：先自己，再遍历左节点，最后遍历右节点

后序遍历(postorder)：先左节点，再右节点，最后自己

最常用的一般是中序遍历，因为中序遍历可以得到一个已经排好序的列表，这也是为什么会用二叉搜索树排序的原因

根据上面对中序遍历的解释，那么代码就变的很简单，就是一个递归的过程，递归停止的条件就是节点为null

先遍历左节点-->yield* this._transverse(node.left)

遍历自己 --> yield* node

遍历左节点 --> yield* this._transverse(node.right)

 transverse() {
 return this._transverse(this.root);
 }
 
 *_transverse(node){
 if(!node){
  return;
 }
 yield* this._transverse(node.left);
 yield node;
 yield* this._transverse(node.right)
 }

看上面这张图，我们简化的来看一下，先访问左节点4，再自己12，然后右节点18，这样输出的就刚好是一个12，4，8

补充：这个地方用了generater，所以返回的一个迭代器。可以通过下面这种方式得到一个有序的数组，这里的前提就当是已经有插入的节点了

 const tree = new BinaryTree();
 //...中间省略插入过程
 
 // 这样就返回了一个有序的数组 
 var arr = [...tree.transverse()].map(item=>item.key);

完整代码

class BinaryTreeNode {
 constructor(key, value) {
 // 指向父节点
 this.p = null;

 // 左节点
 this.left = null;

 // 右节点
 this.right = null;

 // 键
 this.key = key;

 // 值
 this.value = value;
 }
}

class BinaryTree {
 constructor() {
 this.root = null;
 }

 static createNode(key, value) {
 return new BinaryTreeNode(key, value);
 }

 search(key) {
 let p = this.root;
 if (!p) {
 return;
 }

 while (p && p.key !== key) {
 if (p.key < key) {
 p = p.right;
 } else {
 p = p.left;
 }
 }

 return p;
 }

 insert(node) {
 // 尾指针的父节点指针
 let p = this.root;

 // 尾指针
 let tail = this.root;

 while (tail) {
 p = tail;
 if (node.key < tail.key) {
 tail = tail.left;
 } else {
 tail = tail.right;
 }
 }

 if (!p) {
 this.root = node;
 return;
 }

 // 插入
 if (p.key < node.key) {
 p.right = node;
 } else {
 p.left = node;
 }

 node.p = p;
 }

 transverse() {
 return this.__transverse(this.root);
 }

 *__transverse(node) {
 if (!node) {
 return;
 }
 yield* this.__transverse(node.left);
 yield node;
 yield* this.__transverse(node.right);
 }
}

总结

二叉查找树就讲完了哈，其实这个和链表很像的，还是操作那么几个指针，既然叫查找树了，它主要还是用来左一些搜索，还有就是排序了，另外补充一下，二叉查找树里找最大值和最小值也很方便是不是，如果你大致读懂了的话。

热心网友时间：2022-04-22 13:42

基本定义：
二叉树是每个结点最多有两个子树的有序树。
度就是结点的分支数，二叉树结点的度可能是0、1、2。
度为0的结点，称为叶结点。
以组成该树各结点中最大的度作为该树的度
树高也就是树的深度，指组成该树各结点的最大层次
完全二叉树就是指只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
满二叉树就是指除了叶结点外每一个结点都有左右子叶，且叶结点都处在最底层的二叉树
二叉树的应用：包括二叉树的建立、遍历、叶结点数、高度、左右子结点互换、等价性判断、复制、二叉搜索树的创建、线索二叉树的创建、搜索已知结点的层数、前中序确定二叉树等等
C语言的实现：
二叉树的链式存储
typedef struct node *tree_pointer;
struct node{
char ch;
tree_pointer left_child,right_child;
};

二叉树的建立
tree_pointer create(tree_pointer ptr)
{
char ch;
scanf("%c",&ch);
if(ch==' ')
ptr=NULL;
else{
ptr=(tree_pointer)malloc(sizeof(node));
ptr->ch=ch;
ptr->left_child=create(ptr->left_child);
ptr->right_child=create(ptr->right_child);
}
return ptr;
}

二叉树的前序遍历
void preorder(tree_pointer ptr)
{
if(ptr){
printf("%c",ptr->ch);
preorder(ptr->left_child);
preorder(ptr->right_child);
}
}

二叉树的中序遍历
void inorder(tree_pointer ptr)
{
if(ptr){
inorder(ptr->left_child);
printf("%c",ptr->ch);
inorder(ptr->right_child);
}
}

二叉树的后序遍历
void postorder(tree_pointer ptr)
{
if(ptr){
postorder(ptr->left_child);
postorder(ptr->right_child);
printf("%c",ptr->ch);
}
}

二叉树的层序遍历
void level_order(tree_pointer ptr)
{
if(!ptr)
printf("The tree is null\n");
else{
pushq(&rear,ptr);
for(;;){
ptr=popq(&front,rear);
if(ptr){
printf("%c",ptr->ch);
if(ptr->left_child)
pushq(&rear,ptr->left_child);
if(ptr->right_child)
pushq(&rear,ptr->right_child);
}
else break;
}
}
}

二叉树的叶结点数求解
int leaf(tree_pointer ptr)
{
if(!ptr)
return 0;
else{
if(!ptr->left_child&&!ptr->right_child)
return 1;
return leaf(ptr->left_child)+leaf(ptr->right_child);
}
}

二叉树的高度求解
int height(tree_pointer ptr)
{
if(!ptr)
return 0;
return 1+max(height(ptr->left_child),height(ptr->right_child));//构造max函数，返回较大值
}

二叉树的左右子结点互换
void exchange(tree_pointer ptr)
{
tree_pointer temp;
if(ptr){
temp=ptr->left_child;
ptr->left_child=ptr->right_child;
ptr->right_child=temp;
exchange(ptr->right_child);
exchange(ptr->left_child);
}
}

二叉树的等价性判断
int equal(tree_pointer first,tree_pointer second)
{
return((!first&&!second)
||(first&&second&&(first->ch==second->ch)
&&equal(first->left_child,second->left_child)
&&equal(first->right_child,second->right_child)));
}

二叉树的复制
tree_pointer copy(tree_pointer original)
{
tree_pointer temp;
if(original){
temp=(tree_pointer)malloc(sizeof(node));
temp->left_child=copy(original->left_child);
temp->right_child=copy(original->right_child);
temp->ch=original->ch;
return temp;
}
return NULL;
}

后面的应用程序相对比较大，不一一C语言实现了，值得一提的是二叉树的C语言实现一般采用递归的方式。

全部频道