GVKun编程网logo

数据结构与算法 -- 二叉树链式详解（（非）/递归遍历，叶子个数，深度计算）

11

针对数据结构与算法--二叉树链式详解和这两个问题，本篇文章进行了详细的解答，同时本文还将给你拓展C数据结构与算法树之二叉树、C++数据结构二叉树（前序/中序/后序递归、非递归遍历）、javascrip

针对数据结构与算法 -- 二叉树链式详解和这两个问题，本篇文章进行了详细的解答，同时本文还将给你拓展C 数据结构与算法 树之二叉树、C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）、javascript数据结构与算法--二叉树遍历（中序）、javascript数据结构与算法--二叉树遍历（先序）等相关知识，希望可以帮助到你。

本文目录一览：

数据结构与算法 -- 二叉树链式详解（（非）/递归遍历，叶子个数，深度计算）

数据结构与算法 -- 二叉树链式详解（（非）/递归遍历，叶子个数，深度计算）

前言

PS：树型结构是一种重要的非线性数据结构，教科书上一般都是树与二叉树，由此可见，树和二叉树是有区别和联系的，网上有人说二叉树是树的一种特殊形式，但经过查资料，树和二叉树没有一个肯定的说法，但唯一可以肯定都是树型结构。但是按照定义来看二叉树并不是树的一种特殊形式（下面解释）。树型数据结构的作用可以表示数据元素之间一对多的关系，一个公司里的各个部门都可以用树形来表示。

二叉树不是树的一种特殊情形，主要差别：

  1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
  2. 树的结点无左、右之分，而二叉树的结点有左、右之分。

二叉树类型

(1)完全二叉树 ——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

(2)满二叉树 ——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二叉树的链式

1：结构体

/*
刘志通
**/

typedef struct twoCha {
    char data;
    struct twoCha *Lchild, *Rchild;//左右孩子结点
} twoCha, *twoChaL;

2：创建二叉树

当我们在键盘上敲了一行的char类型数据，可以按照一定的结构储存在计算机上，就要写一个算法，二叉树分左右孩子，所以，如果没有左（右）孩子就输入一个空格或者#，代表空。如果有左（右）孩子就新建一个结点，来存放该结点的数据data。

int createTwo(twoChaL &tL) {
    char ch;
    scanf("%c",&ch);
    if (ch == ''#'')
    {
        tL = NULL;
        return 0;
    }
    else
    {
        tL= (twoChaL)malloc(sizeof(twoCha));
        if (tL == NULL)
        {
            printf("错误tl=NULL\n");
            return 0;
        }
        else
        {
            tL->data = ch;
            createTwo(tL->Lchild);
            createTwo(tL->Rchild);
        }
    }
    return 0;
}

3：递归遍历

画的不好，凑活着看吧。

我们以这个二叉树为例子，来分析他的遍历形式，遍历分为三种

  • 先序遍历 -- 根左右 -- ABDCE
  • 中序遍历 -- 左根右 -- DBAEC
  • 后序遍历 -- 左右根 -- DBECA
void diGuiBianLi(twoChaL &tL,int xl)
{
    if (tL == NULL)
    {
        return;
    }
    else
    {
        if(xl == 1){
            //先序遍历
            printf("%c ",tL->data);
            diGuiBianLi(tL->Lchild,xl);
            diGuiBianLi(tL->Rchild,xl);
        }else if(xl == 2){
            //中序遍历
            diGuiBianLi(tL->Lchild,xl);
            printf("%c ",tL->data);
            diGuiBianLi(tL->Rchild,xl);
        }
        else if(xl == 3){
            //后序遍历
            diGuiBianLi(tL->Lchild,xl);
            diGuiBianLi(tL->Rchild,xl);
            printf("%c ",tL->data);
        }
    }
}

递归的代码非常少，但是一开始接触 理解起来还是比较难的，当然，你一旦理解后，那就非常简单了。递归的思想就是把一个大问题分成多个类似的小问题解决。

4：叶子个数

方法：查找一个结点没有左右孩子，就是叶子结点。可以定义一个static int count变量，如果该结点没有左右结点那么就让count++；

int leafCount(twoChaL &tL)
{
    static int count;
    if (tL != NULL)
    {
        if (tL->Lchild == NULL && tL->Rchild == NULL)
        {
            count++;
        }
        leafCount(tL->Lchild);
        leafCount(tL->Rchild);
    }

    return count;
}

5：深度

方法：看结点的左孩子和右孩子哪一个更长，当深入到最低结点时，左右孩子比较，谁大谁加一（相等左孩子加一）。

int treeDeep(twoChaL &tL)
{
    int deep = 0;
    if (tL != NULL)
    {
        int leftdeep = treeDeep(tL->Lchild);
        int rightdeep = treeDeep(tL->Rchild);
        deep = leftdeep >= rightdeep?leftdeep+1:rightdeep+1;
    }
    return deep;
}

 6：非递归遍历

这里以中序为例，利用栈的知识点（顺序栈），首先把根节点进栈，然后依次左孩子进栈，直到左孩子为NULL时结束，但是NULL也是入栈的，然后再把NULL出栈，下一步就是把栈顶元素取出并打印，再把该栈顶元素的右孩子进栈，不管右孩子是不是NULL都要入栈，入栈之前把栈顶元素弹栈。

定义栈的data域，要用结点的结构体

int top = -1;
//栈
void push(twoChaL *a,twoChaL elem){
    a[++top]=elem;
}
//弹栈函数
void pop(){
    if (top==-1) {
        return ;
    }
    top--;
}
//拿到栈顶元素
twoChaL getTop(twoChaL *a){
    return a[top];
}

void zhongXu2(twoChaL Tree){
    //顺序栈
    twoChaL a[100];
    twoChaL p;
    push(a, Tree);//根结点进栈
    while (top!=-1) {//top!=-1说明栈内不为空
        while ((p=getTop(a)) &&p){//取栈顶元素，且不能为NULL
            push(a, p->Lchild);//将该结点的左孩子进栈，如果没有左孩子，NULL进栈
        }
        pop();//跳出循环，栈顶元素肯定为NULL，将NULL弹栈
        /*
        //测试数据，主要观察栈中NULL出栈后，还有什么在栈中（栈顶）,
          if(a[top]){
            printf(" 跳出循环 %c\n",a[top]->data);
        }*/

        if (top!=-1) {
            p=getTop(a);//取栈顶元素
            pop();//栈顶元素弹栈
            printf("%c ",p->data);
            push(a, p->Rchild);//将p指向的结点的右孩子进栈
        }
    }
}

结果图：

讨论群

C 数据结构与算法 树之二叉树

C 数据结构与算法 树之二叉树

树 非线性数据结构

稍后补充更多描述以及二叉树的链式存储结构代码

C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）

C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）

C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）

二叉树的性质：

二叉树是一棵特殊的树，二叉树每个节点最多有两个孩子结点，分别称为左孩子和右孩子。

例：

实例代码：

#include <iostream> 
#include <Windows.h> 
#include <stack> 
using namespace std; 
 
template <class T> 
struct BinaryTreeNode 
{ 
 int _data; 
 BinaryTreeNode<T>* _left; //左孩子 
 BinaryTreeNode<T>* _right;  //右孩子 
 BinaryTreeNode(const T& data) 
  :_data(data),_left(NULL),_right(NULL) 
 {} 
}; 
 
template <class T> 
class BinaryTree 
{ 
 typedef BinaryTreeNode<T> Node; 
public: 
 BinaryTree() 
  :_root(NULL) 
 {} 
 
 BinaryTree(T* arr,size_t n,const T& invalid=T()) 
 { 
  size_t index = 0; 
  _root = _CreatTree(arr,n,invalid,index); 
 } 
 
 void PreOrderR()  //前序遍历 递归 
 { 
  _PreOrderR(_root); 
 } 
 
 void PreOrder()  //前序遍历 非递归 
 { 
  _PreOrder(_root); 
 } 
 
 void InorderR() //中序遍历 递归 
 { 
  _InorderR(_root); 
 } 
 
 void Inorder()   //中序遍历  非递归 
 { 
  _Inorder(_root);  
 } 
 
 void postorderR()  //后序遍历 左 右 根  递归 
 { 
  _postorderR(_root);  
 } 
 
 void postorder()  //后序遍历 左 右 根  非递归 
 { 
  _postorder(_root);  
 } 
 
 ~BinaryTree() 
 {} 
 
protected: 
 //建树 arr:建树使用的数组 n：数组大小 invalid:非法值 index:当前下标 
 Node* _CreatTree(T* arr,const T& invalid,size_t& index) 
 { 
  Node* root = NULL; 
  if (index < n && arr[index] != invalid) 
  { 
   root = new Node(arr[index]); //根节点 
   root->_left = _CreatTree(arr,++index); 
   root->_right = _CreatTree(arr,++index); 
  } 
  return root;  
 } 
 
 void _PreOrderR(Node* root)  //前序遍历 递归 
 { 
  if (root == NULL) 
  { 
   return; 
  } 
  cout << root->_data << " "; 
  _PreOrderR(root->_left); 
  _PreOrderR(root->_right); 
 } 
 
 void _PreOrder(Node* root)  //前序遍历 非递归 
 { 
  stack<Node*> tty; 
  while (root != NULL || !tty.empty()) 
  { 
   if (root) 
   { 
    cout << root->_data << " "; 
    tty.push(root); 
    root = root->_left; 
   } 
   else 
   { 
    Node* temp = tty.top(); 
    tty.pop(); 
    root = temp->_right; 
   } 
  } 
 } 
 
 void _InorderR(Node* root) //中序遍历 递归 
 { 
  if (root == NULL) 
  { 
   return; 
  } 
  _InorderR(root->_left); 
  cout << root->_data << " "; 
  _InorderR(root->_right); 
 } 
 
 void _Inorder(Node* root) //中序遍历 非递归 
 { 
  if (root == NULL) 
  { 
   return; 
  } 
  stack<Node*> tty; 
  while (root != NULL || !tty.empty()) 
  { 
   while (root) 
   { 
    tty.push(root); 
    root = root->_left; 
   } 
   //此时出了循环走到了最左叶子节点 
   Node* temp = tty.top(); 
   tty.pop(); 
   cout << temp->_data << " "; 
   root = temp->_right; 
  } 
 } 
 
 void _postorderR(Node* root)  //后序遍历 左 右 根  递归 
 { 
  if (root == NULL) 
  { 
   return; 
  } 
  _postorderR(root->_left); 
  _postorderR(root->_right); 
  cout << root->_data << " "; 
 } 
 
 void _postorder(Node* root)  //后序遍历 左 右 根  非递归 
 { 
  if (root == NULL) 
  { 
   return; 
  } 
  stack<Node*> tty; 
  Node* PreNode = NULL; //上一个访问的结点 
  tty.push(root); 
  while (!tty.empty()) 
  { 
   Node* cur = tty.top(); 
   //访问的当前节点左右孩子均为空或者当前节点左右子树均已经访问过 
   if ((cur->_left == NULL && cur->_right == NULL) || ((PreNode != NULL) && (PreNode == cur->_left || PreNode == cur->_right))) 
   { 
    cout << cur->_data << " "; 
    tty.pop(); 
    PreNode = cur; 
   } 
   else 
   { 
    if (cur->_right != NULL) 
    { 
     tty.push(cur->_right); 
    } 
    if (cur->_left != NULL) 
    { 
     tty.push(cur->_left); 
    } 
   } 
  } 
 } 
 
protected: 
 Node* _root; 
}; 

#include "源.h" 
 
void test() 
{ 
 int array[10] = { 1,2,3,'#',4,5,6 }; 
 BinaryTree<int> p(array,sizeof(array) / sizeof(array[0]),'#'); 
 cout << "前序递归遍历： " << ""; 
 p.PreOrderR(); 
 cout << endl; 
 
 cout << "前序非递归遍历： " << ""; 
 p.PreOrder(); 
 cout << endl; 
 
 cout << "中序递归遍历： " << ""; 
 p.InorderR(); 
 cout << endl; 
 
 cout << "中序非递归遍历： " << ""; 
 p.Inorder(); 
 cout << endl; 
 
 cout << "后序递归遍历： " << ""; 
 p.postorderR(); 
 cout << endl; 
 
 cout << "后序非递归遍历： " << ""; 
 p.postorder(); 
 cout << endl; 
} 
 
int main() 
{ 
 test(); 
 system("pause"); 
 return 0; 
}


实现效果：

以上就是数据结构二叉树的详解，如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

javascript数据结构与算法--二叉树遍历（中序）

javascript数据结构与算法--二叉树遍历（中序）

javascript数据结构与算法--二叉树遍历（中序）

中序遍历按照节点上的键值，以升序访问BST上的所有节点

 

 代码如下：

<span>/<span>用来生成一个节点<span>/
<span>function<span> Node(data,left,right) {
<span>this.data = data;<span>//<span>节点存储的数据
<span>this.left =<span> left;
<span>this.right =<span> right;
<span>this.show =<span> show;
}

<span>function<span> show() {
<span>return <span>this<span>.data;
}

<span>/<span>用来生成一个二叉树<span>/
<span>function<span> BST() {
<span>this.root = <span>null<span>;
<span>this.insert =<span> insert;
}

<span>/*<span>将数据插入二叉树
（1）设根节点为当前节点。
（2）如果待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点；反
之，执行第4步。
（3）如果当前节点的左节点为null，就将新的节点插入这个位置，退出循环；反之，继续
执行下一次循环。
（4）设新的当前节点为原节点的右节点。
（5）如果当前节点的右节点为null，就将新的节点插入这个位置，退出循环；反之，继续
执行下一次循环。

  • <span>*/
    <span>function<span> insert(data) {
    <span>var n = <span>new Node(data,<span>null,<span>null<span>);
    <span>if (<span>this.root == <span>null<span>) {
    <span>this.root =<span> n;
    }
    <span>else<span> {
    <span>var current = <span>this<span>.root;
    <span>var<span> parent;
    <span>while (<span>true<span>) {
    parent =<span> current;
    <span>if (data <<span> current.data) {
    current = current.left;<span>//<span>待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点
    <span>if (current == <span>null) {<span>//<span>如果当前节点的左节点为null，就将新的节点插入这个位置，退出循环；反之，继续执行下一次while循环。
    parent.left =<span> n;
    <span>break<span>;
    }
    }
    <span>else<span> {
    current = current.right;<span>//<span>待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点
    <span>if (current == <span>null<span>) {
    parent.right =<span> n;
    <span>break<span>;
    }
    }
    }
    }
    }

<span><span>/中序遍历
用递归的方法
/
<span>function<span> inorder(node) {
<span>if (!(node == <span>null<span>)) {
inorder(node.left);
console.log(node.show() + " "<span>);
inorder(node.right);
}
}

/ 测试代码 */
<span>var nums = <span>new<span> BST();
nums.insert(23<span>);
nums.insert(45<span>);
nums.insert(16<span>);
nums.insert(37<span>);
nums.insert(3<span>);
nums.insert(99<span>);
nums.insert(22<span>);
console.log("中序遍历: "<span>);
inorder(nums.root);

 

javascript数据结构与算法--二叉树遍历（先序）

javascript数据结构与算法--二叉树遍历（先序）

 javascript数据结构与算法--二叉树遍历（先序）

先序遍历先访问根节点， 然后以同样方式访问左子树和右子树 

 

 

 代码如下：

<span>/<span>用来生成一个节点<span>/
<span>function<span> Node(data,left,right) {
<span>this.data = data;<span>//<span>节点存储的数据
<span>this.left =<span> left;
<span>this.right =<span> right;
<span>this.show =<span> show;
}

<span>function<span> show() {
<span>return <span>this<span>.data;
}

<span>/<span>用来生成一个二叉树<span>/
<span>function<span> BST() {
<span>this.root = <span>null<span>;
<span>this.insert =<span> insert;
}

<span>/*<span>将数据插入二叉树
（1）设根节点为当前节点。
（2）如果待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点；反
之，执行第4步。
（3）如果当前节点的左节点为null，就将新的节点插入这个位置，退出循环；反之，继续
执行下一次循环。
（4）设新的当前节点为原节点的右节点。
（5）如果当前节点的右节点为null，就将新的节点插入这个位置，退出循环；反之，继续
执行下一次循环。

  • <span>*/
    <span>function<span> insert(data) {
    <span>var n = <span>new Node(data,<span>null,<span>null<span>);
    <span>if (<span>this.root == <span>null<span>) {
    <span>this.root =<span> n;
    }
    <span>else<span> {
    <span>var current = <span>this<span>.root;
    <span>var<span> parent;
    <span>while (<span>true<span>) {
    parent =<span> current;
    <span>if (data <<span> current.data) {
    current = current.left;<span>//<span>待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点
    <span>if (current == <span>null) {<span>//<span>如果当前节点的左节点为null，就将新的节点插入这个位置，退出循环；反之，继续执行下一次while循环。
    parent.left =<span> n;
    <span>break<span>;
    }
    }
    <span>else<span> {
    current = current.right;<span>//<span>待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点
    <span>if (current == <span>null<span>) {
    parent.right =<span> n;
    <span>break<span>;
    }
    }
    }
    }
    }

<span>/<span>先序遍历
用递归的方法
<span>*/
<span>function<span> preOrder(node) {
<span>if (!(node == <span>null<span>)) {
console.log(node.show() + " "<span>);
preOrder(node.left);
preOrder(node.right);
}
}

<span>/<span> 测试代码 <span>/
<span>var nums = <span>new<span> BST();
nums.insert(23<span>);
nums.insert(45<span>);
nums.insert(16<span>);
nums.insert(37<span>);
nums.insert(3<span>);
nums.insert(99<span>);
nums.insert(22<span>);
console.log("先序遍历: "<span>);
preOrder(nums.root);

 

我们今天的关于数据结构与算法 -- 二叉树链式详解和的分享就到这里，谢谢您的阅读，如果想了解更多关于C 数据结构与算法 树之二叉树、C++ 数据结构二叉树（前序/中序/后序递归、非递归遍历）、javascript数据结构与算法--二叉树遍历（中序）、javascript数据结构与算法--二叉树遍历（先序）的相关信息，可以在本站进行搜索。

本文标签：

上一篇arcgis engine计算点到线的最短距离（arcgis计算点到线的最小距离）

下一篇云计算，因何而生？（云计算意味着什么）

相关文章